While doing a bunch of research on exactly this problem space recently for a project, I stumbled onto this improvement on the Norvig corrector idea http://blog.faroo.com/2012/06/07/improved-edit-distance-base... that's one of those things that's so deceptively simple you kick yourself for not thinking of it: it turns out you can model the same "generate all the variations" effect but generating only the deletes, rather than also the insertions and substitutions, if you symmetrically apply the same transformation to the lookup side. So if your dictionary contains "cat" and you want to match queries for "cast," rather than adding "cast" to the corpus, you drop the s (and every other single letter) on the lookup side instead, and still match. Turns out it's much faster and, requires a much smaller index, and as a bonus, doesn't tie you to a specific alphabet like Norvig's approach does.