First of identify the 2 words to be compared e.g.
The incorrectly typed word is stebl and the word we are looking for is stable.
| * We create a grid and the shortest word goes along the top and the longest word down the left hand-side. | |||||||
| * The starting number is 0 and increments until the last character in both strings | |||||||
| * To start adding number to the grid we start from the top left and work along the row, and then down to the next row and so on. | |||||||
| * The first numbers at the top left in anti-clockwise direction are 1, 0, 1. We use the minimum of those numbers and add 1 unless the letters on the X and Y axis match. If the letters on the X, and Y axis do match the value is 0 unless the letters are offset yet match in which case the offset value is inserted. | |||||||
| * On the last row if there is a matching pair of letters then the 1 of the minimum 3 values from the top left is inserted. | |||||||
| The table below was generated using the Dynarex-Levenshtein gem. | |||||||
| 0 | s | t | e | b | l | ||
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | |
| 2 | s | 1 | 0 | 1 | 2 | 3 | 4 |
| 3 | t | 2 | 1 | 0 | 1 | 2 | 3 |
| 4 | a | 3 | 2 | 1 | 1 | 2 | 3 |
| 5 | b | 4 | 3 | 2 | 2 | 1 | 2 |
| 6 | l | 5 | 4 | 3 | 3 | 2 | 1 |
| 7 | e | 6 | 5 | 4 | 3 | 3 | 2 |
Ths screenshot below was a dry-run edited using a spreadsheet.
To calculate the distance we use the length of the shortest string, and count the number of the columns on the last row starting from the lest using the length value to find the distance. In the above image n is 5 and start from 0 on the last row we count 5 to identify the value 2 as the levenshtein distance.
That means it takes 2 operations (change and add) to modify the string from stebl to stable.