ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
31
венштейна (редакционного расстояния) основано на понятии «редак-
ционное предписание».
Редакционное предписание
–
последовательность действий, необ-
ходимых для получения из первой строки второй кратчайшим спосо-
бом. Как правило, действия имеют следующие обозначения: D (
delete
) –
удаление символа; I (
insert
) –
добавление символа; R (
replace
) –
замена
символа; M (
match
) –
совпадение символа.
В качестве примера редакционного предписания рассмотрим
преобразование слова «ПРИМЕРЫ» в слово «ПРЕДМЕТ» (рис. 1),
которое выполняется за четыре действия (добавление, удаление и
две замены).
Рис. 1. Пример редакционного предписания
Расстояние Левенштейна
–
минимальное количество действий,
необходимых для преобразования одного слова в другое. В приве-
денном примере расстояние Левенштейна равно 4.
Преобразовать одно слово в другое можно различными способа-
ми, количество действий также может быть разным. При вычислении
расстояния Левенштейна следует выбирать минимальное количество
действий.
Если поиск слова осуществляется в тексте, который набран с кла-
виатуры, то вместо расстояния Левенштейна используют усовершен-
ствованное расстояние Дамерау – Левенштейна.
Исследования Ф. Дамерау показали, что наиболее частая ошибка
при наборе слова – перестановка двух соседних букв, транспозиция T
(
transposition
) [2].
В случае одной транспозиции расстояние Левен-
штейна равно 2. При использовании поправки Дамерау транспозиция
принимается за единичное расстояние (рис. 2).
При использовании расстояния Дамерау – Левенштейна за
единичное расстояние принимают следующие действия: I (
insert
) –
добавление символа; D (
delete
) –
удаление символа; R (
replace
) –
замена символа; T (
transposition
) –
перестановка двух соседних
символов.