Natural Language Processing · free preview
Minimum Edit Distance by Dynamic Programming
Insert, delete, substitute costs; the dynamic programming recurrence with a worked table; backtrace alignments and weighted variants.
1. Minimum Edit Distance by Dynamic Programming
Minimum Edit Distance by Dynamic Programming
2. The dynamic programming recurrence
The dynamic programming recurrence
3. Computing distance and alignment with NumPy
Computing distance and alignment with NumPy
4. Distance by pure insertion
What is the minimum edit distance between "fog" and "fbog" (insert, delete, substitute all cost 1)?
5. Levenshtein distance
Compute the minimum edit distance between "reef" and "crane" (insertions, deletions, substitutions each cost 1).
6. Substitution cost two
Compute the minimum edit distance between "reef" and "crane" when insertions and deletions cost 1 and substitutions cost 2.
7. Asymmetric edit costs
Compute the minimum edit cost between "reef" and "crane" with deletion cost 1, insertion cost 2, and substitution cost 1.5. Round your answer to one decimal place.
8. Bounds on the distance
For arbitrary strings of lengths 4 and 5 (such as "reef" and "crane"), which statement about their minimum edit distance (all costs 1) is always true?
Practice this interactively
Free account · instant grading · spaced review that schedules itself.
Start this course for free