ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
38
После расчета всей матрицы анализируется правый нижний эле-
мент. Если его значение отсечено или больше
K
(
рис. 5,
а
,
б
),
то стро-
ки не совпадают, если меньше или равно
K
(
рис. 5,
в
,
г
),
то строки
совпадают.
Производительность алгоритма Вагнера – Фишера с отсечениями
Укконена зависит от порогового расстояния
K
.
Чем меньше значения
K
,
тем больше элементов отсекается и тем выше производительность
алгоритма.
Временная сложность алгоритма Вагнера – Фишера с отсечения-
ми Укконена составляет
O
(
MK
),
т. е. в каждом столбце вычисляются
не все
N
элементов, а в среднем
K
элементов [3].
Методика идентификации пассажира по установочным дан-
ным.
С учетом рассмотренных алгоритмов нечеткого сравнения
строк текста, сформулируем методику идентификации пассажира по
установочным данным, которая содержит следующие шаги.
1.
Загрузка оперативных списков в поисковый массив.
2.
Задание значений порогового расстояния для каждого элемента
установочных данных (фамилии, имени, отчества).
3.
Сравнение установочных данных пассажира, проходящего
контроль, с каждой записью в оперативных списках.
4.
Вычисление расстояния Дамерау – Левенштейна для каждого
элемента установочных данных пассажира (фамилии, имени, отче-
ства) и каждого элемента установочных данных в текущей записи
оперативных списков с использованием алгоритма Вагнера – Фишера
с отсечениями Укконена.
5.
Сравнение вычисленных значений расстояния Дамерау – Ле-
венштейна со значениями порогового расстояния. Если для каждого
элемента установочных данных пассажира (фамилии, имени, отче-
ства) полученные значения меньше значений порогового расстояния,
то пассажир считается найденным в оперативных списках.
Выводы.
Проблема нечеткого сравнения установочных данных
сводится к проблеме нечеткого сравнения множества строк. Для не-
четкого сравнения строк используется подход на основе вычисления
значений расстояния Дамерау – Левенштейна. Чтобы определить
расстояние Дамерау – Левенштейна, используют алгоритм Вагнера –
Фишера, производительность которого повышают с помощью отсе-
чения Укконена.
СПИСОК ЛИТЕРАТУРЫ
1.
Л е в е н ш т е й н В. И. Двоичные коды с исправлением выпадений, вставок
и замещений символов: Докл. Академий Наук СССР, 1965. С. 845–848.
2.
D a m e r a u F. A. Technique for Computer Detection and Correction of Spelling
Errors // Communications of the ACM. 1964. Vol. 7. No. 3. P. 171–176.