Изменения
→Разные цены операций
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* <tex>w(a, b)</tex> — цена замены символа <tex>a</tex> на символ <tex>b</tex>
* <tex>w(ε\epsilon, b)</tex> — цена вставки символа <tex>b</tex>* <tex>w(a, ε\epsilon)</tex> — цена удаления символа <tex>a</tex>
Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* <tex>w(a, аa)</tex> = <tex>0</tex>
* <tex>w(a, b)</tex> = <tex>1</tex> при <tex>a\ne b</tex>
* <tex>w(ε\epsilon, b)</tex> = <tex>1</tex>* <tex>w(a, ε\epsilon)</tex> = <tex>1</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>).
