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

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

== Свойства ==

Для расстояния Левенштейна справедливы следующие утверждения:
* <tex>\rm{d}(S_1,S_2) \geqslant | |S_1| - |S_2| |</tex>
* <tex>\rm{d}(S_1,S_2) \leqslant max( |S_1| , |S_2| )</tex>
* <tex>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</tex>
где <tex>\rm{d}(S_1,S_2)</tex> — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а <tex>|S|</tex> — длина строки <tex>S</tex>.

Расстояние Левенштейна является [[Метрическое пространство|метрикой]].
Для того чтобы доказать это достаточно доказать что выполняется неравенство треугольника:
* <tex>\rm{d}(S_1,S_3) \leqslant \rm{d}(S_1,S_2) + \rm{d}(S_2,S_3)</tex>

Пусть <tex>\rm{d}(S_1,S_3) = x</tex>, <tex>\rm{d}(S_1,S_2) = y</tex>, <tex>\rm{d}(S_2,S_3) = z</tex>. <tex>x</tex> — кратчайшее редакционное расстояние от <tex>S_1</tex> до <tex>S_3</tex>, <tex>y</tex> — кратчайшее редакционное расстояние от <tex>S_1</tex> до <tex>S_2</tex>, а <tex>z</tex> — кратчайшее редакционное расстояние от <tex>S_2</tex> до <tex>S_3</tex>. <tex>y + z</tex> — какое-то расстояние от <tex>S_1</tex> до <tex>S_3</tex>. В других случаях <tex>\rm{d}(S_1,S_3) < \rm{d}(S_1,S_2) + \rm{d}(S_2,S_3)</tex>. Следовательно, выполняется неравенство треугольника.

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

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* <tex>w(a, b)</tex> — цена замены символа <tex>a</tex> на символ <tex>b</tex>
* <tex>w(\varepsilon, b)</tex> — цена вставки символа <tex>b</tex>
* <tex>w(a, \varepsilon)</tex> — цена удаления символа <tex>a</tex>

Для решения задачи о редакционном расстоянии необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* <tex>w(a, a) = 0</tex>
* <tex>w(a, b) = 1</tex> при <tex>a\ne b</tex>
* <tex>w(\varepsilon, b) = 1</tex>
* <tex>w(a, \varepsilon) = 1</tex>

<tex>\varepsilon</tex> — пустая последовательность.

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

== Формула ==

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

Пусть <tex>S_1</tex> и <tex>S_2</tex> — две строки (длиной <tex>M</tex> и <tex>N</tex> соответственно) над некоторым алфавитом, тогда редакционное расстояние <tex>\rm{d}(S_1, S_2)</tex> можно подсчитать по следующей рекуррентной формуле:

<tex>\ \rm{d}(S_1, S_2) = \rm{D}(M,N)</tex> , где

<tex>
D(i, j) = \left\{\begin{array}{llcl}
0&;\ i = 0,\ j = 0\\
i * deleteCost&;\ j = 0,\ i > 0\\
j * insertCost&;\ i = 0,\ j > 0\\
D(i - 1, j - 1)&;\ S_1[i] = S_2[j]\\
\min{(}\\
\begin{array}{llcl}
&D(i, j - 1) + insertCost\\
&D(i - 1, j) + deleteCost&&\\
&D(i - 1, j - 1) + replaceCost\\
\end{array}&;\ j > 0,\ i > 0,\ S_1[i] \ne S_2[j]\\
)
\end{array}\right.
</tex>

<tex>\min(a, b, c)</tex> возвращает наименьший из аргументов.

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

Рассмотрим формулу более подробно. Здесь <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми <tex>i</tex> символами строки <tex>S_1</tex> и первыми <tex>j</tex> символами строки <tex>S_2</tex>. Для нашей динамики должен выполняться [[Динамическое программирование|принцип оптимальности на префиксе]]. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления, а чтобы получить строку длиной <tex>j</tex> из пустой, нужно произвести <tex>j</tex> операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
* Две замены одного и того же символа — неоптимально (если мы заменили <tex>x</tex> на <tex>y</tex>, потом <tex>y</tex> на <tex>z</tex>, выгоднее было сразу заменить <tex>x</tex> на <tex>z</tex>).
* Две замены разных символов можно менять местами
* Два стирания или две вставки можно менять местами
* Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
* Стирание и вставку разных символов можно менять местами
* Вставка символа с его последующей заменой — неоптимально (излишняя замена)
* Вставка символа и замена другого символа меняются местами
* Замена символа с его последующим стиранием — неоптимально (излишняя замена)
* Стирание символа и замена другого символа меняются местами

Пускай <tex>S_1</tex> кончается на символ <tex>a</tex>, <tex>S_2</tex> кончается на символ <tex>b</tex>. Есть три варианта:
# Символ «а», на который кончается <tex>S_1</tex>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ <tex>a</tex>, после чего превратили первые <tex>i-1</tex> символов <tex>S_1</tex> в <tex>S_2</tex> (на что потребовалось <tex>D(i-1,\ j)</tex> операций), значит, всего потребовалось <tex>D(i-1,\ j)+1</tex> операций
# Символ <tex>b</tex>, на который кончается <tex>S_2</tex>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <tex>S_1</tex> в первые <tex>j-1</tex> символов <tex>S_2</tex>, после чего добавили <tex>b</tex>. Аналогично предыдущему случаю, потребовалось <tex>D(i,\ j-1)+1</tex> операций.
# Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального <tex>a</tex>, то чтобы сделать последним символом <tex>b</tex>, мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального <tex>a</tex> мы не добавляли. Самого финального <tex>a</tex> мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
## Если <tex>a=b</tex>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <tex>D(i-1,\ j-1)</tex> операций.
## Если <tex>a\ne b</tex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <tex>D(i-1,\ j-1)</tex> операций, значит, всего потребуется <tex>D(i-1,\ j-1)+1</tex> операций.

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

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

Псевдокод ниже решает простой частный случай, когда вставка символа, удаление символа и замена одного символа на другой стоят одинаково для любых символов.

<code>
 '''int''' '''levensteinInstruction'''('''String''' s1, '''String''' s2, '''int''' InsertCost, '''int''' DeleteCost, '''int''' ReplaceCost):
   D[0][0] = 0
   '''fo'''r j = 1 '''to''' N
     D[0][j] = D[0][j - 1] + InsertCost                  
   '''for''' i = 1 '''to''' M
     D[i][0] = D[i - 1][0] + DeleteCost                  
     '''for''' j = 1 '''to''' N
       '''if''' S1[i] != S2[j] 
          D[i][j] = min(D[i - 1][j] + DeleteCost,        
                        D[i][j - 1] + InsertCost,                      
                        D[i - 1][j - 1] + ReplaceCost)                 
       '''else''' 
          D[i][j] = D[i - 1][j - 1]
   '''return''' D[M][N]
</code>

=== Память ===

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

<code>
 '''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]
</code>

== Рекурсивный алгоритм ==
Для того, чтобы обеспечить время <tex>\Theta(M \cdot N)</tex> при памяти <tex>\Theta(\min(M,N))</tex>, определим матрицу <tex> E </tex> минимальных расстояний между ''суффиксами'' строк, то есть <tex> E(i, j) </tex> {{---}} расстояние между последними <tex> i </tex> символами <tex>S_1</tex> и последними <tex> j </tex> символами <tex>S_2</tex>. Очевидно, матрицу <tex> E </tex> можно вычислить аналогично матрице <tex> D </tex>, и так же быстро.

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

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

===Псевдокод===

<code>
 '''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)           <font color=darkgreen> // S1-</font color=darkgreen> 
            s1r = s1.substring(s1.length / 2, s1.length)   <font color=darkgreen> // S1+</font color=darkgreen>
                                                           <font color=darkgreen> // d, e - массивы</font color=darkgreen>
            d = '''calcD'''(s1l, s2)                             <font color=darkgreen> // Вычисляем последнюю строку матрицы D для S1- и S2</font color=darkgreen>
            e = '''calcE'''(s1r, s2)                             <font color=darkgreen> // Вычисляем последнюю строку матрицы E для S1+ и S2</font color=darkgreen>
            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'''
                                                           <font color=darkgreen> // s1 - меньшая строка</font color=darkgreen>
            s2l = s2.substring(0, s2.length / 2)           <font color=darkgreen> // S2-</font color=darkgreen>
            s2r = s2.substring(s2.length / 2, s2.length)   <font color=darkgreen> // S2+</font color=darkgreen>
            d = '''calcD'''(s2l, s1)                             <font color=darkgreen> // Вычисляем последнюю строку матрицы D для S2- и S1</font color=darkgreen>
            e = '''calcE'''(s2r, s1)                             <font color=darkgreen> // Вычисляем последнюю строку матрицы E для S2+ и S1</font color=darkgreen>
            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)

</code>

Время выполнения удовлетворяет (с точностью до умножения на константу) условию
: <tex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\leqslant N'\leqslant N</tex>,
Докажем:
: <tex>T(M,N) \leqslant 2MN</tex>
База индукции очевидна
: <tex>T(1,N) = N \leqslant 2N</tex>
Пусть для всех <tex>M' < M</tex> выполнено <tex>T(M',N') \leqslant 2M'N'</tex>.  
Тогда учитывая <tex>T(M/2,N') \leqslant 2(M/2)N'</tex>,  <tex>T(M/2,N-N') \leqslant 2(M/2)(N-N')</tex>, получим:
: <tex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N') \leqslant</tex> <tex> MN+2(M/2)N'+2(M/2)(N-N')=2MN</tex>
следовательно
: <tex>T(M,N) = \Theta(M \cdot N)</tex>

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

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

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

'''Редакционное предписание''' (англ. ''Editorial prescription'') — последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.

Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
{| class="wikitable"
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
|-
|h ||e ||l ||l ||1 ||2||3 ||
|-
|h ||e||l ||l ||o ||2 ||1 ||4
|}

==См. также==
*[[Задача о расстоянии Дамерау-Левенштейна]]

== Источники информации ==
*[http://en.wikipedia.org/wiki/Levenshtein_distance Wikipedia {{---}} Levenshtein distance]

*[http://pastie.org/5574488 Реализация рекурсивного алгоритма поиска редакционного предписания на языке Java]

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]