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

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

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

Свойства

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

• [math]\rm{d}(S_1,S_2) \geqslant | |S_1| - |S_2| |[/math]
• [math]\rm{d}(S_1,S_2) \leqslant 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], а [math]|S|[/math] — длина строки [math]S[/math].

Разные цены операций

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:

• [math]w(a, b)[/math] — цена замены символа [math]a[/math] на символ [math]b[/math]
• [math]w(\varepsilon, b)[/math] — цена вставки символа [math]b[/math]
• [math]w(a, \varepsilon)[/math] — цена удаления символа [math]a[/math]

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

• [math]w(a, a)[/math] = [math]0[/math]
• [math]w(a, b)[/math] = [math]1[/math] при [math]a\ne b[/math]
• [math]w(\varepsilon, b)[/math] = [math]1[/math]
• [math]w(a, \varepsilon)[/math] = [math]1[/math]

[math]\varepsilon[/math] — пустая последовательность.

Как частный случай, так и задачу для произвольных [math]w[/math], решает алгоритм Вагнера-Фишера, приведённый ниже. Здесь и ниже мы считаем, что все [math]w[/math] неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ [math]x[/math] на [math]y[/math], а потом с [math]y[/math] на [math]z[/math] не лучше, чем сразу [math]x[/math] на [math]z[/math]).

Формула

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

Пусть [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}({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] — расстояние между префиксами строк: первыми [math]i[/math] символами строки [math]S_1[/math] и первыми [math]j[/math] символами строки [math]S_2[/math]. Для нашей динамики должен выполняться принцип оптимальности на префиксе. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной [math]i[/math], нужно совершить [math]i[/math] операций удаления, а чтобы получить строку длиной [math]j[/math] из пустой, нужно произвести [math]j[/math] операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

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

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

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

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

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

Для нахождения кратчайшего расстояния необходимо вычислить матрицу [math]D[/math], используя вышеприведённую формулу. Её можно вычислять как по строкам, так и по столбцам. Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с [math]1[/math]):

int levensteinInstruction(String s1, String s2, int[] S2InsertCost, int[] S1DeleteCost, int[] ReplaceCost):
  D[0][0] = 0
  for j = 1 to N
    D[0][j] = D[0][j - 1] + S2InsertCost[j]                  //S2InsertCost[j] - цена вставки символа S2[j]
  for i = 1 to M
    D[i][0] = D[i - 1][0] + S1DeleteCost[i]                  //S1DeleteCost[i] - цена удаления символа S1[i]
    for j = 1 to N
      if S1[i] != S2[j] 
         D[i][j] = min(D[i - 1][j] + S1DeleteCost[i],        
         D[i][j - 1] + S2InsertCost[j],                      
         D[i - 1][j - 1] + ReplaceCost[i][j])                //ReplaceCost[i][j] - цена замены символа S1[i] на символ S2[j]
      else 
         D[i][j] = D[i - 1][j - 1]
  return D[M][N]

Память

Алгоритм в виде, описанном выше, требует [math]\Theta(M \cdot N)[/math] операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до [math]\Theta(N)[/math]. Заметим, что для вычисления [math]D[i][/math] нам нужно только [math]D[i - 1][/math], поэтому будет вычислять [math]D[i][/math] в [math]D[1][/math], а [math]D[i - 1][/math] в [math]D[0][/math]. Осталось только поменяем местами [math]D[1][/math] и [math]D[0][/math].

int levensteinInstruction(int[] D):
  for i = 0 to M
    for j = 0 to N
      вычислить D[1][j]
    swap(D[0], D[1])
  return D[0, 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]).
• Объединяем оба редакционных предписания.

Псевдокод

int levensteinInstruction(String s1, String s2):
   if  s1.length <=  1 || s2.length <= 1  
       Решаем тривиально, возвращаем редакционное предписание
   else    
       String s1l, s1r, s2l, s2r
       if  s2.length < s1.length 
           s1l = s1.substring(0, s1.length / 2)            // S1- 
           s1r = s1.substring(s1.length / 2, s1.length)    // S1+
                                                           // d, e - массивы
           d = calcD(s1l, s2)                              // Вычисляем последнюю строку матрицы D для S1- и S2
           e = calcE(s1r, s2)                              // Вычисляем последнюю строку матрицы E для S1+ и S2
           k = 0
           for i = 1 to 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)            // S2-
           s2r = s2.substring(s2.length / 2, s2.length)    // S2+
           d = calcD(s2l, s1)                              // Вычисляем последнюю строку матрицы D для S2- и S1
           e = calcE(s2r, s1)                              // Вычисляем последнюю строку матрицы E для S2+ и S1
           k = 0
           for i = 1 to 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\leqslant N'\leqslant N[/math],

Докажем:

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

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

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

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

[math]T(M,N)=MN+T(M/2,N')+T(M/2,N-N') \leqslant[/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]

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

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