Data structure for sentence completion suggestions

Question

If a word is typed in Google, it will show a list of words as suggestions in a drop-down list.

For example, if you type what, it will show what is your name, what is your father's name, what is your college name, etc. in 8 words.

What is a suitable data structure, as well as best way to list those suggestions?

What means "suitable" and "best way"? As long as your goals are not specified, this question cannot be answered. — Reinhard Männer, Apr 23 '13 at 12:15
If you're only dealing with prefixes: Possibly [a trie](http://en.wikipedia.org/wiki/Trie). Possibly a database where you do a `LIKE '...%'` and `ORDER BY` for popular ones first. — Bernhard Barker, Apr 23 '13 at 12:17
Something [this](http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm) way? — Suvarna Pattayil, Apr 23 '13 at 12:18
Check http://stackoverflow.com/questions/2901831/algorithm-for-autocomplete — Shubh, Apr 23 '13 at 12:19

score 1 · Answer 1 · answered Apr 23 '13 at 12:39

1

I think the best method is to use a trie where each edge is weighted according to the probability that the next letter correspond to this edge so that first suggestions have higher probabilities.

answered Apr 23 '13 at 12:39

Thomash

6,339
1
30
50

Data structure for sentence completion suggestions

1 Answers1