Algorithm used for auto-suggestion

Question

Which algorithms or data structures are used in auto-suggest features?

It seems that edit-distance will be used, but again a frequency or score associated with each word should also be considered. For example, consider the tags option on SO's Ask Question page.

score 5 · Accepted Answer · answered Mar 10 '10 at 04:07

5

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

answered Mar 10 '10 at 04:07

Jack

128,551
28
227
331

I think TRIE is the best solution for auto suggest. Edit distance is mainly use for spelling correction when one or two letters from the word are missing, deleted or added. I go with Jack answer. – Kapil D Mar 19 '10 at 08:22

score 1 · Answer 2 · edited May 23 '17 at 11:52

1

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.

edited May 23 '17 at 11:52

Community

1
1

answered Mar 11 '10 at 06:34

Bobby

18,009
15
73
88

score 0 · Answer 3 · answered Jul 31 '13 at 03:32

hi raccha , Autosuggestion system work on recursive Algorithm.Google & facebook are implement this algo in his formation . facebook are use graph+recursive type alog. i am give you example for that. if you are type f in facebook search bar then you can saw that facebook is search that how many persons or pages which you like or add. first letter is f then it is showing suggestion's

Algorithm used for auto-suggestion

3 Answers3