包含的有效搜索
本文关键字:搜索 有效 包含 | 更新日期: 2023-09-27 18:26:27
我有一个Trie数据结构,它在眨眼之间搜索了100000个元素。然而,它只搜索以搜索字符串开头的单词,例如"Fi"会找到"Final",但找不到"GooFi",我希望它也返回"GooFi"。这就是为什么我在这里问你们,在这种情况下,这是否是正确的结构。我自己实现了它,编写了单元测试,所以到目前为止它是有效的。我需要的是一个如何实现我的目标的提示,我不希望任何人为我写代码,这不是我来这里的原因。总之,这是我的搜索实现:
public List<string> Seach(string word)
{
List<string> results = new List<string>();
this.DoSearch(this.Root, 0, new StringBuilder(word), results);
return results;
}
private void DoSearch(TrieNode currentNode, int currentPositionInWord, StringBuilder word, List<string> results)
{
if (currentPositionInWord >= word.Length)
{
this.DfsForAllWords(currentNode, word, results);
return;
}
char currentChar = word[currentPositionInWord];
bool containsKey = currentNode.Children.ContainsKey(currentChar);
if (containsKey)
{
if (currentPositionInWord == word.Length - 1)
{
results.Add(word.ToString());
}
TrieNode child = currentNode.Children[currentChar];
this.DoSearch(child, ++currentPositionInWord, word, results);
}
}
private void DfsForAllWords(TrieNode currentNode, StringBuilder word, List<string> results)
{
foreach (var node in currentNode.Children.ToArray())
{
word.Append(node.Value.Value);
if (node.Value.IsWord)
{
results.Add(word.ToString());
}
this.DfsForAllWords(node.Value, word, results);
word.Length--;
}
}
非常感谢您的帮助。
您可以在所有节点上使用一种索引。
Dictionary<char,List<TrieNode>> nodeIndex;
现在,如果您想搜索例如"Fi",请在nodeIndex
上迭代并像以前一样搜索。如果您在该迭代中发现了一些内容,则必须在找到的子字符串前面加上指向实际节点的字符串。
public List<string> Seach(string word)
{
List<string> results = new List<string>();
foreach(var node in nodeIndex[word[0]])
{
List<string> nodeResults = new List<string>();
this.DoSearch(node, 0, new StringBuilder(word), nodeResults);
foreach(var nodeResult in nodeResults)
{
var text = string.Format("{0}{1}",node.Parent.Text, nodeResult);
results.Add(node.Parent.Text, nodeResult);
}
}
return results.Distinct().ToList();
}
也许还有一些尚未实现的属性。
https://github.com/gngeorgiev/Trie
如果有人需要的话,这里是Trie的repo。支持前缀和子字符串搜索。