Изменения
Нет описания правки
где <tex>\rm{d}(S_1,S_2)</tex> — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а |S| - длина строки S.
== Разные цены операций ==
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* w(a, b) — цена замены символа a на символ b
* w(ε, b) — цена вставки символа b
* w(a, ε) — цена удаления символа a
Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* w(a, а) = 0
* w(a, b) = 1 при a≠b
* w(ε, b) = 1
* w(a, ε) = 1
Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).
## Если <tex>a\ne b</tex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <tex>D(i-1,\ j-1)</tex> операций, значит, всего потребуется <tex>D(i-1,\ j-1)+1</tex> операций.
== Алгоритм Вагнера — Фишера ==
