Изменения
Нет описания правки
{{Определение|definition='''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}
== Свойства ==
Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений(важно помнить, что элементы нумеруются с 1):
<code>
D(0,0) = 0
вернуть D(M, N)
</code>
== Литература ==
*http://en.wikipedia.org
*Романовский И.В. "Дискретный анализ"
