views:

1565

answers:

7

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?

A: 

Regular expressions.

Jon Homan
A: 

Is utilizing a database a viable option?

Nope, I'm interested in a general algorithm using general data-structures like hash, tree, list, etc.
Kaarel
A: 

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.

John Case
+2  A: 

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

Aidos
+3  A: 

Hello, 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...

pgras
Fantastic suggestion, I'd never heard of PATRICIA trie. Definately one I'm going to do some more research into,
Aidos
Thanks for the answer. I ended up using this Java implementation of radix trees: http://code.google.com/p/radixtree/
Kaarel
A: 

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!

Shilad Sen
A: 

Hi!

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/

Wellington RIbeiro