How to write a spelling corrector (2016)

Disclaimer:

- Couldn't determine the exact date of that article

- Previous discussion here: https://news.ycombinator.com/item?id=12453535

I really enjoyed the code, it is incredibly clever and idiomatic.

This is a really good introduction to some natural language processing concepts, and the code as other people mentions is very beautiful and easy to read too.

Just as a curiosity: I once did some text correction applied to tweets, using word embeddings (word vectors, word2vec), which are a language model too. In real life contexts, where you don't limit yourself to a dictionary, it's really interesting because word vectors can include many foreignisms and other "incorrect" words that you might want to keep in the text.

The article also mentions edit distances, the distances between words (in this case, the "incorrect" word and its possible corrections). In general, algorithms are based on common errors at the keyboard. Missing or adding a letter, transposing two of them, etc. Algorithms like Damerau-Levenshtein (pretty much the one applied in the article, even though it's not explicitly mentioned I think, and there are many variations) keep it simple by doing this, but it's interesting to notice that you can also fine-tune distances by considering which keys are closer to other keys in the keyboard (it's easier to accidentally type "a" instead of "s" in qwerty than "u"), but when doing more general text correction you can also use phonetic distances or even more sophisticated techniques like finite-state transducers that apply language-specific rules to suggest corrections. (I know the article is only meant as an introduction, but thought someone might find it interesting)

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.

You could make a very simple AutoHotkey script to do this.

I remember having done something similar many years ago in one of my first websites when I was 17. I used the Levenshtein distance [1] to achieve something similar and it worked well.

[1]: https://en.wikipedia.org/wiki/Levenshtein_distance