You can cheat so your web site seems faster than it is
I couldn't sleep. Took some neo citron for my cold and rewrote the rhymebrain instant algorithm.
When you start typing "ox" into rhymebrain, there is almost 100% chance that you are going to type "oxygen". Likewise for "or" it is "orange". There is a perceived time savings if rhymebrain prefetches the results for what it thinks you are going to type while you are still typing. On the other hand, if you go ahead and enter "oxen" then it will actually take longer to get the results, since the requests are serialized by the browser. Prefetching can waste time.
Previously, I was precalculating the completion which maximized the probability of the word, using some basterdized half-remembered version of bayes law. But I think there is a better approach, by running simulations on existing data.
I have lots of data of what people typed into the search box.
Google-mad-scientist-and-textbook-writer Peter Norvig once wrote a spellchecker in python that works efficiently by brute force. (http://norvig.com/spell-correct.html) I took some inspiration from that and wrote a python program that does, by brute force:
for each possible prefix of all the words, for each word with that prefix, assume the word is completed. calculate time saved if the word is completed * count for each other word with that prefix, subtract time wasted * count
...where count is the number of times the word was entered into Rhymebrain's search box by people. This time of year, there is a large savings for completing "Christ" to "christmas" because people enter it so often.
Now when you use rhymebrain and enter one of the 1800 words in the list, and type slowly enough, then the results will instantly pop onto the screen when you press enter.
Finally getting tired. Almost time to wake up and feed breakfast to kids