Задача о редакционном расстоянии

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

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

Свойства

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

• [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\\ \rm{min}(\\ &\rm{D}(i, j - 1) + w1\\ &\rm{D}(i - 1, j) + w2&;&j \gt 0,\ i \gt 0\\ &\rm{D}(i - 1, j - 1) + \rm{m}(S_1[i], S_2[j])\\ ) \end{array}\right. [/math],

где [math]\rm{m}(a,b)[/math] равна нулю, если [math]a = b[/math] и цену операции замены в противном случае; [math]\min(a, b, c)[/math] возвращает наименьший из аргументов. w1 — цена вставки символа b, w2 — цена удаления символа a.

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

Рассмотрим формулу более подробно. Здесь [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

Код получения редакционного предписания

Функция distance принимает две строки s1, s2 и возвращает последовательность действий, необходимых для получения из первой строки второй кратчайшим образом.

a - цена вставки символа, b - цена удаления символа, c - цена замены символа

function distance(s1, s2: longint): string;
begin
  n = length(s1);
  m = length(s2);
  for i = 1 to n do d[0, i] = i;
  for i = 1 to m do d[i, 0] = i;
  for i = 1 to n do for j = 1 to m do
    if s1[i] == s2[j] then
    begin
      d[i, j] = d[i - 1, j - 1];
      p[i, j].x = i - 1;
      p[i, j].y = j - 1;
    end else 
    begin 
      if (d[i - 1, j] + a <= d[i, j - 1] + b) and (d[i - 1, j] + a <= d[i - 1, j - 1] + c) then
      begin
        d[i, j] = d[i - 1, j] +a;
        p[i, j].x = i - 1;
        p[i, j].y = j;
      end;
      if (d[i, j - 1] + b <= d[i - 1, j] + a)and (d[i, j - 1] + b <= d[i - 1, j - 1] + c) then
      begin
        d[i, j] = d[i, j - 1] +b;
        p[i, j].x = i;
        p[i, j].y = j - 1;
       end;
      if (d[i - 1, j - 1] + c <= d[i, j - 1] + b) and (d[i - 1, j - 1]  + c <= d[i - 1, j] + a) then
     begin
        d[i, j] = d[i - 1, j - 1] + c;
        p[i, j].x = i - 1;
        p[i, j].y = j - 1;
      end;
    end;
  x = n;
  y = m;
  while (x > 0) and (y > 0) do
  begin
   if p[x, y].x - x == 0 then s = 'D' + s else
   if p[x, y].y - y == 0 then s = 'I' + s else
   if s1[x] == s2[y] then s = 'M' + s else s = 'R' + s;
   x = p[x, y].x;
   y = p[x, y].y;
  end;
  distance = s;
end;

Литература

Wikipedia - Levenshtein distance

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