c# - 用于在字符串列表 C# 中查找字符串匹配的最佳比较算法

Question

假设我有一个包含 100,000 个单词的列表。我想查明给定的字符串是否与该列表中的任何单词匹配，并且我想以最快的方式进行。我还想知道该字符串中以第一个字符开头形成的任何其他单词是否出现在列表中。

例如:

假设你有字符串“icedtgg”

“我”“我知道了”“冰”“冰镇”“冰”“icedtg”“icedtgg”

我正在尝试提出一个最佳比较算法，告诉我以下单词是否在我的列表中。

到目前为止，我的 100,000 个单词列表存储在一个

Dicitonary<char, List<string>> WordList;

哪里char是单词的第一个字符，List<string>是以该字符开头的所有单词。

所以 WordList['a']有一个以“a”开头的所有单词的列表(“ape”、“apple”、“art”等)，而“b”有一个以 b 开头的所有单词的列表等。

因为我知道我所有的单词都以“i”开头，所以我可以先将我的解决方案从 100,000 个单词缩小到仅以“i”开头的单词。

List<string> CurrentWordList = WordList['i'];

现在我检查

if( CurrentWordList[0].Length == 1 )

然后我知道我的第一个字符串匹配“i”，因为“i”将是列表中的第一个单词。这些列表预先按字母顺序排序，以免减慢匹配速度。

有什么想法吗？

*不，这不是硬件分配，我是一名专业的软件架构师，试图为乐趣/爱好/游戏开发找到最佳匹配算法。

Answer 1

我决定添加这个答案并不是因为它是您问题的最佳解决方案，而是为了说明两种可能的解决方案，这些解决方案相对简单并且在某种程度上符合您似乎正在遵循的方法。

下面的(未优化的)示例提供了一个极其简单的前缀特里树实现，每个消耗的字符使用一个节点。

public class SimplePrefixTrie
{
    private readonly Node _root = new Node(); // root represents empty string.

    private class Node
    {
        public Dictionary<char, Node> Children;
        public bool IsTerminal; // whether a full word ends here.

        public Node Find(string word, int index)
        {
            var child = default(Node);
            if (index < word.Length && Children != null)
                Children.TryGetValue(word[index], out child);
            return child;
        }

        public Node Add(string word, int toConsume)
        {
            var child = default(Node);
            if (toConsume == word.Length)
                this.IsTerminal = true;
            else if (Children == null || !Children.TryGetValue(word[toConsume], out child))
            {
                if (Children == null)
                    Children = new Dictionary<char, Node>();
                Children[word[toConsume]] = child = new Node();
            }
            return child;
        }
    }

    public void AddWord(string word)
    {
        var ndx = 0;
        var cur = _root;
        while (cur != null)
            cur = cur.Add(word, ndx++);
    }

    public IEnumerable<string> FindWordsMatchingPrefixesOf(string searchWord)
    {
        var ndx = 0;
        var cur = _root;
        while (cur != null)
        {
            if (cur.IsTerminal)
                yield return searchWord.Substring(0, ndx);
            cur = cur.Find(searchWord, ndx++);
        }
    }
}

下面还添加了一个压缩前缀特里树的简单实现。它遵循与上述示例几乎相同的方法，但存储共享前缀部分，而不是单个字符。当现有的存储前缀变为共享且需要拆分为两部分时，它会拆分节点。

public class SimpleCompressedPrefixTrie
{
    private readonly Node _root = new Node();

    private class Node
    {
        private Dictionary<char, Node> _children;
        public string PrefixValue = string.Empty;
        public bool IsTerminal;

        public Node Add(string word, ref int startIndex)
        {
            var n = FindSharedPrefix(word, startIndex);
            startIndex += n;
            if (n == PrefixValue.Length) // full prefix match
            {
                if (startIndex == word.Length) // full match
                    IsTerminal = true;
                else
                    return AddToChild(word, ref startIndex);
            }
            else // partial match, need to split this node's prefix.
                SplittingAdd(word, n, ref startIndex);
            return null;
        }

        public Node Find(string word, ref int startIndex, out int matchLen)
        {
            var n = FindSharedPrefix(word, startIndex);
            startIndex += n;
            matchLen = -1;
            if (n == PrefixValue.Length)
            {
                if (IsTerminal)
                    matchLen = startIndex;
                var child = default(Node);
                if (_children != null && startIndex < word.Length && _children.TryGetValue(word[startIndex], out child))
                {
                    startIndex++; // consumed map key character.
                    return child;
                }
            }
            return null;
        }

        private Node AddToChild(string word, ref int startIndex)
        {
            var key = word[startIndex++]; // consume the mapping character
            var nextNode = default(Node);
            if (_children == null)
                _children = new Dictionary<char, Node>();
            else if (_children.TryGetValue(key, out nextNode))
                return nextNode;
            var remainder = word.Substring(startIndex);
            _children[key] = new Node() { PrefixValue = remainder, IsTerminal = true };
            return null; // consumed.
        }

        private void SplittingAdd(string word, int n, ref int startIndex)
        {
            var curChildren = _children;
            _children = new Dictionary<char, Node>();
            _children[PrefixValue[n]] = new Node()
            {
                PrefixValue = this.PrefixValue.Substring(n + 1),
                IsTerminal = this.IsTerminal,
                _children = curChildren
            };
            PrefixValue = PrefixValue.Substring(0, n);
            IsTerminal = startIndex == word.Length;
            if (!IsTerminal)
            {
                var prefix = word.Length > startIndex + 1 ? word.Substring(startIndex + 1) : string.Empty;
                _children[word[startIndex]] = new Node() { PrefixValue = prefix, IsTerminal = true };
                startIndex++;
            }
        }

        private int FindSharedPrefix(string word, int startIndex)
        {
            var n = Math.Min(PrefixValue.Length, word.Length - startIndex);
            var len = 0;
            while (len < n && PrefixValue[len] == word[len + startIndex])
                len++;
            return len;
        }
    }

    public void AddWord(string word)
    {
        var ndx = 0;
        var cur = _root;
        while (cur != null)
            cur = cur.Add(word, ref ndx);
    }

    public IEnumerable<string> FindWordsMatchingPrefixesOf(string searchWord)
    {
        var startNdx = 0;
        var cur = _root;
        while (cur != null)
        {
            var matchLen = 0;
            cur = cur.Find(searchWord, ref startNdx, out matchLen);
            if (matchLen > 0)
                yield return searchWord.Substring(0, matchLen);
        };
    }
}

使用示例:

var trie = new SimplePrefixTrie(); // or new SimpleCompressedPrefixTrie();
trie.AddWord("hello");
trie.AddWord("iced");
trie.AddWord("i");
trie.AddWord("ice");
trie.AddWord("icecone");
trie.AddWord("dtgg");
trie.AddWord("hicet");
foreach (var w in trie.FindWordsMatchingPrefixesOf("icedtgg"))
    Console.WriteLine(w);

输出:

i
ice
iced

更新:选择正确的数据结构很重要

我认为更新可以提供一些值(value)来说明选择适合问题的数据结构的重要性以及涉及哪些类型的权衡。因此，我创建了一个小型基准测试应用程序，用于测试到目前为止为该问题提供的答案中的策略，并与基准引用实现进行比较。

• 朴素:是最简单的朴素解决方案。
• JimMischel:基于 this answer 中的方法.
• MattyMerrix:是根据你自己的回答here .
• JimMattyDSL:结合了“JimMischel”和“MattyMerrix”方法，并在排序列表中使用更优化的二进制字符串搜索。
• SimpleTrie 和 CompessedTrie 基于此答案中描述的两个实现。

完整的基准代码可以在 this gist 中找到.使用 10,000、100,000 和 1,000,000(随机生成的字符序列)单词的词典运行它并搜索 5,000 个术语的所有前缀匹配的结果是:

将 5000 个单词匹配到最大长度为 25 的 10000 个术语的字典

       Method              Memory (MB)         Build Time (s)        Lookup Time (s)
        Naive          0.64-0.64, 0.64     0.001-0.002, 0.001     6.136-6.312, 6.210
   JimMischel          0.84-0.84, 0.84     0.013-0.018, 0.016     0.083-0.113, 0.102
  JimMattyDSL          0.80-0.81, 0.80     0.013-0.018, 0.016     0.008-0.011, 0.010
   SimpleTrie       24.55-24.56, 24.56     0.042-0.056, 0.051     0.002-0.002, 0.002
CompessedTrie          1.84-1.84, 1.84     0.003-0.003, 0.003     0.002-0.002, 0.002
  MattyMerrix          0.83-0.83, 0.83     0.017-0.017, 0.017     0.034-0.034, 0.034

将 5000 个单词匹配到最大长度为 25 的 100000 个术语的字典

       Method              Memory (MB)         Build Time (s)        Lookup Time (s)
        Naive          6.01-6.01, 6.01     0.024-0.026, 0.025  65.651-65.758, 65.715
   JimMischel          6.32-6.32, 6.32     0.232-0.236, 0.233     1.208-1.254, 1.235
  JimMattyDSL          5.95-5.96, 5.96     0.264-0.269, 0.266     0.050-0.052, 0.051
   SimpleTrie    226.49-226.49, 226.49     0.932-0.962, 0.951     0.004-0.004, 0.004
CompessedTrie       16.10-16.10, 16.10     0.101-0.126, 0.111     0.003-0.003, 0.003
  MattyMerrix          6.15-6.15, 6.15     0.254-0.269, 0.259     0.414-0.418, 0.416

将 5000 个单词匹配到最大长度为 25 的 1000000 个术语的字典

       Method              Memory (MB)         Build Time (s)        Lookup Time (s)
   JimMischel       57.69-57.69, 57.69     3.027-3.086, 3.052  16.341-16.415, 16.373
  JimMattyDSL       60.88-60.88, 60.88     3.396-3.484, 3.453     0.399-0.400, 0.399
   SimpleTrie 2124.57-2124.57, 2124.57  11.622-11.989, 11.860     0.006-0.006, 0.006
CompessedTrie    166.59-166.59, 166.59     2.813-2.832, 2.823     0.005-0.005, 0.005
  MattyMerrix       62.71-62.73, 62.72     3.230-3.270, 3.251     6.996-7.015, 7.008

如您所见，(非空间优化)尝试所需的内存要高得多。它随着字典的大小增加，对于所有测试的实现都是 O(N)。

正如预期的那样，尝试的查找时间或多或少是恒定的:O(k)，仅取决于搜索项的长度。对于其他实现，时间将根据要搜索的字典的大小而增加。

请注意，可以为这个问题构建更优化的实现，搜索时间将接近 O(k)，并允许更紧凑的存储和减少内存占用。如果您映射到简化的字母表(例如，仅“A”-“Z”)，这也是可以利用的。