Measure word similarity with edit distance
Count the edits between two words and use it to correct typos.
- Explain the three edit operations and compute edit distance by hand
- Fill an edit-distance table with dynamic programming
- Build a tiny spelling corrector
You type “teh” and your phone suggests “the”. How does it know? One key ingredient: “teh” is only a couple of small edits away from “the”, and much further from “ten thousand”. The edit distance (or Levenshtein distance) between two words is the fewest single-character insertions, deletions and substitutions that turn one into the other.
Try it
Guess the distance
For each pair, guess the fewest edits before you count carefully - then compare your guess with one cheapest sequence of edits. A good habit: first line up the letters the two words share.
cat to cut
What's the fewest single-letter edits (insert, delete or swap)?
Computing it: a table of smaller problems
Trying every possible sequence of edits would be hopeless. Instead, dynamic programming builds a table where cell (i, j) holds the distance between the first i letters of one word and the first j letters of the other. Each cell is the cheapest of three moves:
- delete a letter: the cell above + 1
- insert a letter: the cell to the left + 1
- substitute (or keep, if the letters match): the cell diagonally up-left + 1 (or + 0)
Here is the table for “cat” → “cut”. The answer is in the bottom-right corner:
| ε | c | u | t | |
|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 |
| c | 1 | 0 | 1 | 2 |
| a | 2 | 1 | 1 | 2 |
| t | 3 | 2 | 2 | 1 |
(ε is the empty string: turning nothing into “cu” takes two insertions.)
1def edit_distance(source, target):
2 previous = list(range(len(target) + 1))
3 for row, source_letter in enumerate(source, start=1):
4 current = [row]
5 for column, target_letter in enumerate(target, start=1):
6 substitution = previous[column - 1] + (source_letter != target_letter)
7 current.append(min(previous[column] + 1, current[column - 1] + 1, substitution))
8 previous = current
9 return previous[-1]
10
11print(edit_distance("kitten", "sitting"))3
A spelling corrector
A simple corrector compares the typed word to every word in a dictionary and suggests the closest one. Real correctors (like the one Peter Norvig famously wrote in about 20 lines) also prefer more common words: “teh” is 2 edits from both “the” and “tech”, but “the” is far more likely.
Key takeaways
Edit distance counts the fewest insertions, deletions and substitutions between two strings.
Dynamic programming fills a table of smaller answers so each cell takes constant work.
Spelling correction = candidates that are few edits away + a preference for common words.
Lesson quiz
6 questions · pass with 5 correct · up to 50 XP
Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.
Practice: apply NLP with Python
Try each text-processing idea in Python, run it against sample inputs, and use the results to see where the method works or falls short.
Compute the edit distance
Read two words on separate lines and print their Levenshtein edit distance (insert, delete and substitute each cost 1).
- kitten → sitting
- One substitution
- Identical words
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Suggest a correction
The first line is a misspelled word. The second line is a space-separated dictionary. Print the dictionary word with the smallest edit distance to the misspelled word; if several tie, print the one that comes first alphabetically.
- Swapped letters
- Missing letter
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Questions about this lesson
Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.
Loading posts…