Исследование алгоритмов расчета редакционного расстояния

Министерство образования и науки Российской Федерации Федеральное агентство по образованию ГОУ ВПО «Северокавказский государственный технический университет»

Факультет информационных технологий и телекоммуникаций Курсовая работа на тему: «Исследование алгоритмов расчета редакционного расстояния»

по специальности 90 105 «Комплексное обеспечение информационной безопасности автоматизированных систем»

Выполнил: Червоненко Александр Игоревич Группа БАС-081

Содержание Введение

1. Алгоритм Вагнера-Фишера

1.1 Редакционное предписание

1.2 Разные цены операций и транспозиция

1.3 Структура алгоритма Вагнера-Фишера

2. Алгоритм Хиршберга

2.1 Структура алгоритма Хиршберга

2.2 Анализ алгоритма

3. Нечёткий поиск

3.1 Алгоритмы нечёткого поиска без индексации

3.2 Алгоритм Bitap

3.3 Алгоритм расширения выборки Заключение Список использованных источников

Очень часто мы сравниваем, две строки по принципу равны/не равны, и искать строку в подстроке. На практике же, когда строки не равны, интересен вопрос, а насколько отличаются две строки?

Редакционное расстояние (также расстояние Левенштейна или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. Расстояние Левенштейна определяет, сколько раз надо добавить/удалить/заменить символ, чтобы одну строку превратить в другую. Например, расстояние между словами kitten и sitting равно трем. Этот, и похожие алгоритмы используется для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированного текста или речи), в биоинформатике для сравнения генов, хромосом и белков.

Я рассмотрел метод вычисления редакционного расстояния при использовании небольшого объема памяти, без существенной потери скорости. Данный подход может быть применен для больших строк (порядка 105 символов, т. е. фактически для текстов) при получении не только оценки «схожести», но и последовательности всех происходящих изменений для перевода текста одной строки в другую.

1. Алгоритм Вагнера-Фишера

Для решения поставленной задачи, я решил воспользоваться некоторыми алгоритмами, первый, из которых алгоритм Вагнера-Фишера.

1.1 Редакционное предписание

Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) — удалить, I (англ. insert) — вставить, R (replace) — заменить, M (match) — совпадение.

Например, для 2-х строк «CONNECT» и «CONEHEAD» можно построить следующую таблицу преобразований:

Таблица 1.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% ошибок при наборе текста человеком являются транспозициями. Кроме того, расстояние Дамерау — Левенштейна используется и в биоинформатике.

1.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 операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:

§ Две замены одного и того же символа — не оптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).

§ Две замены разных символов можно менять местами.

§ Два стирания или две вставки можно менять местами.

§ Вставка символа с его последующим стиранием — не оптимально (можно их обе отменить).

§ Стирание и вставку разных символов можно менять местами.

§ Вставка символа с его последующей заменой — не оптимально (излишняя замена).

§ Вставка символа и замена другого символа меняются местами.

§ Замена символа с его последующим стиранием — не оптимально (излишняя замена).

§ Стирание символа и замена другого символа меняются местами.

Пускай S1 кончается на символ «a», S2 кончается на символ «b». Есть три варианта:

1. Символ «а», на который кончается S1, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые i? 1 символов S1 в S2 (на что потребовалось операций), значит, всего потребовалось операций;

2. Символ «b», на который кончается S2, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили S1 в первые j ?1 символов S2, после чего добавили «b». Аналогично предыдущему случаю, потребовалось D (i, j-1)+1 операций;

3. Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз не оптимально.

Значит:

1. Если a = b, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили операций.

2. Если, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить D (i-1, j-1) операций, значит, всего потребуется D (i-1, j-1)+1 операций.

2. Алгоритм Хиршберга

При рассмотрении массива расстояний из метода Вагнера-Фишера становится, очевидно, что при таком подходе требования к памяти равны O (M*N). Например, для сравнения файлов длиной в 105 строк потребуется около 40 гигабайт памяти. Чтобы избежать проблем с памятью при работе с длинными строками, Хиршберг разработал линейную относительно затрат памяти версию этого алгоритма.

2.1 Структура алгоритма Хиршберга

Будем применять рекурсию для разбиения задачи на подзадачи, каждая из которых не потребует много памяти. Для дальнейших зарисовок возьмем какие-нибудь начальные значения строк:

S1 = ACGTACGTACGT,

S2 = AGTACCTACCGT.

Переписать одну в другую «на глаз» не так очевидно. Буквы, кстати, выбраны не случайно — это азотистые основания (A, T, G, C), компоненты ДНК: метод оценки редакционного расстояния активно применяется в биологии для оценки мутаций. Тогда исходная не заполненная матрица будет выглядеть (именно выглядеть, хранить мы будем только необходимые данные) следующим образом:

Рисунок 2.1 — Матрица

В каждой клетке должно стоять значение редакционного расстояния. Поделим исходную задачу на подзадачу, поделив вторую строку на две равные (или почти равные) части, запомним место разбиения, и начнем заполнять матрицу ровно так же, как делали в Вагнера — Фишера:

Рисунок 2.2 — Матрица

При заполнении мы не будем хранить предыдущие столбцы, двигаясь слева направо, сверху вниз, по мере вычисления значений D (i, j) значения D (i-1, j) можно удалять:

Рисунок 2.3 — Заполнение матрицы

Аналогично, заполним правую часть разбиения. Здесь будем двигаться справа налево, сверху вниз.

Вот мы и встретились. Теперь можно получить часть решения общей задачи, совместив частные. Просуммируем получившиеся в левых и правых столбцах значения и выберем минимум.

Рисунок 2.4 — Подсчет матрицы

алгоритм редакционное предписание

Что означает это совмещение? Я попытался совместить первую строку с первой половиной второй строки, затем первую строку с второй половиной строки. Сумма позволяет получить количество операций изменения первой строки, чтобы привести ее к конкатенации первой и второй половины второй строки (то есть к второй строке) это значит что мы получили значение редакционного расстояния. Но, рано радоваться, ибо этого результата можно было достичь и проще (вышеописанный метод).

Однако, посмотрев на картинку под другим углом (буквально), мы получили еще один существенный факт: теперь мы знаем как «разрезать» первую строку на две половины, чтобы соответствующие пары дали нам редакционное расстояние: d (S11,S21) + d (S12,S22) = d (S1,S2). Строка (в матрице), в которой расположен минимум и есть искомое разбиение S1, и это разбиение отправляется в выдачу редакционного предписания.

Аналогично будем делить задачу уже для получившихся подстрок S11 и S21 (и вторую пару тоже не забудем):

Рисунок 2.5 — Подсчет матрицы

Завершим подразделение, когда не останется ни одной подстроки S1 длины больше 1.

Рисунок 2.6- Принцип подсчета матрицы

Получим список разбиений, где каждая подстрока S1 (смотреть по вертикали) дает минимальную оценку изменений относительно соответствующей подстроки S2 (по горизонтали).

Для удобства я раскрасил отметки цветами: зеленый означает посимвольное совпадение строк в выбранных позициях, синим необходимость замены, а красным — удаления или добавления. Нетрудно заметить, что «красные» кружки находятся в той же строке/столбце (задачка внимательным: объяснить из чего это следует).

В более удобной форме результат может быть записан так (красные штрихи — соответствие символов, сдвиги обозначены черными горизонтальными):

Рисунок 2.7 — Строки

2.2 Анализ алгоритма

Память: для каждого шага потребуется запоминать не более чем один столбец d (i,*) и набор разбиений S1. Итого O (|S1| + |S2|). То есть вместо квадратичного объема мы получаем линейный.

Время: каждое разбиение S[0.N] по столбцу t порождает обработку подстрок S[0.t] и S[t.N]. Всего разбиений N. При обработке каждого разбиения (S1[i.j], S1[k.n]) требуется (j — i) x (n — k) операций. Суммируя, оценку худших случаев для подстрок получаем в итоге 2 * |S1| * |S2| операций. Время работы алгоритма осталось квадратичным, хоть и изменилась мультипликативная константа.

Итак, я решил задачу, используя, линейное количество памяти и незначительно потеряли в скорости, что в данном случае можно считать успехом.

3. Нечёткий поиск

3.1 Алгоритмы нечёткого поиска без индексации

Эти алгоритмы предназначены для поиска по заранее неизвестному тексту, и могут быть использованы, например, в текстовых редакторах, программах для просмотра документов или в веб браузерах для поиска по странице. Они не требуют предварительной обработки текста и могут работать с непрерывным потоком данных.

Простое последовательное применение заданной метрики (например, метрики Левенштейна) к словам из входного текста. При использовании метрики с ограничением, этот метод позволяет добиться оптимальной скорости работы. Но, при этом, чем больше k, тем сильнее возрастает время работы. Асимптотическая оценка времени — O (kn).

3.2 Алгоритм Bitap

Алгоритм Bitap (также известный как Shift-Or или Baeza-Yates-Gonnet)и различные его модификации наиболее часто используются для нечеткого поиска без индексации. Его вариация используется, например, в unix-утилите agrep, выполняющей функции аналогично стандартному grep, но с поддержкой ошибок в поисковом запросе и даже предоставляя ограниченные возможности для применения регулярных выражений.

Впервые идею этого алгоритма предложили граждане Ricardo Baeza-Yates и Gaston Gonnet, опубликовав соответствующую статью в 1992 году. Оригинальная версия алгоритма имеет дело только с заменами символов, и, фактически, вычисляет расстояние Хемминга. Но немного позже Sun Wu и Udi Manber предложили модификацию этого алгоритма для вычисления расстояния Левенштейна, т. е. привнесли поддержку вставок и удалений, и разработали на его основе первую версию утилиты agrep.

Операция Bitshift:

(3.1)

Вставки:

(3.2)

Удаления:

(3.3)

Замены:

(3.4)

Результирующее значение:

(3.5)

где k — количество ошибок, j — индекс символа, sx — маска символа (в маске единичные биты располагаются на позициях, соответствующих позициям данного символа в запросе). Совпадение или несовпадение запросу определяется самым последним битом результирующего вектора R.

Высокая скорость работы этого алгоритма обеспечивается за счет битового параллелизма вычислений — за одну операцию, возможно, провести вычисления над 32 и более битами одновременно. При этом тривиальная реализация поддерживает поиск слов длиной не более 32. Это ограничение обуславливается шириной стандартного типа int (на 32-битных архитектурах). Можно использовать и типы больших размерностей, но это может в некоторой степени замедлить работу алгоритма.

Не смотря на то, что асимптотическое время работы этого алгоритма O (kn) совпадает с таковым у линейного метода, он значительно быстрее при длинных запросах и количестве ошибок k более 2.

Очевидно, что простой перебор с использованием метрики, в отличие от алгоритма Bitap, сильно зависит от количества ошибок k.

Тем не менее, если речь заходит о поиске в неизменных текстах большого объема, то время поиска можно значительно сократить, произведя предварительную обработку такого текста, также называемую индексацией.

3.3 Алгоритм расширения выборки

Этот алгоритм часто применяется в системах проверки орфографии (т.е. в spell-checker'ах), там, где размер словаря невелик, либо же где скорость работы не является основным критерием. Он основан на сведении задачи о нечетком поиске к задаче о точном поиске.

Из исходного запроса строится множество «ошибочных» слов, для каждого из которых затем производится точный поиск в словаре.

Время его работы сильно зависит от числа k ошибок и от размера алфавита A, и в случае использования бинарного поиска по словарю составляет:

(3.6)

Например, при k = 1 и слова длины 7 (например, «Крокодил») в русском алфавите множество ошибочных слов будет размером около 450, то есть будет необходимо сделать 450 запросов к словарю, что вполне приемлемо. Но уже при k = 2 размер такого множества будет составлять более 115 тысяч вариантов, что соответствует полному перебору небольшого словаря, либо, же 1 / 27 в нашем случае, и, следовательно, время работы будет достаточно велико. При этом не нужно забывать еще и о том, что для каждого из таких слов необходимо провести поиск на точное совпадение в словаре.

Особенности: алгоритм может быть легко модифицирован для генерации «ошибочных» вариантов по произвольным правилам, и, к тому же, не требует никакой предварительной обработки словаря, и, соответственно, дополнительной памяти.

Возможные улучшения: можно генерировать не всё множество «ошибочных» слов, а только те из них, которые наиболее вероятно могут встретиться в реальной ситуации, например, слова с учетом распространенных орфографических ошибок или ошибок набора.

Заключение

Результатом написания данной курсовой работы стала программная реализация одного из алгоритмов расчета редакционного расстояния или расстояния Левенштейна.

Данные алгоритмы широко применяются в программных средствах интернет — ресурсов, различных видах символьного поиска, а также в коррекции текста и обнаружения в нем ошибок.

Основной задачей при совершенствовании подобных алгоритмов является уменьшение ресурсоёмкости программного обеспечения, что зачастую сказывается на скорости расчета редакционного расстояния. Именно так были созданы алгоритмы нечёткого поиска. Это и является основным недостатком алгоритмов расчета расстояния Левенштейна.

В своей реализации подобного алгоритма я взял алгоритм Вагнера-Фишера.

алгоритм редакционное предписание

Список использованных источников

1. В. И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР, 1965

2. В. И. Левенштейн, Об одном классе систематических кодов, Докл. АН СССР, 131, 5, 1960, 1011−1014

3. В. И. Левенштейн, О некоторых свойствах кодовых систем, Докл. АН СССР, 140, 6, 1961, 1274−1277

4. В. И. Левенштейн, Двоичные коды с исправлением выпадений, вставок и замещений символов, Докл. АН СССР, 163, 4, 1965, 845−848

5. Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. Невский Диалект БВХ — Петербург, 2003

6. Блейхут Р. Теория и практика кодов, контролирующих ошибки (Theory and Practice of Error Control Codes) — М.: Мир, 1986

7. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979

8. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006

9. Романовский И. В. «Дискретный анализ», Москва, 2005

10. Р. Лоуренс, Роберт А. Вагнер, «Проблемы коррекции при расширении строка — в — строку», JACM, 1975

11. Б. Д. Ооммен, Р.К. С. Лок, «Распознавание строки с заменой, вставкой, удалением и обобщенной перестановкой»