5
правок
Изменения
→Формула: Цитирую: Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления
{{Определение
|id=levenstain_dist
|definition=
'''Расстояние Левенштейна''' (англ. ''Levenshtein distance'') (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}
Для расстояния Левенштейна справедливы следующие утверждения:
* <tex>\rm{d}(S_1,S_2) \ge geqslant | |S_1| - |S_2| |</tex>* <tex>\rm{d}(S_1,S_2) \le 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(\epsilonvarepsilon, b)</tex> — цена вставки символа <tex>b</tex>* <tex>w(a, \epsilonvarepsilon)</tex> — цена удаления символа <tex>a</tex>
Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при* <tex>w(a, a)</tex> = <tex>0</tex>* <tex>w(a, b)</tex> = <tex>1</tex> при <tex>a\ne b</tex>* <tex>w(\epsilonvarepsilon, b)</tex> = <tex>1</tex>* <tex>w(a, \epsilonvarepsilon)</tex> = <tex>1</tex>
<tex>\epsilonvarepsilon</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>\ \rm{d}(S_1, S_2) = \rm{D}(M,N)</tex> , где
<tex>\rm{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]\\\rmmin{min(}(\\&\rmbegin{array}{llcl}&D}(i, j - 1) + insertCost\\&D(i - 1, j) + deleteCost&&\rm{\&D}(i - 1, j- 1) + deleteCostreplaceCost\\\end{array}&;&\ j > 0,\ i > 0,\ S_1[i] \ne S_2[j]\\&\rm{D}(i - 1, j - 1) + replaceCost\\
)
\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>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] + цена вставки символа S2[j]InsertCost '''for''' i = 1 '''to''' M D[i][0] = D[i - 1][0] + цена удаления символа S1[i]DeleteCost '''for''' j = 1 '''to''' N '''if''' S1[i] != S2[j] D[i][j] = min(D[i - 1][j] + цена удаления символа S1[i]DeleteCost, D[i][j - 1] + цена вставки символа S2[j]InsertCost, D[i - 1][j - 1] + цена замены символа S1[i] на символ S2[j]ReplaceCost) '''else''' D[i][j] = D[i - 1][j - 1] '''return''' D[M][N]
</code>
=== Память ===
Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(\min(M,N))</tex>. Для этого надо учестьЗаметим, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после для вычисления <tex>D([i, j)]</tex> не нужны также нам нужно только <tex>D([i-1]</tex>,0)поэтому будем вычислять <tex>D[i]</tex> в <tex>\dotsD[1]</tex> , а <tex>D([i-1,j-1)]</tex>. Поэтому алгоритм можно переписать какв <codetex> '''for''' i = 0 '''to''' M '''for''' j = 0 '''to''' N вычислить D[i0][j] '''if''' i </tex> 0 и j . Осталось только поменять местами <tex> 0 стереть D[i - 1][j - 1] '''return''' </tex> и <tex>D[M, N0]</codetex>.
<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>
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
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
Время выполнения удовлетворяет (с точностью до умножения на константу) условию
: <tex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\le leqslant N'\le leqslant N</tex>,
Докажем:
: <tex>T(M,N) \le leqslant 2MN</tex>
База индукции очевидна
: <tex>T(1,N) = N \le leqslant 2N</tex>Пусть для всех <tex>M' < M</tex> выполнено <tex>T(M',N') \le leqslant 2M'N'</tex>. Тогда учитывая <tex>T(M/2,N') \le leqslant 2(M/2)N'</tex>, <tex>T(M/2,N-N') \le leqslant 2(M/2)(N-N')</tex>, получим:: <tex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N') \leleqslant</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» можно построить следующую таблицу преобразований:
|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
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
