Изменения

'''Расстояние Левенштейна''' (англ. ''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(\min(M,N))</tex>. Для этого надо учестьЗаметим, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после для вычисления <tex>D([i, j) не нужны также ]</tex> нам нужно только <tex>D([i-1]</tex>,0) … поэтому будем вычислять <tex>D([i-]</tex> в <tex>D[1]</tex>,jа <tex>D[i -1)]</tex> в <tex>D[0]</tex>. Осталось только поменять местами <tex>D[1]</tex> и <tex>D[0]</tex>. Поэтому алгоритм можно переписать как 

для всех '''int''' '''levensteinInstruction'''('''int[]''' D): '''for''' i от = 0 до '''to''' M для всех '''for''' j от = 0 до '''to''' N вычислить D(i, [1][j)] если i>swap(D[0 и j>0 стереть ], D(i-1, j-[1]) вернуть '''return''' D(M, [0][N)]

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

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

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

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

  String '''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> //<math>S_1^S1-</mathfont color=darkgreen> s1r = s1.substring(s1.length() / 2, s1.length()); <font color=darkgreen> //S1+</font color=darkgreen> <mathfont color=darkgreen>S_1^+// d, e - массивы</mathfont color=darkgreen> int [] d = '''calcD'''(s1l, s2); <font color=darkgreen> //Вычисляем последнюю строку матрицы D для <math>S_1^S1-</math> и <math>S_2S2</mathfont color=darkgreen> int [] e = '''calcE'''(s1r, s2); <font color=darkgreen> //Вычисляем последнюю строку матрицы E для <math>S_1^S1+</math> и <math>S_2S2</mathfont color=darkgreen> int k = 0; '''for (int ''' i = 1; i <= '''to''' 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 {''' <font color=darkgreen> //s1 - меньшая строка</font color=darkgreen> s2l = s2.substring(0, s2.length() / 2); <font color=darkgreen> //<math>S_2^S2-</mathfont color=darkgreen> s2r = s2.substring(s2.length() / 2, s2.length()); <font color=darkgreen> //<math>S_2^S2+</mathfont color=darkgreen> int [] d = '''calcD'''(s2l, s1); <font color=darkgreen> //Вычисляем последнюю строку матрицы D для <math>S_2^S2-</math> и <math>S_1S1</mathfont color=darkgreen> int [] e = '''calcE'''(s2r, s1); <font color=darkgreen> //Вычисляем последнюю строку матрицы E для <math>S_2^S2+</math> и <math>S_1S1</mathfont color=darkgreen> int k = 0; '''for (int ''' i = 1; i <= '''to''' 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); }

: <mathtex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\le leqslant N'\le leqslant N</mathtex>,

: <mathtex>T(M,N) \le leqslant 2MN</mathtex>

: <mathtex>T(1,N) = N \le leqslant 2N</mathtex>Пусть для всех <mathtex>M' < M</mathtex> выполнено <mathtex>T(M',N') \le leqslant 2M'N'</mathtex>. Тогда учитывая <mathtex>T(M/2,N') \le leqslant 2(M/2)N'</mathtex>, <mathtex>T(M/2,N-N') \le leqslant 2(M/2)(N-N')</mathtex>, получим:: <mathtex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N') \leleqslant</mathtex> <mathtex> MN+2(M/2)N'+2(M/2)(N-N')=2MN</mathtex>

: <mathtex>T(M,N) = \Theta(M \cdot N)</mathtex>

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

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

''Редакционным предписанием'Редакционное предписание' называется '' (англ. ''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