ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
34
утверждениям 1 и 2, необходимо осуществить
[
]
1, 1
D i
j
− −
опера-
ций, т. е. потребуется операций,
[
]
1, 1 1
D i
j
− − +
,
[ ] [ ]
1
2
(
,
) 1
m S i S j
=
.
Расстояние Левенштейна определяет минимальное количество
действий, в связи с чем берется минимум из выражений, полученных
в рамках утверждений 1–3.
При нахождении расстояния Дамерау – Левенштейна (транспо-
зиция принимается за единичное расстояние) на основе вычислен-
ных элементов матрицы
[ ]
,
D i j
определяются элементы матрицы
[ ]
,
DT i j
[2]:
[ ]
[ ]
[
]
[ ]
[ ]
[ ]
[ ] [ ]
[ ]
[ ]
1
2
(
транспозиция)
1
2
1
2
,
;
min(
Если выполняются условия
(
расстояние Левенштайна);
,
1, 1,
(2)
(
,
)
;
2,
2
1 ,
1
)
,
;
Если не выполняются условия
DT i j
D i j
i
j
D
m S S
i
j
j
i
S i S j
S i
S j
D i j
=
⎧
⎪
⎪
⎪
> >
⎪= ⎨
+
− −
⎪
= −
− =
⎪
⎪
⎪⎩
Значение правого нижнего элемента матрицы
[
]
,
D M N
и будет
расстоянием Дамерау – Левенштейна.
В качестве примера рассмотрим расчет расстояния Дамерау – Ле-
венштейна при выполнении четырех действий над словом «ИВА-
НОВ» (рис. 3):
1.
Добавление буквы Н в середине слова – «ИВАННОВ».
2.
Удаление буквы И в начале слова – «ВАННОВ».
3.
Замена буквы В на Б – «БАННОВ».
4.
Перестановка букв В и О – «БАННВО».
Каждое действие увеличивает расстояние на 1, в результате чего
итоговое расстояние Дамерау – Левенштейна равно 4.
Алгоритм Вагнера – Фишера
позволяет получать расстояние
Дамерау – Левенштейна по формуле (2), предполагает полный обход
матрицы
DT
по столбцам и вычисление ее элементов [6].
Временная сложность алгоритма, зависящая от произведения
MN
,
составляет
O
(
MN
),
где
M
и
N
–
длины строк. Таким образом, время
выполнения алгоритма прямо пропорционально количеству ячеек в
матрице
DT
.
Для уменьшения объема используемой памяти компьютера мож-
но строить не матрицу
MN
,
а матрицу 3
N
,
так как для вычислений
используются только три последних столбца матрицы.