Задача о редакционном расстоянии, алгоритм Вагнера-Фишера

Материал из Викиконспекты
Версия от 02:48, 13 января 2012; 192.168.0.2 (обсуждение) (Новая страница: «{{Определение |definition= '''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''д...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.


Свойства

Для расстояния Левенштейна справедливы следующие утверждения:

  • [math]\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |[/math]
  • [math]\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )[/math]
  • [math]\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2[/math]

где [math]\rm{d}(S_1,S_2)[/math] — расстояние Левенштейна между строками [math]S_1[/math] и [math]S_2[/math], а |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).


Формула

Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.

Пусть [math]S_1[/math] и [math]S_2[/math] — две строки (длиной [math]M[/math] и [math]N[/math] соответственно) над некоторым алфавитом, тогда редакционное расстояние [math]\rm{d}(S_1, S_2)[/math] можно подсчитать по следующей рекуррентной формуле:

[math]\ \rm{d}(S_1, S_2) = \rm{D}(M,N)[/math] , где

[math]\rm{D}(i, j) = \left\{\begin{array}{llcl} 0&&;&i = 0,\ j = 0\\ i&&;&j = 0,\ i \gt 0\\ j&&;&i = 0,\ j \gt 0\\ D(i - 1, j - 1)&&;&S_1[i] = S_2[j]\\ \rm{min}(\\ &\rm{D}(i, j - 1) + insertCost\\ &\rm{D}(i - 1, j) + deleteCost&;&j \gt 0,\ i \gt 0,\ S_1[i] \ne S_2[j]\\ &\rm{D}(i - 1, j - 1) + replaceCost\\ ) \end{array}\right. [/math],

[math]\min(a, b, c)[/math] возвращает наименьший из аргументов.

Доказательство

Рассмотрим формулу более подробно. Здесь [math]D(i, j)[/math] — расстояние между префиксами строк: первыми i символами строки [math]S_1[/math] и первыми j символами строки [math]S_2[/math]. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной [math]i[/math], нужно совершить [math]i[/math] операций удаления, а чтобы получить строку длиной [math]j[/math] из пустой, нужно произвести [math]j[/math] операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:

  • Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
  • Две замены разных символов можно менять местами
  • Два стирания или две вставки можно менять местами
  • Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
  • Стирание и вставку разных символов можно менять местами
  • Вставка символа с его последующей заменой — неоптимально (излишняя замена)
  • Вставка символа и замена другого символа меняются местами
  • Замена символа с его последующим стиранием — неоптимально (излишняя замена)
  • Стирание символа и замена другого символа меняются местами

Пускай [math]S_1[/math] кончается на символ «a», [math]S_2[/math] кончается на символ «b». Есть три варианта:

  1. Символ «а», на который кончается [math]S_1[/math], в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые [math]i-1[/math] символов [math]S_1[/math] в [math]S_2[/math] (на что потребовалось [math]D(i-1,\ j)[/math] операций), значит, всего потребовалось [math]D(i-1,\ j)+1[/math] операций
  2. Символ «b», на который кончается [math]S_2[/math], в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили [math]S_1[/math] в первые [math]j-1[/math] символов [math]S_2[/math], после чего добавили «b». Аналогично предыдущему случаю, потребовалось [math]D(i,\ j-1)+1[/math] операций.
  3. Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
    1. Если [math]a=b[/math], мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили [math]D(i-1,\ j-1)[/math] операций.
    2. Если [math]a\ne b[/math], мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить [math]D(i-1,\ j-1)[/math] операций, значит, всего потребуется [math]D(i-1,\ j-1)+1[/math] операций.

Алгоритм Вагнера — Фишера

Для нахождения кратчайшего расстояния необходимо вычислить матрицу 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)

Память

Алгоритм в виде, описанном выше, требует [math]\Theta(M \cdot N)[/math] операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до [math]\Theta(\min(M,N))[/math]. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления 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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_редакционном_расстоянии,_алгоритм_Вагнера-Фишера&oldid=16417»