加權特里自動建議功能

Question

我有一個特里特（後綴樹），我用於我的網站自動建議功能。

現在我想以較低的權重顯示文本上方最受歡迎（權重最高）的文本。我怎樣才能改變我的建議，使建議以加權的順序出現。

或者我應該按內存中的重量進行排序？

Answer 1

您可以在每個節點添加一個count或weight屬性，並在您使用單詞構建樹時更新它。每個字符的初始權重爲0，但如果一個字符是一個單詞的終端字符，則它的初始權重爲1。隨着您不斷添加單詞，您可以調整終端字符上的權重。

因此，例如，你可以有：

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

對於字符串to（出現一次），tow（三次出現），towel（出現四次），town（出現2次），toward （也出現兩次）。

然後，如果你有前綴tow，你可以看看非零加權字符串如tow:3，towel:4，town:2，並toward:2。

之後，您可以根據體重進行排序。

我還沒有在實踐中嘗試過這個實現;這只是一個想法。