1
$\begingroup$

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
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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ read this answer may help you. $\endgroup$
    – Grijesh Chauhan
    Jul 26, 2014 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
    Jul 26, 2014 at 19:00

2 Answers 2

Reset to default
2
$\begingroup$

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}$

Improve this answer
$\endgroup$
2
  • $\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
    Jul 27, 2014 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, 2014 at 12:40
-1
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 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, 2014 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
    Jul 27, 2014 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, 2014 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
    Jul 27, 2014 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, 2014 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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