自动建议特征的加权trie

Question

我有一个trie (后缀树)，我正在使用我的网站中的自动建议功能。

现在我想用较低的权重在文本上方显示最流行(最高权重)的文本。我如何改变我的trie，使建议以加权的顺序出现。

或者我应该只在内存中按权重排序？

Answer 1

您可以在每个节点添加一个count或weight属性，并在使用您的单词构建trie时对其进行更新。每个字符的初始权重都是0，但是如果字符是单词的末尾字符，那么它的初始权重就是1。当您不断添加单词时，您可以调整终端字符的权重。

因此，例如，您可以拥有：

t:0
|  
o:1
|
w:3---e:0
|  \    \
n:2 a:0  l:4
     \
      r:0
       \
        d:2

对于字符串to (出现一次)、tow (出现三次)、towel (出现四次)、town (出现两次)和toward (也出现两次)。

如果您有前缀tow，那么您可以查看非零加权字符串，如tow:3、towel:4、town:2和toward:2。

在此之后，您可以根据权重进行排序。

我还没有在实践中尝试过这个实现；这只是一个想法。