Problem Detail: I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we’ll get the result matrix: 
What I don’t understand is: In case of comparison the last «o» from «solo» with the first «o» of «oslo» will see the submatrix: 3 2
4 3 As far as I understand, in order to calculate the bottom right value, which is equal in this example to 3 of this submatrix, we’ll get the min(3, 2, 4) + (0 if the letters are the same, otherwise 1). So, why in this example the bottom right value is equal to 3 and not to 2?
What I don’t understand is: In case of comparison the last «o» from «solo» with the first «o» of «oslo» will see the submatrix: 3 24 3 As far as I understand, in order to calculate the bottom right value, which is equal in this example to 3 of this submatrix, we’ll get the min(3, 2, 4) + (0 if the letters are the same, otherwise 1). So, why in this example the bottom right value is equal to 3 and not to 2?
Asked By : Mike B.
Answered By : Mike B.
If we look deeply at algorithm implementation in C: http://en.m.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C we’ll see the main string which fills the matrix:
matrix[x][y] = MIN3(matrix[x-1][y] + 1, matrix[x][y-1] + 1, matrix[x-1][y-1] + (s1[y-1] == s2[x-1] ? 0 : 1));
as we can see, the value of cells with indexes matrix[x-1][y] (upper cell) and matrix[x][y-1] (left cell) in automatically increased, the upper-left cell (by diagonal) with index matrix[x-1][y-1] is increased by 1 only if the letters are different and only after that we’ll take a minimum from these 3 values. In other words: 3 2
4 min(3+0, 2+1, 4+1) = 3
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28734
