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

c++ c algorithm search autocomplete
subbul picture subbul · Nov 23, 2009 · Viewed 51.3k times · Source

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

Can someone give a good algorithm, data structure for implementing autocomplete?

Answer

Glen picture Glen · Nov 23, 2009

A trie is a data structure that can be used to quickly find words that match a prefix.

Edit: Here's an example showing how to use one to implement autocomplete 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 implementation. Both the trie and the set are a good bit faster than the relational database solution.

The setup cost of the Set is lower than the Trie or DB solution. You'd have to decide whether you'd be constructing new "wordsets" frequently or whether lookup speed is the higher priority.

These results are in Java, your mileage may vary with a C++ solution.

Related questions

Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More
Fast ceiling of an integer division in C / C++

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3. The …

Read More
Data Compression Algorithms

I was wondering if anyone has a list of data compression algorithms. I know basically nothing about data compression and I was hoping to learn more about different algorithms and see which ones are the newest and have yet to …

Read More