Изменить алгоритм расстояния объяснение

Question

Согласно Википедии, определение рекурсивной формулы, которая вычисляет расстояние Левенштейна между двумя строками а и Ь является следующее:

Я не понимаю, почему мы не» t принять во внимание случаи, в которых мы удаляем a[j], или вставляем b[i]. Кроме того, исправьте меня, если я ошибаюсь, не так ли вставка такая же, как в случае удаления? Я имею в виду, вместо того, чтобы удалять символ из одной строки, мы могли бы вставить тот же символ во вторую строку, и наоборот. Итак, почему бы не объединить операции вставки/удаления в одну операцию со стоимостью, равной min{cost_insert, cost_delete}?

Answer 1

Если затраты на вставки и удаления различаются, вставка одной строки не совпадает с удалением с другой. Даже стоимость замены может отличаться от стоимости вставки + удаления, и разумно держать их отдельно.

Проблема обычно асимметрична: у вас есть список допустимых строк, и вы хотите соответствовать другому, у которого есть ошибки.

Answer 2

Это не сделано, потому что вам не разрешено редактировать обе строки. Определение расстояния редактирования (из википедии):

Серия минимальных весов операций редактирования, которая преобразует a в b.

Так вы специально искали (вес) последовательности операций для выполнения на строке a, чтобы преобразовать его в строку b.

Кроме того, расстояние редактирования не обязательно симметрично. Если ваши расходы на вставки и делеции идентичны расстояние симметрично: d(a,b) = d(b,a)

Рассмотрим пример википедии, но с разными затратами:

• затраты на вставках: w_ins = 1
• стоимость для удалений: w_del = 2
• затраты на замещений: w_sub = 1

расстояние котенка и сидит все еще 3,

kitten -> sitten (substitution k->s, cost 1) 
sitten -> sittin (substitution e->i, cost 1) 
sittin -> sitting (insertion of g, cost 1) 
=> d(kitten, sitting) = 3 

но расстояние сидя и котенка нет:

sitting -> kitting (substitution s->k, cost 1) 
kitting -> kitteng (substitution i->e, cost 1) 
kitteng -> kitten (deletion of g, cost 2) 
=> d(kitten, sitting) = 4 

Вы видите, что d(kitten, sitting) != d(kitten, sitting).

С другой стороны, если вы используете симметричные затраты, так как расстояние Левенштейна (которое является расстоянием редактирования с единичными затратами), вы можете предположить, что имеет место d(a,b) = d(b,a). Тогда вы ничего не выигрываете, рассматривая обратные случаи. То, что вы теряете, - это информация, в которой символ был заменен в строке, что затрудняет извлечение последовательности операций после этого.

Wagner-Fisher algorithm, который вы показываете в своем вопросе, может извлечь это из матрицы DP, возвратив трассу с минимальными затратами. Рассмотрим эти два редактирования матрицы между к и Foo с удельных затрат:

t o  f o o 
f 1 2  t 1 2 3 
o 2 1  o 2 1 2 
o 3 2 

Обратите внимание, что если вы транспонировать матрицу для d(to, foo) вы получите матрицу для d(foo, to). Обратите внимание, что посредством этого вставка в первой матрице становится удалением во второй матрице и наоборот. Так вот эта симметрия, которую вы ищете, подходит снова.

Я надеюсь, что это помогает :)