ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
37
Если в новом столбце все элементы больше
K
,
то значение право-
го нижнего элемента матрицы заведомо больше значения
K
.
Расчет
останавливается, значения в оставшихся столбцах не вычисляются.
Строки не совпадают, так как они различаются на расстояние, боль-
шее
K
(
рис. 5,
а
).
Рис. 5. Пример вычисления расстояния Дамерау – Левенштейна с ис-
пользованием отсечений Укконена для значений
K
= 2 (
а
), 3 (
б
), 4 (
в
)
и
5 (
г
) (
отсеченные ячейки заполнены символом «*»)
Если при переходе к следующему столбцу
U
=
N
(
достигнута
нижняя граница матрицы), то проводить отсечения далее нельзя, для
следующих столбцов осуществляется полный расчет (рис. 5,
а
,
в
).