Concept of the day1 / 3
Edit distance
The conceptHow a spell checker knows 'recieve' is close to 'receive'
Edit distance is the smallest number of single-letter edits that turn one word into another. Each insertion, deletion or substitution of a letter counts as 1.
The classic example: 'kitten' becomes 'sitting' in 3 edits. Swap k for s, swap e for i, then add g at the end. No shorter route exists, so the distance is 3.
What it’s forWorks out the edit distance between the first i letters of word a and the first j letters of word b.
d[i][j] = min(d[i−1][j] + 1, d[i][j−1] + 1, d[i−1][j−1] + c)
- d[i][j]
- edits needed to turn the first i letters of a into the first j letters of b
- +1 terms
- cost of deleting a letter from a, or inserting a letter from b
- c
- 0 if letter i of a equals letter j of b, otherwise 1 (a substitution)
What it givesThe final cell, d[length of a][length of b], is the edit distance between the two words.
- kitten → sitten: substitute k with s (1)
- sitten → sittin: substitute e with i (2)
- sittin → sitting: insert g (3)