c# - 在大量数据中快速(子)字符串搜索

Question

给定一个城市:

public class City
{
    public int Id { get; set; }
    public string Name { get; set; }
    public string Country { get; set; }
    public LatLong Location { get; set; }
}

我在一个文件中列出了将近 3,000,000 个城市(以及城镇和村庄等)。该文件被读入内存；我一直在玩数组、列表、字典 (key = Id) 等。

我想尽快找到与子字符串匹配的所有城市(不区分大小写)。因此，当我搜索“yor”时，我想尽快获得所有匹配项 (1000+)(匹配“York Town”、“Villa Mayor”、“New < strong>York', ...).

在功能上你可以这样写:

cities.Values.Where(c => c.Name.IndexOf("yor", StringComparison.OrdinalIgnoreCase) >= 0)

我不介意在读取文件时做一些预处理；事实上:这就是我最想要的。阅读文件，“咀嚼”数据以创建某种索引或...然后准备好回答诸如“yor”之类的查询。

我希望它是独立的、独立的。我不想添加 RDBMS、ElasticSearch 或其他任何依赖项。我不介意在内存中不止一次地拥有(部分)列表。我不介意在数据结构上花费一些内存来帮助我快速找到我的结果。我不想要库或包。我想要一个我可以自己实现的算法。

基本上我想要上面的 LINQ 语句，但针对我的情况进行了优化；目前浏览近 3,000,000 条记录大约需要 +/- 2 秒。我想要这个低于 0.1 秒的时间，这样我就可以使用搜索并将其结果作为“自动完成”。

创建一个“索引”(类似)结构可能正是我所需要的。在我写作时，我记得一些关于“bloom filter”的事情，但我不确定这是否有助于甚至支持子字符串搜索。现在会调查。

非常感谢任何提示、指示和帮助。

Answer 1

我创建了一些基于后缀数组/字典的混合体。感谢saibot感谢首先提出建议，以及所有其他帮助和建议的人。

这是我想出的:

public class CitiesCollection
{
    private Dictionary<int, City> _cities;
    private SuffixDict<int> _suffixdict;

    public CitiesCollection(IEnumerable<City> cities, int minLen)
    {
        _cities = cities.ToDictionary(c => c.Id);
        _suffixdict = new SuffixDict<int>(minLen, _cities.Values.Count);
        foreach (var c in _cities.Values)
            _suffixdict.Add(c.Name, c.Id);
    }

    public IEnumerable<City> Find(string find)
    {
        var normalizedFind = _suffixdict.NormalizeString(find);
        foreach (var id in _suffixdict.Get(normalizedFind).Where(v => _cities[v].Name.IndexOf(normalizedFind, StringComparison.OrdinalIgnoreCase) >= 0))
            yield return _cities[id];
    }
}


public class SuffixDict<T>
{
    private readonly int _suffixsize;
    private ConcurrentDictionary<string, IList<T>> _dict;

    public SuffixDict(int suffixSize, int capacity)
    {
        _suffixsize = suffixSize;
        _dict = new ConcurrentDictionary<string, IList<T>>(Environment.ProcessorCount, capacity);
    }

    public void Add(string suffix, T value)
    {
        foreach (var s in GetSuffixes(suffix))
            AddDict(s, value);
    }

    public IEnumerable<T> Get(string suffix)
    {
        return Find(suffix).Distinct();
    }

    private IEnumerable<T> Find(string suffix)
    {
        foreach (var s in GetSuffixes(suffix))
        {
            if (_dict.TryGetValue(s, out var result))
                foreach (var i in result)
                    yield return i;
        }
    }

    public string NormalizeString(string value)
    {
        return value.Normalize().ToLowerInvariant();
    }

    private void AddDict(string suffix, T value)
    {
        _dict.AddOrUpdate(suffix, (s) => new List<T>() { value }, (k, v) => { v.Add(value); return v; });
    }

    private IEnumerable<string> GetSuffixes(string value)
    {
        var nv = NormalizeString(value);
        for (var i = 0; i <= nv.Length - _suffixsize ; i++)
            yield return nv.Substring(i, _suffixsize);
    }
}

用法(我假设 mycities 是一个 IEnumerable<City> 与问题中给定的 City 对象):

var cc = new CitiesCollection(mycities, 3);
var results = cc.Find("york");

一些结果:

Find: sterda elapsed: 00:00:00.0220522 results: 32
Find: york   elapsed: 00:00:00.0006212 results: 155
Find: dorf   elapsed: 00:00:00.0086439 results: 6095

内存使用非常非常可以接受。总共只有 650MB，内存中包含 3,000,000 个城市的全部集合。

在上面我将 Id 存储在“SuffixDict”中并且我有一个间接级别(字典查找以找到 id=>city)。这可以进一步简化为:

public class CitiesCollection
{
    private SuffixDict<City> _suffixdict;

    public CitiesCollection(IEnumerable<City> cities, int minLen, int capacity = 1000)
    {
        _suffixdict = new SuffixDict<City>(minLen, capacity);
        foreach (var c in cities)
            _suffixdict.Add(c.Name, c);
    }

    public IEnumerable<City> Find(string find, StringComparison stringComparison = StringComparison.OrdinalIgnoreCase)
    {
        var normalizedFind = SuffixDict<City>.NormalizeString(find);
        var x = _suffixdict.Find(normalizedFind).ToArray();
        foreach (var city in _suffixdict.Find(normalizedFind).Where(v => v.Name.IndexOf(normalizedFind, stringComparison) >= 0))
            yield return city;
    }
}

public class SuffixDict<T>
{
    private readonly int _suffixsize;
    private ConcurrentDictionary<string, IList<T>> _dict;

    public SuffixDict(int suffixSize, int capacity = 1000)
    {
        _suffixsize = suffixSize;
        _dict = new ConcurrentDictionary<string, IList<T>>(Environment.ProcessorCount, capacity);
    }

    public void Add(string suffix, T value)
    {
        foreach (var s in GetSuffixes(suffix, _suffixsize))
            AddDict(s, value);
    }

    public IEnumerable<T> Find(string suffix)
    {
        var normalizedfind = NormalizeString(suffix);
        var find = normalizedfind.Substring(0, Math.Min(normalizedfind.Length, _suffixsize));

        if (_dict.TryGetValue(find, out var result))
            foreach (var i in result)
                yield return i;
    }

    private void AddDict(string suffix, T value)
    {
        _dict.AddOrUpdate(suffix, (s) => new List<T>() { value }, (k, v) => { v.Add(value); return v; });
    }

    public static string NormalizeString(string value)
    {
        return value.Normalize().ToLowerInvariant();
    }

    private static IEnumerable<string> GetSuffixes(string value, int suffixSize)
    {
        var nv = NormalizeString(value);
        if (value.Length < suffixSize)
        {
            yield return nv;
        }
        else
        {
            for (var i = 0; i <= nv.Length - suffixSize; i++)
                yield return nv.Substring(i, suffixSize);
        }
    }
}

这会增加加载时间 00:00:16.3899085至 00:00:25.6113214 ，内存使用量从 650MB 下降到 486MB。查找/搜索的性能要好一些，因为我们少了一层间接。

Find: sterda elapsed: 00:00:00.0168616 results: 32
Find: york elapsed: 00:00:00.0003945 results: 155
Find: dorf elapsed: 00:00:00.0062015 results: 6095

我对目前的结果很满意。我会做一些润色和重构，然后收工!感谢大家的帮助!

这是它在 2,972,036 个城市中的表现:

通过修改代码，这已经演变成不区分大小写、不区分重音的搜索:

public static class ExtensionMethods
{
    public static T FirstOrDefault<T>(this IEnumerable<T> src, Func<T, bool> testFn, T defval)
    {
        return src.Where(aT => testFn(aT)).DefaultIfEmpty(defval).First();
    }

    public static int IndexOf(this string source, string match, IEqualityComparer<string> sc)
    {
        return Enumerable.Range(0, source.Length) // for each position in the string
                         .FirstOrDefault(i => // find the first position where either
                                              // match is Equals at this position for length of match (or to end of string) or
                             sc.Equals(source.Substring(i, Math.Min(match.Length, source.Length - i)), match) ||
                             // match is Equals to on of the substrings beginning at this position
                             Enumerable.Range(1, source.Length - i - 1).Any(ml => sc.Equals(source.Substring(i, ml), match)),
                             -1 // else return -1 if no position matches
                          );
    }
}

public class CaseAccentInsensitiveEqualityComparer : IEqualityComparer<string>
{
    private static readonly CompareOptions _compareoptions = CompareOptions.IgnoreCase | CompareOptions.IgnoreNonSpace | CompareOptions.IgnoreKanaType | CompareOptions.IgnoreWidth | CompareOptions.IgnoreSymbols;
    private static readonly CultureInfo _cultureinfo = CultureInfo.InvariantCulture;
    public bool Equals(string x, string y)
    {
        return string.Compare(x, y, _cultureinfo, _compareoptions) == 0;
    }

    public int GetHashCode(string obj)
    {
        return obj != null ? RemoveDiacritics(obj).ToUpperInvariant().GetHashCode() : 0;
    }

    private string RemoveDiacritics(string text)
    {
        return string.Concat(
            text.Normalize(NormalizationForm.FormD)
            .Where(ch => CharUnicodeInfo.GetUnicodeCategory(ch) != UnicodeCategory.NonSpacingMark)
        ).Normalize(NormalizationForm.FormC);
    }
}

public class CitiesCollection
{
    private SuffixDict<City> _suffixdict;
    private HashSet<string> _countries;
    private Dictionary<int, City> _cities;
    private readonly IEqualityComparer<string> _comparer = new CaseAccentInsensitiveEqualityComparer();

    public CitiesCollection(IEnumerable<City> cities, int minLen, int capacity = 1000)
    {
        _suffixdict = new SuffixDict<City>(minLen, _comparer, capacity);
        _countries = new HashSet<string>();
        _cities = new Dictionary<int, City>(capacity);
        foreach (var c in cities)
        {
            _suffixdict.Add(c.Name, c);
            _countries.Add(c.Country);
            _cities.Add(c.Id, c);
        }
    }

    public City this[int index] => _cities[index];

    public IEnumerable<string> Countries => _countries;

    public IEnumerable<City> Find(string find, StringComparison stringComparison = StringComparison.OrdinalIgnoreCase)
    {
        foreach (var city in _suffixdict.Find(find).Where(v => v.Name.IndexOf(find, _comparer) >= 0))
            yield return city;
    }
}

public class SuffixDict<T>
{
    private readonly int _suffixsize;
    private ConcurrentDictionary<string, IList<T>> _dict;

    public SuffixDict(int suffixSize, IEqualityComparer<string> stringComparer, int capacity = 1000)
    {
        _suffixsize = suffixSize;
        _dict = new ConcurrentDictionary<string, IList<T>>(Environment.ProcessorCount, capacity, stringComparer);
    }

    public void Add(string suffix, T value)
    {
        foreach (var s in GetSuffixes(suffix, _suffixsize))
            AddDict(s, value);
    }

    public IEnumerable<T> Find(string suffix)
    {
        var find = suffix.Substring(0, Math.Min(suffix.Length, _suffixsize));

        if (_dict.TryGetValue(find, out var result))
        {
            foreach (var i in result)
                yield return i;
        }
    }

    private void AddDict(string suffix, T value)
    {
        _dict.AddOrUpdate(suffix, (s) => new List<T>() { value }, (k, v) => { v.Add(value); return v; });
    }

    private static IEnumerable<string> GetSuffixes(string value, int suffixSize)
    {
        if (value.Length < 2)
        {
            yield return value;
        }
        else
        {
            for (var i = 0; i <= value.Length - suffixSize; i++)
                yield return value.Substring(i, suffixSize);
        }
    }
}

感谢Netmage和 Mitsugui .仍然存在一些问题/边缘情况，但它正在不断改进!