5
правок
Изменения
→Формула: Цитирую: Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления
{{Определение
|id=levenstain_dist
|definition=
'''Расстояние Левенштейна''' (англ. ''Levenshtein distance'') (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}
* <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>
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{(}\\
=== Память ===
Алгоритм в виде, описанном выше, требует <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>
