搜索三數據結構

Question

我有大約150,000個字加載到一個Trie數據結構，並希望搜索。每次我在searchBox中輸入一個新字符時，都會作爲NextMatch的參數傳遞。

例如：如果我輸入'Appl'，則將返回以'Appl'開頭的所有單詞。如果我輸入字符'e'，則同樣顯示以'Apple'開頭的所有單詞。

問題是，當我刪除字符'e'時，'l'將作爲NextMatch參數傳遞給Matcher方法，並創建類似'Appll'的東西，但我想要以'Appl'開頭的那些單詞的列表。

這裏是我的代碼狙擊

private void searchBox_TextChanged(object sender, TextChangedEventArgs e) 
{ 
    listboxWords1.Items.Clear(); 

    if (searchBox.Text.Length > 0) 
    { 
     trie.Matcher.NextMatch(searchBox.Text.Trim().Last()); 
     foundWords = trie.Matcher.GetPrefixMatches(); //foundWords is List<string> 
     for (int i = foundWords.Count - 1; i > 0 ; i--) 
     { 
      listboxWords1.Items.Add(foundWords[i]); 
     } 

     foundWords = null; 
     isFoundExact = trie.Matcher.IsExactMatch(); 
     if (isFoundExact) 
      listboxWords1.Items.Add(trie.Matcher.GetExactMatch()); 
    } 
    else 
    { 
     foundWords = null; 
     trie.Matcher.ResetMatch(); 

    } 
} 

特里數據結構的實現，可以發現here

Answer 1

看來API是單向的，但是這很好，我們可以重新每次從一開始就計算匹配。

Trie的計算複雜度並不是那麼大，所以你不會感覺到任何性能問題。

private void searchBox_TextChanged(object sender, TextChangedEventArgs e) 
{ 
    listboxWords1.Items.Clear(); 

    if (searchBox.Text.Length > 0) 
    { 
     trie.Matcher.ResetMatch();//Reset the match 

     foreach (char c in searchBox.Text) 
      trie.Matcher.NextMatch(c); //Start the match from beginning 

     foundWords = trie.Matcher.GetPrefixMatches(); //foundWords is List<string> 
     for (int i = foundWords.Count - 1; i > 0 ; i--) 
     { 
      listboxWords1.Items.Add(foundWords[i]); 
     } 

     foundWords = null; 
     isFoundExact = trie.Matcher.IsExactMatch(); 
     if (isFoundExact) 
      listboxWords1.Items.Add(trie.Matcher.GetExactMatch()); 
    } 
    else 
    { 
     foundWords = null; 
     trie.Matcher.ResetMatch();  
    } 
} 

未經測試，但應該給你一個想法。如果用戶鍵入的速度非常快，並且想要避免頻繁計算，則可以使用一些限制邏輯推遲搜索算法。