- Being filled
- Read from
- Answer
Edit distance (Levenshtein distance)
How many single-letter changes turn kitten into sitting? Three: replace k by s, replace e by i, and add a g. That number is the edit distance, and it is how spell checkers rank suggestions and how biologists compare genes. Type two words and watch a table find it. Press Play to watch the table fill, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Type two words: the first runs down the side of the table, the second along the top. Each cell holds the fewest edits that turn the letters up to its row into the letters up to its column. At the end the edits are read back from the bottom right cell. New example picks another pair of words. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Type two words: the first runs down the side of the table, the second along the top.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere.
- Watch each cell take the cheapest of its three neighbours, then see the edits read back in orange.
How the table works
A cell holds the fewest edits that turn the first word's letters up to its row into the second word's letters up to its column. The first row counts inserts, building the second word from nothing, and the first column counts deletes. If a cell's two letters are equal, it copies the cell up and to the left: no edit is needed. Otherwise it is one more than the smallest of three neighbours: up and to the left for a replace, above for a delete, and to the left for an insert.
Reading back the edits
The bottom right cell is the edit distance. Starting there, the app finds which neighbour the cell's value came from and steps to it: diagonally for a kept or replaced letter, up for a deleted one, left for an inserted one. Read from the top left, the steps are a shortest list of edits, shown under the table: a plain letter is kept, k→s is a replace, −e a delete and +g an insert.
Frequently asked questions
What is the Levenshtein distance?
Another name for this edit distance: the fewest single-letter inserts, deletes and replacements that turn one string into another. It is named after Vladimir Levenshtein, who described it in 1965.
What is the edit distance between kitten and sitting?
3: replace k by s, replace e by i, and insert g at the end. The table shows that no shorter list of edits exists.
How fast is the edit distance algorithm?
For words of lengths m and n the table has (m + 1)·(n + 1) cells, each filled in one step, so it takes O(m·n) time. If only the distance is needed, two rows of the table are enough.
What other edit distances are there?
The Damerau–Levenshtein distance also counts swapping two neighbouring letters as one edit, which suits typing mistakes. The Hamming distance allows only replacements and works for strings of equal length. The LCS distance allows only inserts and deletes.
Is anything sent anywhere?
No. Everything is worked out in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor