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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Редакционное предписание)
(Добавил рекурсивный алгоритм поиска редакционного предписания с линейным использованием памяти)
Строка 102: Строка 102:
 
  вернуть D(M, N)
 
  вернуть D(M, N)
 
</code>
 
</code>
 +
 +
== Рекурсивный алгоритм ==
 +
Для того, чтобы обеспечить время <math>\Theta(M \cdot N)</math> при памяти <math>\Theta(\min(M,N))</math>, определим матрицу E минимальных расстояний между ''суффиксами'' строк, то есть E(i, j) — расстояние между последними i символами <math>S_1</math> и последними j символами <math>S_2</math>. Очевидно, матрицу E можно вычислить аналогично матрице D, и так же быстро.
 +
 +
Теперь опишем алгоритм, считая, что <math>S_2</math> — кратчайшая из двух строк.
 +
 +
* Если длина одной из строк (или обеих) не больше 1, задача тривиальна. Если нет, выполним следующие шаги.
 +
* Разделим строку <math>S_1</math> на две подстроки длиной <math>M/2</math>. (Если M нечётно, то длины подстрок будут <math>(M-1)/2</math> и <math>(M+1)/2</math>.) Обозначим подстроки <math>S_1^-</math> и <math>S_1^+</math>.
 +
* Для вычислим последнюю строку матрицы D для строк <math>S_1^-</math> и <math>S_2</math>, последнюю строку матрицы E для строк <math>S_1^+</math> и <math>S_2</math>.
 +
* Найдём i такое, что <math>D(|S_1^-|, i) + E(|S_1^+|, N-i)</math> минимально. Здесь D и Е — матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение <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>).
 +
* Объединяем оба редакционных предписания.
 +
 +
В псевдокоде:
 +
<code>
 +
 +
String levensteinInstruction(String s1, String s2){
 +
    if ( s1.length() <= 1 || s2.length() <= 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>
 +
        int [] d = calcD(s1l, s2); //Вычисляем последнюю строку матрицы D для <math>S_1^-</math> и <math>S_2</math>
 +
        int [] e = calcE(s1r, s2); //Вычисляем последнюю строку матрицы E для <math>S_1^+</math> и <math>S_2</math>
 +
        int k = 0;
 +
        for (int i = 1; i <= s2.length(); i++) {
 +
            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>
 +
        int [] d = calcD(s2l, s1); //Вычисляем последнюю строку матрицы D для <math>S_2^-</math> и <math>S_1</math>
 +
        int [] e = calcE(s2r, s1); //Вычисляем последнюю строку матрицы E для <math>S_2^+</math> и <math>S_1</math>
 +
        int k = 0;
 +
        for (int i = 1; i <= s1.length(); i++) {
 +
            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);
 +
}
 +
 +
</code>
 +
 +
Время выполнения удовлетворяет (с точностью до умножения на константу) условию
 +
: <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' < 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>
 +
 +
Для вычисления последних строк матриц D, E можно использовать два глобальных двумерных массива размера <math>2 \times (min(M, N)+1)</math>.
 +
 +
Т.к. мы вычисляем функцию рекурсивно, требуемый размер стека тоже следует учесть. На стек вызовов потребуется <math>\Theta(log(max(M,N))</math> памяти, потому общая оценка использования памяти будет <math> \Theta(min(M,N)) </math>
  
 
== Редакционное предписание ==
 
== Редакционное предписание ==
Строка 118: Строка 188:
 
== Литература ==
 
== Литература ==
 
[http://en.wikipedia.org/wiki/Levenshtein_distance Wikipedia - Levenshtein distance]
 
[http://en.wikipedia.org/wiki/Levenshtein_distance Wikipedia - Levenshtein distance]
 +
 +
[http://pastie.org/5574488 Реализация рекурсивного алгоритма поиска редакционного предписания на языке Java]
  
 
Романовский И.В. "Дискретный анализ". Третье издание. Стр. 103 - 105
 
Романовский И.В. "Дискретный анализ". Третье издание. Стр. 103 - 105

Версия 19:44, 26 декабря 2012

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


Свойства

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

  • [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], определим матрицу E минимальных расстояний между суффиксами строк, то есть E(i, j) — расстояние между последними i символами [math]S_1[/math] и последними j символами [math]S_2[/math]. Очевидно, матрицу E можно вычислить аналогично матрице D, и так же быстро.

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

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

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

String levensteinInstruction(String s1, String s2){
   if ( s1.length() <= 1 || s2.length() <= 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]
       int [] d = calcD(s1l, s2); //Вычисляем последнюю строку матрицы D для [math]S_1^-[/math] и [math]S_2[/math]
       int [] e = calcE(s1r, s2); //Вычисляем последнюю строку матрицы E для [math]S_1^+[/math] и [math]S_2[/math]
       int k = 0;
       for (int i = 1; i <= s2.length(); i++) {
           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]
       int [] d = calcD(s2l, s1); //Вычисляем последнюю строку матрицы D для [math]S_2^-[/math] и [math]S_1[/math]
       int [] e = calcE(s2r, s1); //Вычисляем последнюю строку матрицы E для [math]S_2^+[/math] и [math]S_1[/math]
       int k = 0;
       for (int i = 1; i <= s1.length(); i++) {
           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]

Для вычисления последних строк матриц D, E можно использовать два глобальных двумерных массива размера [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