Исследование алгоритмов расчета редакционного расстояния
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Министерство образования и науки Российской Федерации Федеральное агентство по образованию ГОУ ВПО Северокавказский государственный технический университет
Факультет информационных технологий и телекоммуникаций
Курсовая работа
на тему: Исследование алгоритмов расчета редакционного расстояния
по специальности 090105 Комплексное обеспечение информационной безопасности автоматизированных систем
Выполнил: Червоненко Александр Игоревич
Группа БАС-081
Содержание
Введение
. Алгоритм Вагнера-Фишера
.1 Редакционное предписание
.2 Разные цены операций и транспозиция
.3 Структура алгоритма Вагнера-Фишера
. Алгоритм Хиршберга
.1 Структура алгоритма Хиршберга
.2 Анализ алгоритма
. Нечёткий поиск
.1 Алгоритмы нечёткого поиска без индексации
.2 Алгоритм Bitap
.3 Алгоритм расширения выборки
Заключение
Список использованных источников
Введение
Очень часто мы сравниваем, две строки по принципу равны/не равны, и искать строку в подстроке. На практике же, когда строки не равны, интересен вопрос, а насколько отличаются две строки?
Редакционное расстояние (также расстояние Левенштейна или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике - это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. Расстояние Левенштейна определяет, сколько раз надо добавить/удалить/заменить символ, чтобы одну строку превратить в другую. Например, расстояние между словами kitten и sitting равно трем. Этот, и похожие алгоритмы используется для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированного текста или речи), в биоинформатике для сравнения генов, хромосом и белков.
Я рассмотрел метод вычисления редакционного расстояния при использовании небольшого объема памяти, без существенной потери скорости. Данный подход может быть применен для больших строк (порядка 105 символов, т.е. фактически для текстов) при получении не только оценки схожести, но и последовательности всех происходящих изменений для перевода текста одной строки в другую.
1. Алгоритм Вагнера-Фишера
Для решения поставленной задачи, я решил воспользоваться некоторыми алгоритмами, первый, из которых алгоритм Вагнера-Фишера.
.1 Редакционное предписание
Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) - удалить, I (англ. insert) - вставить, R (replace) - заменить, M (match) - совпадение.
Например, для 2-х строк CONNECT и CONEHEAD можно построить следующую таблицу преобразований:
MMMRRRRICONNECTCONEHEADТаблица 1.1 - Таблица преобразований.
Найти только расстояние Левенштейна - более простая задача, чем найти ещё и редакционное предписание.
.2 Разные цены операций и транспозиция
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии, разную вероятность разных ошибок при вводе текста и т. д. В общем случае:
w(a, b) - цена замены символа a на символ b;
w(?, b) - цена вставки символа b;
w(a, ?) - цена удаления символа a.
Необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при:
w(a, а) = 0;
w(a, b) = 1 при a?b;
w(?, b) = 1;
w(a, ?) = 1.
Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера - Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).
Если к списку разрешённых операций добавить транспозицию (два соседних символа меняются местами), получается расстояние Дамерау - Левенштейна. Для неё также существует алгоритм, требующий O(MN) операций. Дамерау показал, что 80% ошибок при наборе текста человеком являются транспозициями. Кроме того, расстояние Дамерау - Левенштейна используется и в биоинформатике.
.3 Структура алгоритма Вагнера-Фишера
Здесь и далее считается, что элементы строк нумеруются с первого, как принято в математике, а не с нулевого, как принято в языках С, С++, Java.
Пусть S1 и S2 - две строки (длиной M и N соответственно) над некоторым алфавитом, тогда редакционное расстояние d(S1,S2).
(1.1);
(1.2).
где m(a,b) равна нулю, если a = b и единице в противном случае; min(a,b,c) возвращает наименьший из аргументов.
Рассмотрим формулу 1.3.2 более подробно. Здесь D(i,j) - расстояние между префиксами строк: первыми i символами строки S1 и первыми j символами строки S2. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной i, нужно совершить i операций удаления, а чтобы получить строку длиной j из пустой, нужно произвести j операций вставки. Осталось рассмотреть нетривиальный