In this article I explain a dynamic programming approach to solve the edit distance problem. The only operations are deleting, replacing, and adding chars.
Goal of this algorithm is that one given word should be transformed into another given word. The important note is that the edit costs should be minimal.
Example
Transform ‘Bier’ into ‘Berg’. Therefore, the ‘i’ must be removed and the ‘g’ must be added. The edit distance is 2.
Solve it with DP
The table below shows the initial state. The ε indicates the empty word. The column and row of ε can be filled ascending because to obtain the empty word we must delete every char (column) and to get the desired word we must add every char of the desired word (row), respectively. On the left column, we have the original word, and on the top row, we have the word we want to transform the original word into.
| ε | B | e | r | g | |
|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 |
| B | 1 | ||||
| i | 2 | ||||
| e | 3 | ||||
| r | 4 |
Then, we go through the table from left to right and top to bottom and compare the chars. The costs will be inserted based on the following patterns:
Chars are the same:
| 0 | +1 |
|---|---|
| +1 |
Chars are different:
| +1 | +1 |
|---|---|
| +1 |
The minimum value will be inserted in the empty space. The numbers represent the edit cost. So we fill up the table.
| ε | B | e | r | g | |
|---|---|---|---|---|---|
| ε | *0 | 1 | 2 | 3 | 4 |
| B | 1 | *0 | 1 | 2 | 3 |
| i | 2 | *1 | 1 | 2 | 3 |
| e | 3 | 2 | *1 | 2 | 3 |
| r | 4 | 3 | 2 | *1 | *2 |
After that, we backtrack from the last char at the bottom right corner and always choose the minimum value between the left, upper and left upper cell. If the cost between the corner cell and the other two cells are the same, the default choice is the diagonal.
The diagonal means we always replace the char if the cost between both cells is different or keep the char if the cost is the same. Moving left means we add a character, and moving up means we delete a character.
For readability, I marked the path with an asterix *.
Complexity Analysis
Algorithm Structure
Table Construction:
- Rows: $length\ of\ first\ word\ + 1$ or $(m + 1)$
- Columns: $length\ of\ second\ word\ + 1$ or $(n + 1)$
Table Filling:
- Iterate through each cell once
- Perform constant-time operations per cell
Complexity Breakdown
Space Complexity: $O(m \cdot n)$
- Uses a table of size $(m+1) \cdot (n+1)$
Time Complexity: $O(m \cdot n)$
- Fills $(m+1) \cdot (n+1)$ cells
- Constant number of operations per cell
Backtracking: $O(m + n)$
- Traces path from bottom-right to top-left
- Dominated by table filling complexity
Where $m$ and $n$ are the lengths of the two strings being compared.
Use cases
- Spelling mistake correction: Identifying and suggesting corrections for misspelled words.
- Search engine optimization: Improving search results by considering similar words or phrases.
Conclusion
The algorithm is efficient for most practical purposes. But it can be computationally expensive for very long strings. This is the standard dynamic programming approach and generally considered optimal for exact edit distance computation.