Compare two strings and get the edit distance — the fewest single-character insertions, deletions, and substitutions that turn one into the other. Shows the actual edits it picked, and the dynamic programming matrix with the cheapest path traced through it.
Edit Distance
3
3 edits turn A into B
Similarity (1 − distance ÷ length of the longer string)
Substitutions
2
changed in place
Insertions
1
added to reach B
Deletions
0
dropped from A
Hamming
—
needs equal lengths
The Edits (A on top, B below, read left to right)
Dynamic Programming Matrix (each cell is the distance between the prefixes; the shaded run is the cheapest path)
| ε | s | i | t | t | i | n | g | |
|---|---|---|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| k | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| i | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| t | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| t | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| e | 5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
| n | 6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |
Bottom-right corner = the answer. 4 of 7 positions needed no edit at all.
marduc812
© 202620260824_1c411cc