Задача о редакционном расстоянии

Материал из Викиконспекты
Версия от 13:52, 10 декабря 2010; 192.168.0.2 (обсуждение) (Редакционное предписание)
Перейти к: навигация, поиск

Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.


Свойства

Для расстояния Левенштейна справедливы следующие утверждения:

  • [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 (англ. 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