Изменения
→Разные цены операций
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* <tex>w(a, b)</tex> — цена замены символа <tex>a </tex> на символ <tex>b</tex>* <tex>w(ε, b)</tex> — цена вставки символа <tex>b</tex>* <tex>w(a, ε)</tex> — цена удаления символа <tex>a</tex>
Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* <tex>w(a, а) </tex> = <tex>0</tex>* <tex>w(a, b) </tex> = <tex>1 </tex> при a≠b* <tex>w(ε, b) </tex> = <tex>1</tex>* <tex>w(a, ε) </tex> = <tex>1 Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).</tex>
Как частный случай, так и задачу для произвольных <tex>w</tex>, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все <tex>w</tex> неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ <tex>x</tex> на <tex>y</tex>, а потом с <tex>y</tex> на <tex>z</tex> не лучше, чем сразу <tex>x</tex> на <tex>z</tex>).
== Формула ==
