расчет ячейки ячейки levenshtein

Question

Я не понимаю, как вычисляются значения в матрице levenshtein According to this article. Я знаю, как мы достигаем расстояния редактирования 3. Может ли кто-нибудь объяснить в условиях неспециалиста, как мы достигаем каждого значения в каждой ячейке?

Answer 1

Привет Я просто взглянули на ссылку статьи Википедии вы поделились:

То, как матрица построена описана в разделе «Определение». Теперь я просто переведу то, что это значит, и что вам нужно сделать, чтобы построить матрицу самостоятельно:

Просто убедитесь, что нет никакой основной информации: i обозначает номер строки, а j обозначает столбец номер.

Итак, давайте начнем с первой строкой определения матрицы: Это говорит о том, что матрица макс (I, J), если мин (I, J) = 0 условие будет выполнено только для элементов 0-я строка и 0-й столбец. (Тогда min (0, j) равно 0, а min (i, 0) равно 0). Итак, для 0-й строки и 0-го столбца вы вводите значение max (i, j), которое соответствует номеру строки для 0-го столбца и номеру столбца для 0-й строки. До сих пор так хорошо:

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 

Все остальные значения строятся как минимум одного из этих трех значений:

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

Где лева соответствует уже существующему Левенштейн матричных элементов. lev (i, j-1) является просто матричной составляющей слева от той, которую мы хотим определить. lev (i-1, j) - это компонент выше, а lev (i-1, j-1) - это элемент слева и выше. Здесь 1_ (a_i! = B_i) означает, что если буквы в этом пространстве не равны 1, в противном случае 0.

Если мы прыгаем прямо в матричный элемент (1, 1), который соответствует буквам (s, K): Определяем 3 компонента:

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 

Теперь мы возьмем минимум этих трех значений, и мы нашли следующую запись матрицы Левенштейн.

Выполняйте эту оценку для каждой строки элемента или столбца, а результат - полная матрица Левенштейна.

Answer 2

Наведите курсор мыши над каждым значением с точки внизу в этой матрице в wikipedia article и описывает с точки зрения непрофессионала, что каждая ценность означает.

например. используя (x,y) обозначения

• элемент (0,0) сравнивает None с None. (0,0) = 0 поскольку они равны
• элемент (0,1) сравнивает 'k' по None. (0,1) = 1 потому что:
  1. insert 'k' превратить None в 'k' так +1
• элемент (3,2) сравнивает 'kit' с 'si'. (3,2) = 2 из ``
  1. None == None так +0 - Lev = 0 см элемент (0,0)
  2. swap 's','k' так +1 - Lev = 1 см элемент (1,1)
  3. 'i' == 'i' так +0 - Lev = 1 см элемент (2,2)
  4. insert 't' так +1 - Lev = 2 см. элемент (3,2)