How to implement a simple auto-complete functionality?

Question

I'd like to implement a simple class (in Java) that would allow me to register and deregister strings, and on the basis of the current set of strings auto-complete a given string. So, the interface would be:

• void add(String)
• void remove(String)
• String complete(String)

What's the best way to do this in terms of algorithms and data-structures?

Answer 1

you should consider to use a PATRICIA trie for the data structure. Search for 'patricia trie' on google and you'll find a lot of information...

Answer 2

The datastructure you are after is called a Ternary Search Tree.

There's a great JavaWorld example at www.javaworld.com/javaworld/jw-02-2001/jw-0216-ternary.html

Answer 3

It would have to be some kind of a List that you can maintain in sorted order. You would also have to write your own search algorithm that would give you the index of the first element in the list that matches your search pattern. Then iterate from that index until the first element that doesn't match and you have your list of possible completions.

I'd look at TreeList from commons-collections. It has fast insert and remove times from the middle of the List which you'll want in order to maintain sorted order. It would probably be fairly easy to write your search function off of the tree that backs that list.

Answer 4

For those who stumble upon this question...

I just posted a server-side autocomplete implementation on Google Code. The project includes a java library that can be integrated into existing applications and a standalone HTTP AJAX autocomplete server.

My hope is that enables people to incorporate efficient autocomplete into their applications. Kick the tires!

Answer 5

I have created a JQuery plugin called Simple AutoComplete, that allows you to add many autocomplete as you want on the same page, and to add filters with extra param, and execute a callback function to bring other params, like the id of the item.

See it at http://www.idealmind.com.br/projetos/simple-autocomplete-jquery-plugin/

Answer 6

Regular expressions.