What is the best auto-suggest search algorithm for javascript

Say I have an object:

var names = ["john", "jane", "al", "mary", "zan开发者_运维技巧e" ... 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?

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.

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.

Why don't you sort the array using Array.sort()and then perform a binary search on the same ?

Here is a code demonstrating Binary Search in js.

http://www.nczonline.net/blog/2009/09/01/computer-science-in-javascript-binary-search/

Also check the comments on the page, it has a more efficient implementation of the binary search

You can use the Autocomplete of the Jquery UI framework. You'll find the documentation here.
It will avoid you to remake the wheel...

If you like to find Jan in John than have a look at the PHP functions soundex and metaphone. This functions converts a string in a phonetic string. At http://php.net are some examples you could easily convert to JS. You are glad - English has no special characters.

Make a second array with this phonetic equalization and add a pointer to the source element. You need to multisort the second array. https://stackoverflow.com/a/9374631/817152

Translate the search word too.

Then use the interval search algorithm to be fast. https://stackoverflow.com/a/16371484/817152

Don't give up.