ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
35
Рис. 3. Пример вычисления расстояния Дамерау – Левенштейна
Теоремы Укконена.
Основой для уменьшения временной
сложности алгоритма Вагнера – Фишера стали теоремы, доказанные
Э. Укконеном [4, 5]. Он доказал, что для матрицы
D
(
расстояние Ле-
венштейна) разность значений двух соседних ячеек по горизонтали
или по вертикали может быть равна –1, 0, +1, а разность значений
двух диагональных ячеек – 0 или 1 (рис. 4).
В дополнение к теоремам Укконена Хиро установил, что для
матрицы
DT
(
расстояние Дамерау – Левенштейна) разность значений
двух диагональных ячеек может составлять 2 [3].
Использование отсечений Укконена в алгоритме Вагнера –
Фишера.
На основе свойств диагональных элементов Укконен пред-
ложил более производительную модификацию алгоритма Вагнера –
Фишера для вычисления расстояния Левенштейна. Хиро адаптировал
подход Укконена для расстояния Дамерау – Левенштейна [3].
Отсечения Укконена следует использовать в том случае, когда
кроме строк
S
1
и
S
2
задано пороговое расстояние
K
.
Если расстояние
между строками
S
1
и
S
2
меньше или равно пороговому расстоянию
(
1 2
( , )
d S S K
≤
),
то строки полагаются совпадающими; если это рассто-
яние больше порогового (
1 2
( , )
d S S K
>
),
то – несовпадающими.