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

Question

我有一个 trie（后缀树），用于我网站中的自动建议功能。

现在我想在权重较低的文本上方显示最受欢迎（权重最高）的文本。我怎样才能改变我的尝试，以便建议以加权顺序出现。

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

Answer 1

您可以在每个节点上添加一个countorweight属性，并在使用您的单词构建 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。

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

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