包含的有效搜索

Question

我有一个Trie数据结构，它眨眼之间搜索100 000个元素。但是，它只搜索以搜索字符串开头的单词，例如“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--; 
    } 
} 

任何帮助，非常感谢。

Answer 1

https://github.com/gngeorgiev/Trie

这里是特里的回购一旦有人需要它。支持前缀和子字符串搜索。

Answer 2

您可以在所有节点上使用一种索引。

Dictionary<char,List<TrieNode>> nodeIndex;

现在，如果你想搜索例如用于“网络连接”遍历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(); 
} 

也许还有一些遗漏的属性需要实现。