Расстояние Левенштейна, отдельное отслеживание вставок/удалений/замен

В статье Википедии о расстоянии Левенштейна говорится: возможные модификации, что «[мы] можем хранить количество вставок, удалений и замен отдельно».

Как это делается? Я создал реализацию матричного решения динамического программирования, описанного в статье, где каждая ячейка матрицы имеет отдельное значение для удалений/вставок/замен, но, хоть убей, я не могу понять логику.

Интуитивно кажется, что если мне нужно выполнить удаление и вставку на одном шаге, то вместо этого они должны стать заменой.

Чтобы полностью прояснить, что я хочу, вот образец матрицы для исходной строки «mat» и целевой строки «catch». Я ожидаю, что для этого потребуется одна замена (т. е. замена «m» на «c») и две вставки (т. е. добавление «ch»). Каждая ячейка — это «удаления/вставки/замены».

           C     A     T     C     H
  +-----+-----+-----+-----+-----+-----+
  |D/I/S|0/1/0|0/2/0|0/3/0|0/4/0|0/5/0|
  +-----+-----+-----+-----+-----+-----+
M |1/0/0|0/0/1|0/1/1|0/2/1|0/3/1|0/4/1|
  +-----+-----+-----+-----+-----+-----+
A |2/0/0|1/0/1|0/0/1|0/1/1|0/2/1|0/3/1|
  +-----+-----+-----+-----+-----+-----+
T |3/0/0|2/0/1|1/0/1|0/0/1|0/1/1|0/2/1|
  +-----+-----+-----+-----+-----+-----+

Кто-нибудь разрабатывал этот алгоритм?


algorithm levenshtein-distance
person ulatekh    schedule 03.10.2013    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Для целевой ячейки x нам нужно найти минимум:

this + substitution | this + deletion
--------------------+----------------
this + insertion    |       x

Сверху слева — это когда мы еще не обработали ни одно из значений, поэтому мы должны обрабатывать оба одновременно, таким образом, это замена.

Слева — когда мы еще не обработали целевое значение, так что это вставка.

Сверху — это когда мы еще не обработали исходное значение, так что это удаление.

Чтобы хранить значения отдельно, вам понадобится 3D-массив:

array[targetSize+1][inputSize+1][3]

Затем для каждой из 3 предыдущих ячеек вы добавляете 1 замену, удаление или вставку (как указано выше), затем вычисляете общую стоимость на основе количества замен, удалений и вставок и находите минимум 3 затрат. Затем скопируйте значения из ячейки, дающей минимум, в текущую ячейку (с добавлением 1 операции).

Таким образом, для:

0/1/0|0/2/0
-----+-----
0/0/1|  x

Предположим, что стоимость каждой операции равна 1.

Рассчитываем:
0/1/0 + 1 замена = 0/1/1, стоимость = 2
0/0/1 + 1 вставка = 0/1/1, стоимость = 2
0/2/0 + 1 удаление = 1/2/0, стоимость = 3

Затем мы выбираем любую из двух стоимостей и помещаем 0/1/1 в новую ячейку.

Надеюсь, это поможет.

person Bernhard Barker    schedule 03.10.2013
comment
Вот именно - я больше не нахожу минимальное из этих трех значений. Вместо этого я хочу найти и сохранить эти три значения отдельно. - person ulatekh; 04.10.2013
comment
@ulatekh Добавил еще несколько деталей. - person Bernhard Barker; 04.10.2013
comment
Теперь я понимаю, что вы имеете в виду! Действительно, это решение. Спасибо! Но выше, когда вы говорите о правом верхнем углу, я думаю, вы имеете в виду верхний левый. - person ulatekh; 04.10.2013
comment
@ulatekh Действительно, исправлено. - person Bernhard Barker; 04.10.2013