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

Определение:

Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.

Свойства

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

• [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)

Рекурсивный алгоритм

Для того, чтобы обеспечить время [math]\Theta(M \cdot N)[/math] при памяти [math]\Theta(\min(M,N))[/math], определим матрицу [math] E [/math] минимальных расстояний между суффиксами строк, то есть [math] E(i, j) [/math] — расстояние между последними [math] i [/math] символами [math]S_1[/math] и последними [math] j [/math] символами [math]S_2[/math]. Очевидно, матрицу [math] E [/math] можно вычислить аналогично матрице [math] D [/math], и так же быстро.

Теперь опишем алгоритм, считая, что [math]S_2[/math] — кратчайшая из двух строк.

• Если длина одной из строк (или обеих) не больше [math] 1 [/math], задача тривиальна. Если нет, выполним следующие шаги.
• Разделим строку [math]S_1[/math] на две подстроки длиной [math]M/2[/math]. (Если [math]M[/math] нечётно, то длины подстрок будут [math](M-1)/2[/math] и [math](M+1)/2[/math].) Обозначим подстроки [math]S_1^-[/math] и [math]S_1^+[/math].
• Для вычислим последнюю строку матрицы [math] D [/math] для строк [math]S_1^-[/math] и [math]S_2[/math], последнюю строку матрицы [math] E [/math] для строк [math]S_1^+[/math] и [math]S_2[/math].
• Найдём [math] i [/math] такое, что [math]D(|S_1^-|, i) + E(|S_1^+|, N-i)[/math] минимально. Здесь [math] D [/math] и [math] E [/math] — матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение [math]S_2[/math] на две подстроки, минимизирующее сумму расстояния левой половины [math]S_1[/math] до левой части [math]S_2[/math] и расстояния правой половины [math]S_1[/math] до правой части [math]S_2[/math]. Следовательно, левая подстрока [math]S_2[/math] соответствует левой половине [math]S_1[/math], а правая — правой.
• Рекурсивно ищем редакционное предписание, превращающее [math]S_1^-[/math] в левую часть [math]S_2[/math] (то есть в подстроку [math]S_2[1...i][/math])
• Рекурсивно ищем редакционное предписание, превращающее [math]S_1^+[/math] в правую часть [math]S_2[/math] (то есть в подстроку [math]S_2[i+1...N][/math]).
• Объединяем оба редакционных предписания.

В псевдокоде:

levensteinInstruction(String s1, String s2)
   if ( s1.length [math] \le [/math]  1 || s2.length [math] \le [/math] 1 )
       Решаем тривиально, возвращаем редакционное предписание
       
   //Иначе:
   String s1l, s1r, s2l, s2r
   if ( s2.length < s1.length )
       s1l = s1.substring(0, s1.length / 2)   // [math]S_1^-[/math]
       s1r = s1.substring(s1.length / 2, s1.length)   // [math]S_1^+[/math]
       // d, e - массивы
       d = calcD(s1l, s2)   // Вычисляем последнюю строку матрицы [math]D[/math] для [math]S_1^-[/math] и [math]S_2[/math]
       e = calcE(s1r, s2)   // Вычисляем последнюю строку матрицы [math]E[/math] для [math]S_1^+[/math] и [math]S_2[/math]
       k = 0
       for i = 1..s2.length
           if (d[i] + e[s2.length - i] < d[k] + e[s2.length - k])
               k = i
       s2l = s2.substring(0, k)
       s2r = s2.substring(k, s2.length)
   else
       //s1 - меньшая строка
       s2l = s2.substring(0, s2.length / 2)   // [math]S_2^-[/math]
       s2r = s2.substring(s2.length / 2, s2.length)   // [math]S_2^+[/math]
       d = calcD(s2l, s1)   // Вычисляем последнюю строку матрицы [math]D[/math] для [math]S_2^-[/math] и [math]S_1[/math]
       e = calcE(s2r, s1)   // Вычисляем последнюю строку матрицы [math]E[/math] для [math]S_2^+[/math] и [math]S_1[/math]
       k = 0
       for i = 1..s1.length
           if (d[i] + e[s1.length - i] < d[k] + e[s1.length - k])
               k = i
       s1l = s1.substring(0, k)
       s1r = s1.substring(k, s1.length)
   return levensteinInstruction(s1l, s2l) + levensteinInstruction(s1r, s2r)

Время выполнения удовлетворяет (с точностью до умножения на константу) условию

[math]T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\le N'\le N[/math],

Докажем:

[math]T(M,N) \le 2MN[/math]

База индукции очевидна

[math]T(1,N) = N \le 2N[/math]

Пусть для всех [math]M' \lt M[/math] выполнено [math]T(M',N') \le 2M'N'[/math]. Тогда учитывая [math]T(M/2,N') \le 2(M/2)N'[/math], [math]T(M/2,N-N') \le 2(M/2)(N-N')[/math], получим:

[math]T(M,N)=MN+T(M/2,N')+T(M/2,N-N') \le[/math] [math] MN+2(M/2)N'+2(M/2)(N-N')=2MN[/math]

следовательно

[math]T(M,N) = \Theta(M \cdot N)[/math]

Для вычисления последних строк матриц [math] D, ~E [/math]можно использовать два глобальных двумерных массива размера [math]2 \times (min(M, N)+1)[/math].

Т.к. мы вычисляем функцию рекурсивно, требуемый размер стека тоже следует учесть. На стек вызовов потребуется [math]\Theta(log(max(M,N))[/math] памяти, потому общая оценка использования памяти будет [math] \Theta(min(M,N)) [/math]

Редакционное предписание

Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: 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

Реализация рекурсивного алгоритма поиска редакционного предписания на языке Java

Романовский И.В. "Дискретный анализ". Третье издание. Стр. 103 - 105