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 🙂