Задача о редакционном расстоянии — различия между версиями
(Новая страница: «'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирова…») |
(→Редакционное предписание) |
||
| Строка 12: | Строка 12: | ||
== Редакционное предписание == | == Редакционное предписание == | ||
| − | ''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' ( | + | ''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение. |
Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований: | Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований: | ||
| − | {| | + | {| border="1" |
| − | + | |'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I''' | |
|- | |- | ||
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' || | |'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' || | ||
|- | |- | ||
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4''' | |'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4''' | ||
| − | |} | + | |
| + | |-} | ||
Версия 13:52, 10 декабря 2010
Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Свойства
Для расстояния Левенштейна справедливы следующие утверждения:
где — расстояние Левенштейна между строками и , а |S| - длина строки S.
Редакционное предписание
Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) — удалить, I (англ. insert) — вставить, R (англ. replace) — заменить, M (англ. match) — совпадение.
Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
| M | M | M | M | R | M | R | I |
| h | e | l | l | 1 | 2 | 3 | |
| h | e | l | l | o | 2 | 1 | 4 |
