包含的有效搜索

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(); 
} 

也許還有一些遺漏的屬性需要實現。