Задача о редакционном расстоянии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирова…»)
 
 
(не показано 40 промежуточных версий 3 участников)
Строка 1: Строка 1:
'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
+
#перенаправление [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
 
 
 
== Свойства ==
 
 
 
Для расстояния Левенштейна справедливы следующие утверждения:
 
* <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'''
 
|}
 

Текущая версия на 04:02, 3 февраля 2012