levenshtein matrix cell calculation

Question

I do not understand how the values in the levenshtein matrix is calculated According to this article. I do know how we arrive at the edit distance of 3. Could someone explain in lay man terms how we arrive at each value in each cell?

Answer 1

Hi I just had a look at the link of the Wikipedia article you shared:

The way the matrix is built is described in "Definition". Now I will just translate that into what it means and what you need to do to built the matrix all by yourself:

Just to be sure that no basic information is missing: i denotes the row number and j denotes the column number.

So lets start with the first definition line of the matrix: It says that the matrix is max(i, j), if min(i,j) = 0 The condition will be fulfilled only for elements of the 0-th row and the 0-th column. (Then min(0, j) is 0 and min(i, 0) is 0). So for the 0-th row and the 0-th column you enter the value of max(i,j), which corresponds to the row number for the 0-th column and the column number for the 0-th row. So far so good:

    k i t t e n
  0 1 2 3 4 5 6
s 1
i 2
t 3
t 4
i 5
n 6
g 7

All the other values are built as the minimum of one of these three values:

lev(i-1, j) + 1
lev(i, j-1) + 1
lev(i-1, j-1) + 1_(a_i != b_i)

Where lev corresponds to the already existing levenshtein matrix elements. The lev(i, j-1) is simply the matrix component to the left of the one, that we want to determine. lev(i-1, j) is the component above and lev(i-1, j-1) is the element left and above. Here, 1_(a_i != b_i) means, that if the letters on this space do not equal 1 is added, otherwise 0.

If we jump right into the matrix element (1, 1), wich corresponds to letters (s, k): We determine the 3 components:

lev(i-1, j) + 1 = 2     [1 + 1 = 2]
lev(i, j-1) + 1 = 2     [1 + 1 = 2]
lev(i-1, j-1) + 1 = 1   [0 + 1 = 1]  + 1 because k is clearly not s

Now, we take the minimum of these three values and we found the next entry of the Levenshtein matrix.

Do this evaluation for each single element row OR columnwise and the result is the full Levenshtein matrix.

Answer 2

Hover your mouse above each value with the dots underneath in that matrix in the wikipedia article and it describes in layman's terms what each value means.

e.g. using (x,y) notation

• element (0,0) compares None to None. (0,0) = 0 because they are equal
• element (0,1) compares 'k' to None. (0,1) = 1 because:
  1. insert 'k' to transform None to 'k' so +1
• element (3,2) compares 'kit' to 'si'. (3,2) = 2 because of ``
  1. None == None so +0 - Lev = 0 see element (0,0)
  2. swap 's','k' so +1 - Lev = 1 see element (1,1)
  3. 'i' == 'i' so +0 - Lev = 1 see element (2,2)
  4. insert 't' so +1 - Lev = 2 see element (3,2)