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

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

Свойства

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

• [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