Trigram inverted search index generator/client in Ruby + JS client

by tokumine

I needed a high speed autocomplete dropdown box in some recent work that couldn’t depend on an external service, and that had to be faster than regex parsing of the search corpus.   We needed an autocomplete that you could embed in a static webpage.

Following on my recent algorithmic explorations, I implemented a trigram inverted search index generator and client in Ruby and JS. You can test out the results in the demo below.

It was pretty good fun (and simple!) to learn about the wonderful world of n-grams, and how darn useful they are. Also, as I basically implemented the algorithm based on the information at wikipedia, it really solidified my stance on software patents.