Javascript auto-complete

I’ve seen a number of questions on Stack Overflow wondering how to implement auto-complete in Javascript with large dictionaries. There are bad ideas (using jquery’s autocomplete with an enormous list of words embedded in the page), and there are people who have the right idea (do this in a web service), but no ready-to-use solutions. So I built one.

My proof of concet (American wordlist, 99K words) is currently up at http://enno.kn-bremen.de/prefix.html. That’s my Raspberry Pi doing the heavy lifting so your browser doesn’t have to.

The basic architecture here is a small bit of jQuery code that calls out to a web service written in C with the FastCGI library. The C program uses an implementation of DJB’s critbit tries for storage of the dictionary, which is fast enough to make response times almost instantaneous, and because it’s a long-running process, there is no startup cost for reading the dictionary from disk for each request.

If you’re curious about the code, the meat of the service lives in https://github.com/badgerman/fastcgi/blob/master/complete.c and the trie is an older project of mine at https://github.com/badgerman/critbit.

Feel free to use the code for whatever you want, and if you implement this in your own project, I’d appreciate hearing about what you made 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s