What is the best auto-suggest search algorithm for javascript

Question

Say I have an object:

var names = ["john", "jane", "al", "mary", "zane" ... 1000+ Names]

I want to create an auto-suggest to search these names.

What's the most efficient way of doing this? I've read creating a trie or ternary data structure is best, but I'm not sure how to implement these in js.

Any thoughts?

Answer 1

A trie would be a good solution. Your data set would look something like this:

{"j":
    {"a":
        ["jacob", "jane", ..],
    {"o":
        ["john", "joesph", ..],
    ..
};

You would index character by character as many levels deep as reasonable (so that the innermost arrays have maybe between 20-30 entries.) Then do a simple search on the array stored at the innermost layer.

You can generate this by looping through your collection of names, then check if the particular index entry exists. If so, go down one layer, check if the next characters exists, etc., until you reach the deepest level. Then insert into the array, or start a new array if there isn't one. If a character level doesn't exist while you are adding a new name, then create it. Then you would want to cache the final result instead of regenerating it on every request.

Answer 2

I think that a trie is a natural way to think about doing auto-suggest from a large pool -- what you have to do is a prefix search, and tries excel at this. That said, I'm really not sure how the underlying implementation of arrays works in javascript, so you'd have to benchmark it and see at what point a trie becomes efficient. That is, there is probably some number n below which it makes more sense to do linear search versus using a trie. To top that all off, since each browser uses a different js engine, the efficiency of this will probably differ.

That said, here is a trie implementation in js: http://notdennisbyrne.blogspot.com/2008/12/javascript-trie-implementation.html

If js arrays work the way I think they might (i.e. as fancy hash tables, meaning even doing trienode[10] will end up being a hash table lookup), then another simple option to consider is to store every prefix of a word in an array. e.g. for the name john you'd insert j jo joh john into an array, this would give you constant time lookup but of course use a lot of memory.