搜索三数据结构

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

未经测试，但应该给你一个想法。如果用户键入的速度非常快，并且想要避免频繁计算，则可以使用一些限制逻辑推迟搜索算法。