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