Mat*_*rix 2 c# language-agnostic string algorithm optimization
假设我有一个 100,000 个单词的列表。我想找出给定的字符串是否与该列表中的任何单词匹配，并且我想以最快的方式进行。另外我想知道是否有任何其他单词出现在列表中，这些单词是从该字符串中的第一个字符开始形成的。
例如：
假设你有字符串“icedtgg”
"i" "ic" "ice" "iced" "icedt" "icedtg" "icedtgg"
我正在尝试提出一个最佳比较算法，它告诉我以下单词是否在我的列表中。
到目前为止，我的 100,000 个单词列表存储在一个
Dicitonary<char, List<string>> WordList;
wherechar是单词的第一个字符，theList<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”将是列表中的第一个单词。这些列表事先按字母顺序排序，以免减慢匹配速度。
有任何想法吗？
*不，这不是硬件分配，我是一名专业软件架构师，试图为乐趣/爱好/游戏开发找到最佳匹配算法。
我决定添加这个答案并不是因为它是您问题的最佳解决方案，而是为了说明两种可能的解决方案，它们相对简单，并且在某种程度上符合您似乎正在遵循的方法。
下面的（未优化的）示例提供了一个极其简单的前缀树实现，它对每个消耗的字符使用一个节点。
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
更新：选择正确的数据结构很重要
我认为更新可以提供一些价值来说明选择适合问题的数据结构的重要性以及涉及哪些类型的权衡。因此，我创建了一个小型基准测试应用程序，用于测试迄今为止为该问题提供的答案中的策略，以及基准参考实现。
完整的基准代码可以在这个 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”），这也是可以利用的。