Algorithm used for auto-suggest feature

Question

Hi,

Which algorithm or data structure is used in auto suggest feature to display list of words. I am thinking that edit-distance will be used to display this, but again frequency or score associated with each word should also be considered. For example, consider the tags option on the ask question page.

Thank you
Bala

Answer 1

You can use a trie:

• every node of the trie has all the children that begins with the value itself, for example: from "in" node you can visit the subtree of all strings starting with "in"
• in your case you have to consider score so you can first gather all children (traversing the tree) and then sort them according to the score or whatever
• if you really want to keep Hamming Distance (edit-distance) you can adapt the trie to build children according to it

Answer 2

Take a look at the links provided in the answers to this stackoverflow question autocomplete algorithms, papers, strategies, etc., you may find what you're looking for there.