weighted trie for autosuggest feature

Question

I have a trie (suffix tree) which I am using for an auto-suggest feature in my website.

Now I want to show the most popular (most highly-weighted) text above text with a lower weight. How can I change my trie so that suggestions come out in weighted order.

Or should I just sort by weight in memory?

Answer 1

You could add a count or weight property at each node and update it as you build the trie using your words. Each character will have an initial weight of 0, but if a character is the terminal character of a word, then it will have an initial weight of 1. As you keep adding words, you can adjust the weights on terminal characters.

So, for example, you could have:

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

For the strings to (appearing once), tow (appearing thrice), towel (appearing four times), town (appearing twice), and toward (also appearing twice).

Then if you had the prefix tow, you can look at non-zero weighted strings such as tow:3, towel:4, town:2, and toward:2.

After that, you can sort based on weight.

I haven't tried out this implementation in practice; this is just an idea.