mozilla/gcli — pull request #60 by pquentin (2012-09-03 09:22:18+00:00)
Title: fuzzy-764856: allow fuzzy matching of commands using Damerau-Levenshtein edit distance

It turns out that the Speller module uses Peter Norvig's spellchecking algorithm where the vocabulary size is expected to be huge (~100K words). It computes all plausible edits and tries to match them with a big dictionary. This is not practical for GCLI, since the dictionary is very small. Instead, the Speller module should compute the Levenshtein distance for every possible command.

I implemented a working proof-of-concept that passes existing unit tests (I tested manually since I don't know how to run the tests). I'm not only using Levenshtein distance but Damerau-Levenshtein distance which includes swaps (eg. distance("help", "hlep") is not two but one).

I overwrote spell.js but this may be a bad idea since the patch is hard to read. I'd be happy to change anything in this patch. This is my first patch for a Mozilla product: if I did anything wrong I'll be happy to fix it.