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:

Edit distance (Levenshtein-Distance) calculation 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

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?

  • 1
    $\begingroup$ read this answer may help you. $\endgroup$ – Grijesh Chauhan Jul 26 '14 at 18:45
  • $\begingroup$ Thank you for the link, but this link is not so relevant for me. My question is why this matrix filled in that way in case of comparison the last «o» from «solo» with the first «o» of «oslo». In this example the letters are the same, so we have to add 0 to minimal value of 3, 2 and 4, which is 2. Thus, 2 + 0 = 2 and not 3. $\endgroup$ – Mike B. Jul 26 '14 at 19:00

You got the recursive definition wrong. It's

$\qquad\displaystyle d_{ij} = \min \begin{cases} d_{i-1, j} + c_\mathrm{del}(b_{i}) \\ d_{i,j-1} + c_\mathrm{ins}(a_{j}) \\ d_{i-1,j-1} + [a_j \neq b_i] \cdot c_\mathrm{sub}(a_{j}, b_{i}) \end{cases}$

where the $c_{\mathrm{op}}$ are fixed costs for the respective operations, all of which are $1$ here. You'll note that for alternatives one and two, insertion and deletion (which correspond to a vertical resp. horizontal step in the matrix), don't care if the current symbol matches any other -- you introduce a gap symbol, anyway!

Following this definition, clearly $2+1$ (insertion of $o$) results in the entry you highlight. Note that the alignment computed (implicitly) up until this point is

$\qquad\begin{array}{cccc} - & o & - & - \\ s & o & l & o \end{array}$

  • $\begingroup$ » You got the recursive definition wrong Could you please point me where exactly in this C-implementation there is a recursive definition? $\endgroup$ – Mike B. Jul 27 '14 at 12:31
  • 4
    $\begingroup$ @Mike That's exactly the problem with looking at (low-level) implementation if you need understanding. Dynamic programming is, at its heart, recursion. You define edit distance the way I re-state in my answer (plus the anchors). The typical implementation is with memoisation plus, for additional efficiency, two nested loop iterating over the memoisation array. The recursive part ends up being implemented exactly in the two lines you cite in your answer; read matrix as function. $\endgroup$ – Raphael Jul 27 '14 at 12:40

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
min(3+0, 2+1, 4+1) = 3

  • 2
    $\begingroup$ Looking at a C implementation is clearly the wrong strategy for garnering understanding resp. the wrong advice to give. $\endgroup$ – Raphael Jul 26 '14 at 23:25
  • $\begingroup$ Could you please clarify what is completely wrong with my advice? According to C-implementation: we have 2 simple loops which fill first column and first row by numbers from 0 to length of strings; one nested loops which pass over all matrix and fill its values according to the line, I marked in my answer above. $\endgroup$ – Mike B. Jul 27 '14 at 12:44
  • 2
    $\begingroup$ That's a result of multiple years of experience with teaching dynamic programming. Imho, your problems directly result from a lack of understanding of DP and the recursive property and instead focusing on a particular implementation (there are others). In my experience, understanding the concepts (first) is the better way; the code follows almost as an afterthought (it's basically the same for most DP algorithms). $\endgroup$ – Raphael Jul 27 '14 at 12:46
  • $\begingroup$ You're right, I don't have much experience with DP and in this example I don't see/feel the real need to use recursion too, in contrast with tree-aimed algos, where there are a lot of repetitive steps which sometimes much easier to solve with recursion. In bottom line, is my answer/explanation wrong or just not optimal to understand? I passed with this explanation over couple of examples and my explanation suits fine with the examples. $\endgroup$ – Mike B. Jul 27 '14 at 13:03
  • 2
    $\begingroup$ Of course your explanation is valid (provided the implementation is correct) -- you have found which part of the code computes the value that confused you. At the risk of repeating my self, my point is that you'll probably understand more by determining why the recurrence (and hence the algorithm) is correct. $\endgroup$ – Raphael Jul 27 '14 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.