data-structures - 自动建议功能的加权特里

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。

之后，您可以根据重量排序。

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