What is the best autocomplete/suggest algorithm,datastructure [C++/C]

Question

We see Google, Firefox some AJAX pages shows up list of probable items while user types characters.

Can someone give good algorithm,datastructure for implementing autocomplete ?

Answer 1

A trie should be pretty useful for something like this

Edit: And here's an example showing how to use one for just that http://rmandvikar.blogspot.com/2008/10/trie-examples.html

Here's a comparison of 3 different auto-complete implementations (though it's in Java not C++).

* In-Memory Trie
* In-Memory Relational Database
* Java Set

When looking up keys the trie is marginally faster than the Set imlementation while both are a good bit faster than the Db based version.

The setup cost of the Set is a good bit lower than the Trie or DB solution. So I guess you'd have to decide whether you'd be creating these lookups frequently or whether lookup speed is a priority.

As these results are java based your milage will vary with a C++ solution, but at least this shows you some possibilities.

Answer 2

For a simple solution : you generate a 'candidate' with a minimum edit (Levenshtein) distance (1 or 2) then you test the existence of the candidate with a hash container (set will suffice for a simple soltion, then use unordered_set from the tr1 or boost).

Example: You wrote carr and you want car. arr is generated by 1 deletion. Is arr in your unordered_set ? No. crr is generated by 1 deletion. Is crr in your unordered_set ? No. car is generated by 1 deletion. Is car in your unordered_set ? Yes, you win.

Of course there's insertion, deletion, transposition etc...

You see that your algorithm for generating candidates is really where you’re wasting time, especially if you have a very little unordered_set.

Answer 3

For large datasets, a good candidate for the backend would be Ternary search trees. They combine the best of two worlds: the low space overhead of binary search trees and the character-based time efficiency of digital search tries.

See in Dr. Dobbs journal: http://www.ddj.com/windows/184410528

The goal is fast retrieval of a finite resultset as the user types in. Lets first consider that to search "computer science" you can start typing from "computer" or "science" but not "omputer". So, given a phrase, generate the subphrases starting with a word. Now for each of the phrases, feed them into the TST (ternary search tree). Each node in the TST will represent a prefix of a phrase that has been typed so far. We will store the best 10 (say) results for that prefix in that node. If there are many more candidates than the finite amount of results (10 here) for a node, there should be a ranking function to resolve competition between two results.

The tree can be built once every few hours, depending on the dynamism of the data. If the data is real time, then I guess some other algorithm will give a better balance. In this case the absolute requirement is the lightning fast retrieval of results for every keystroke typed which it does very well.

More complications will arise if suggestion of spelling corrections is involved. In that case the edit distance algorithms will have to be considered as well.

For small datasets like list of countries, a simple implementation of Trie will do. If you are going to implement such an autocomplete dropdown in a web application, the autocomplete widget of YUI3 will do everything for you after you provide the data in a list. If you use YUI3 as just the frontend for an autocomplete backed by large data, make the TST based webservice in C++, and then use script node data source of the autocomplete widget to fetch data from the webservice instead of a simple list.

Answer 4

If you want to suggest the most popular completions, a "Suggest Tree" may be a good choice: Suggest Tree