Edit Distance in Python

Question

I'm programming a spellcheck program in Python. I have a list of valid words (the dictionary) and I need to output a list of words from this dictionary that have an edit distance of 2 from a given invalid word.

I know I need to start by generating a list with an edit distance of one from the invalid word(and then run that again on all the generated words). I have three methods, inserts(...), deletions(...) and changes(...) that should output a list of words with an edit distance of 1, where inserts outputs all valid words with one more letter than the given word, deletions outputs all valid words with one less letter, and changes outputs all valid words with one different letter.

I've checked a bunch of places but I can't seem to find an algorithm that describes this process. All the ideas I've come up with involve looping through the dictionary list multiple times, which would be extremely time consuming. If anyone could offer some insight, I'd be extremely grateful. Thanks!

Answer 1

You are looking for Norvig's excellent post with source code:

How To Write a Spelling Corrector

http://norvig.com/spell-correct.html

Includes Python source code, theory, and background.

Answer 2

The specific algorithm you describe is called Levenshtein distance. A quick Google throws up several Python libraries and recipes to calculate it.