Algorithm for fast substring search in a contact database

Question

I have a database with approximately 1 million names and addresses. This database should be exposed for a "Google Suggest"-like instant search on a web-page. I'm looking for an efficient algorithm/data structure which can help me achieve this.

What makes this more difficult than just using a Trie or a Generalized Suffix Tree, is that it must support queries with some of the names left out. For instance when a user types "Elvis Pr", "Elvis Aaron Presley" should be suggested.

I'm hoping to get the whole index in memory (I have about 4GB of RAM to be used for this).

The application is written in Java, so links to Java-based libraries are considered extra helpful. I've been looking a bit at Lucene and MG4J, but I haven't figured out which type of indexing I could use for my problem.

Answer 1

Perhaps what you actually want is a search in which each word typed by the user must appear as a prefix of some word in a contact. This is a bit easier and faster than general substring search.

1. Build a single sorted array of all words belonging to any contact, and store a "contact ID" field alongside each word (e.g. [Aaron/1, Aleksander/2, Blomskøld/2, Elvis/1, Presley/1]).
2. Separately for each word typed by the user, use binary search to find the range of names starting with that word (this will necessarily be a contiguous range of indices within the array). Since the user is usually adjusting only one word with each keystroke, you will only need to recompute one of these ranges with each keystroke -- and in fact even this recomputation step can be done more efficiently in the common case of typing an additional letter, since this can only narrow the range of matching words.
3. Finally, intersect the sets of contact IDs to produce the list of possibilities. To show the possibilities, you will need a second array, indexed by contact ID and containing the full names.