Изменения

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

Допустим расстояние Левенштейна от <tex>S_1</tex> до <tex>S_2</tex> равно <tex>x</tex>. Значит, нам нужно проделать x операций со строкой <tex>S_1</tex> чтобы получить <tex>S_2</tex>. Значит, у нас есть последовательность из <tex>x</tex> операций. Заменим в этой последовательности <tex>delete(a)</tex> на <tex>insert(a)</tex>, <tex>insert(a)</tex> на <tex>delete(a)</tex>, а <tex>swap(a, b)</tex> на <tex>swap(b, a)</tex> и проделаем все действия, начиная с последнего со строкой <tex>S_2</tex>. Получим строку <tex>S_1</tex> за минимальное количество операций. Следовательно, выполняется аксиома симметрии. <tex>insert(a)</tex> — вставка элемента <tex>a</tex>, <tex>delete(a)</tex> — удаление элемента <tex>a</tex>, <tex>swap(a, b)</tex> — замена <tex>a</tex> на <tex>b</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>S_2</tex>. <tex>\rm{d}(S_1,S_3) = \rm{d}(S_1,S_2) + \rm{d}(S_2,S_3)</tex> только в тех случаях когда <tex>S_2 = S_1</tex> или <tex>S_2 = 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, a)</tex> = <tex>0</tex>* <tex>w(a, b)</tex> = <tex>1</tex> при <tex>a\ne b</tex>* <tex>w(\varepsilon, b)</tex> = <tex>1</tex>* <tex>w(a, \varepsilon)</tex> = <tex>1</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{(}\\\begin{minarray}({llcl}&D}(i, j - 1) + insertCost\\\rm{&D}(i - 1, j) + deleteCost&&\\&D(i - 1, j - 1) + replaceCost\\\end{array}&;&\ j > 0,\ i > 0,\ S_1[i] \ne S_2[j]\\\rm{D}(i - 1, j - 1) + replaceCost)\\ 

</tex>,

'''int''' '''levensteinInstruction'''('''String''' s1, '''String''' s2, '''int[]''' S2InsertCostInsertCost, '''int[]''' S1DeleteCostDeleteCost, '''int[]''' ReplaceCost):

D[0][j] = D[0][j - 1] + S2InsertCost[j] InsertCost <font color=darkgreen>//S2InsertCost[j] - цена вставки символа S2[j]</font color=darkgreen>

D[i][0] = D[i - 1][0] + S1DeleteCost[i] DeleteCost <font color=darkgreen>//S1DeleteCost[i] - цена удаления символа S1[i]</font color=darkgreen>

D[i][j] = min(D[i - 1][j] + S1DeleteCost[i]DeleteCost, D[i][j - 1] + S2InsertCost[j]InsertCost, D[i - 1][j - 1] + ReplaceCost[i][j]) <font color=darkgreen>//ReplaceCost[i][j] - цена замены символа S1[i] на символ S2[j]</font color=darkgreen>

Алгоритм в виде, описанном выше, требует <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>.

'''return''' D[0, ][N]