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

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

Расстояние Левенштейна (англ. 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