ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
36
Рис. 4. Иллюстрация теорем Укконена для матриц
D
(
расстояние Ле-
венштейна) (
а
)
и
DT
(
расстояние Дамерау – Левенштейна) (
б
)
Принцип отсечений Укконена заключается в следующем: если зна-
чение элемента матрицы больше порогового значения, то этот элемент
не входит в расчеты, в результате чего уменьшается время расчета.
Поскольку
[ ]
[
]
,
1,
1 0
D i j D i
j
− − − ≥
,
то элементы произвольной
диагонали матрицы образуют неубывающую последовательность.
Поэтому, если
[ ]
,
D i j K
>
,
то следующие диагональные элементы
[
]
,
D i h j h
+ +
,
где
h
≥ 0, также больше значения
K
и их можно не учи-
тывать при расчетах.
Для реализации отсечений Укконена в алгоритм Вагнера – Фи-
шера необходимо внести следующие изменения.
Вводится дополнительная переменная
U
,
которая соответствует
индексу отсечения для текущего столбца.
Значения в столбце считаются не от 0 до
N
,
как в алгоритме Ваг-
нера – Фишера, а от 0 до
U
.
Элементы с индексами, большими пере-
менной
U
,
отсекаются, так как заполняются заведомо большими зна-
чениями, которые не влияют на действие «минимум» (см. (2)) при
расчете следующих элементов.
Для первого столбца, который в соответствии с алгоритмом Ваг-
нера – Фишера инициализируется последовательными значениями
DT
[
i
, 0]
=
i
значение переменной
U
равно значению
K
.
При переходе к следующему столбцу переменная
U
увеличивает-
ся на 1 (происходит переход к следующему диагональному элемен-
ту). Если в новом столбце элемент с индексом
U
оказывается больше
K
,
то индекс
U
уменьшается до тех пор, пока элемент с индексом
U
не будет меньше или равен
K
.