Изменения

'''Расстояние Левенштейна''' (англ. ''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)</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> при a≠b<tex>a\ne b</tex>* <tex>w(ε\varepsilon, b) = 1</tex>* <tex>w(a, ε\varepsilon) = 1</tex>

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

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

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

'''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) ] + цена удаления символа DeleteCost '''for''' j = 1 '''to''' N '''if''' S1[i] для всех != S2[j от 1 до N] D([i,][j) ] = min( D([i-1, ][j) ] + цена удаления символа S1[i]DeleteCost, D([i, ][j-1) ] + цена вставки символа S2[j]InsertCost, D([i-1, ][j-1] + ReplaceCost) + цена замены символа S1 '''else''' D[i][j] = D[i- 1] на символ S2[j- 1] ) вернуть '''return''' D([M,][N)]

Алгоритм в виде, описанном выше, требует <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> такое, j) не нужны также что <tex>D(i|S_1^-1|,0i) … D+ 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>)* Рекурсивно ищем редакционное предписание,j-превращающее <tex>S_1^+</tex> в правую часть <tex>S_2</tex> (то есть в подстроку <tex>S_2[i+1...N]</tex>). Поэтому алгоритм можно переписать как* Объединяем оба редакционных предписания. ===Псевдокод=== 

для всех i от 0 до M'''int''' '''levensteinInstruction'''('''String''' s1, '''String''' s2): '''if''' s1.length <= 1 || s2.length <= 1 Решаем тривиально, возвращаем редакционное предписание '''else''' для всех j от String s1l, s1r, s2l, s2r '''if''' s2.length < s1.length s1l = s1.substring(0 до N, 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, jk) если i 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- и jS1</font color=darkgreen> e = '''calcE'''(s2r, s1) <font color=darkgreen> // Вычисляем последнюю строку матрицы E для S2+ и S1</font color=darkgreen> k = 0 стереть D( '''for''' i = 1 '''to''' s1.length '''if''' d[i] + e[s1.length - i] < d[k] + e[s1.length -1k] k = i s1l = s1.substring(0, k) s1r = s1.substring(k, j-1s1.length) вернуть D '''return''' '''levensteinInstruction'''(s1l, s2l) + '''levensteinInstruction'''(Ms1r, Ns2r) 

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

== Литература См. также==*[[Задача о расстоянии Дамерау-Левенштейна]] == Источники информации ==*[http://en.wikipedia.org/wiki/Levenshtein_distance Wikipedia {{- --}} Levenshtein distance] *[http://pastie.org/5574488 Реализация рекурсивного алгоритма поиска редакционного предписания на языке Java]

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