Изменения
Новая страница: «'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирова…»
'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
== Свойства ==
Для расстояния Левенштейна справедливы следующие утверждения:
* <math>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</math>
* <math>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</math>
* <math>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</math>
где <math>\rm{d}(S_1,S_2)</math> — расстояние Левенштейна между строками <math>S_1</math> и <math>S_2</math>, а |S| - длина строки S.
== Редакционное предписание ==
''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' ({{lang-en|delete}}) — удалить, '''I''' (англ. insert) — вставить, '''R''' ({{lang-en2|replace}}) — заменить, '''M''' ({{lang-en2|match}}) — совпадение.
Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
{| class="wikitable"
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
|}
== Свойства ==
Для расстояния Левенштейна справедливы следующие утверждения:
* <math>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</math>
* <math>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</math>
* <math>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</math>
где <math>\rm{d}(S_1,S_2)</math> — расстояние Левенштейна между строками <math>S_1</math> и <math>S_2</math>, а |S| - длина строки S.
== Редакционное предписание ==
''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' ({{lang-en|delete}}) — удалить, '''I''' (англ. insert) — вставить, '''R''' ({{lang-en2|replace}}) — заменить, '''M''' ({{lang-en2|match}}) — совпадение.
Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
{| class="wikitable"
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
|}
