Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
Определение: |
Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. |
Содержание[убрать] |
[править] Свойства
Для расстояния Левенштейна справедливы следующие утверждения:
где — расстояние Левенштейна между строками
и
, а |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).
[править] Формула
Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.
Пусть и
— две строки (длиной
и
соответственно) над некоторым алфавитом, тогда редакционное расстояние
можно подсчитать по следующей рекуррентной формуле:
, где
,
возвращает наименьший из аргументов.
[править] Доказательство
Рассмотрим формулу более подробно. Здесь — расстояние между префиксами строк: первыми i символами строки
и первыми j символами строки
.
Очевидно, что редакционное расстояние между двумя пустыми строками
равно нулю. Так же очевидно то, что чтобы получить пустую строку из
строки длиной
, нужно совершить
операций удаления, а чтобы получить строку длиной
из пустой, нужно произвести
операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.
Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
- Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
- Две замены разных символов можно менять местами
- Два стирания или две вставки можно менять местами
- Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
- Стирание и вставку разных символов можно менять местами
- Вставка символа с его последующей заменой — неоптимально (излишняя замена)
- Вставка символа и замена другого символа меняются местами
- Замена символа с его последующим стиранием — неоптимально (излишняя замена)
- Стирание символа и замена другого символа меняются местами
Пускай кончается на символ «a»,
кончается на символ «b». Есть три варианта:
- Символ «а», на который кончается
, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые
символов
в
(на что потребовалось
операций), значит, всего потребовалось
операций
- Символ «b», на который кончается
, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили
в первые
символов
, после чего добавили «b». Аналогично предыдущему случаю, потребовалось
операций.
- Оба предыдущих утверждения неверны. Если мы добавляли символы
справа от финального «a», то чтобы сделать последним символом «b», мы
должны были или в какой-то момент добавить его (но тогда утверждение 2
было бы верно), либо заменить на него один из этих добавленных символов
(что тоже невозможно, потому что добавление символа с его последующей
заменой неоптимально). Значит, символов справа от финального «a» мы не
добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1
неверно. Значит, единственный способ изменения последнего символа —
его замена. Заменять его 2 или больше раз неоптимально. Значит,
- Если
, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили
операций.
- Если
, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить
операций, значит, всего потребуется
операций.
- Если
[править] Алгоритм Вагнера — Фишера
Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя вышеприведённую формулу. Её можно вычислять как по строкам, так и по столбцам.
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с 1):
D(0,0) = 0
для всех j от 1 до N
D(0,j) = D(0,j-1) + цена вставки символа S2[j]
для всех i от 1 до M
D(i,0) = D(i-1,0) + цена удаления символа S1[i]
для всех j от 1 до N
D(i,j) = min(
D(i-1, j) + цена удаления символа S1[i],
D(i, j-1) + цена вставки символа S2[j],
D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]
)
вернуть D(M,N)
[править] Память
Алгоритм в виде, описанном выше, требует операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до
.
Для этого надо учесть, что после вычисления любой строки предыдущая
строка больше не нужна. Более того, после вычисления D(i, j) не нужны
также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
для всех i от 0 до M
для всех j от 0 до N
вычислить D(i, j)
если i>0 и j>0
стереть D(i-1, j-1)
вернуть D(M, N)
[править] Редакционное предписание
Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) — удалить, I (англ. insert) — вставить, R (англ. replace) — заменить, M (англ. match) — совпадение.
Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
M | M | M | M | R | M | R | I |
---|---|---|---|---|---|---|---|
h | e | l | l | 1 | 2 | 3 | |
h | e | l | l | o | 2 | 1 | 4 |
[править] Литература
Wikipedia - Levenshtein distance
Романовский И.В. "Дискретный анализ". Третье издание. Стр. 103 - 105