Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Вятский государственный гуманитарный университет»
ФАКУЛЬТЕТ ИНФОРМАТИКИ
КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И МЕТОДИКИ ОБУЧЕНИЯ ИНФОРМАТИКЕ
ДИПЛОМНАЯ РАБОТА
Алгоритмы построения суффиксных деревьев
Выполнила
___________________/подпись/
Научный руководитель
___________________/подпись/
Допущена к защите в ГАК
Зав. кафедрой _________________________ М.В. Петухова
(подпись) «____»___________2010г.
Декан факультета ______________________С.М. Окулов
(подпись) «____»___________2010г.
Киров
2010
Оглавление
Введение 3
Глава 1. Суффиксные деревья: основные понятия и алгоритмы построения 6
1.1 Определение суффиксного дерева 6
1.2. Алгоритмы построения суффиксных деревьев 9
1.2.1 Наивный алгоритм построения суффиксного дерева 9
1.2.2 Алгоритм Укконена для построения суффиксных деревьев 13
1.3 Выводы по первой главе 22
Глава 2. Программная реализация алгоритмов построения суффиксных деревьев 23
2.1 Реализация наивного алгоритма построения суффиксного дерева на ЯП Паскаль 23
2.2 Реализация алгоритма Укконена построения суффиксного дерева на ЯП Паскаль 25
2.3 Выводы по второй главе 27
Глава 3. Практическое применение суффиксных деревьев 29
Заключение 32
Библиографический список 33
Введение
Актуальность исследования. В теории и практике задачи поиска подстроки в строке встречаются весьма часто. В основном эта область считается довольно хорошо изученной – имеется множество алгоритмов, разработок и т.п. Однако в основном все это относится к строкам небольшой длины.
В том случае, когда осуществляется поиск в очень длинных строках, то практически все алгоритмы быстрого поиска становятся неприменимы из-за требования большого количества дополнительной памяти. При этом применимы только те из них, которые не требовательны к памяти, но зато они медленнее. Как правило, в таких случаях лучше использовать алгоритмы, в которых скорость поиска осуществляется за линейное время. В основном эти алгоритмы базируются на суффиксных деревьях.
Суффиксные деревья получили широкое применение в различных областях. Изначально они были придуманы для решения задачи о быстром поиске в тексте множества заранее неизвестных слов.
Пусть задан текст Т длины m. За препроцессное время О(m), т.е. линейное, нужно приготовиться к тому, чтобы, получив неизвестную строку S длины n, за время О(n) либо найти вхождение S в T, либо определить, что S в T не входит. Это значит, что допустим препроцессинг со временем, пропорциональным длине текста, но после этого поиск строки S должен выполняться за время, пропорциональное длине S, независимо от длины Т. Эти границы достигаются применением суффиксного дерева. Оно строится для текста за время О(m) в препроцессной стадии; а затем, используя это суффиксное дерево, алгоритм, получив строку длины n на входе, ищет ее за время О(n).
Время О(m) на препроцессинг и О(n) на поиск в задаче о подстроке — это удивительный и крайне полезный результат. В обычных приложениях, после того как будет построено суффиксное дерево, вводится длинная последовательность строк-запросов, так что линейная оценка времени для каждого поиска очень важна. Такая оценка не достигается методами Кнута-Морриса-Пратта и Бойера-Мура.
Рассмотренный выше пример задачи возникает в широком спектре приложений. Например, в текстовых редакторах, информационно-поисковых текстовых системах библиотечных каталогов, интернетовских браузерах, которые просеивают огромные количества текстов в поисках материалов, содержащих данные ключевые слова, в электронных журналах, в обслуживании телефонных справочников, в интерактивных энциклопедиях и т.д.
Также суффиксные деревья можно применить и при решении других задач: задача о количестве различных подстрок в данной строке, задача о построении суффиксного автомата, задача о поиске наибольшей подстроки двух строк.
Но суффиксные деревья применяются не только в областях близких к информатике, они также могут эффективно применяться и при изучении таких наук, как молекулярная биология для работы с молекулярными последовательностями (строками), где эффективность обработки информации играет не последнюю роль.
Широкий спектр применения суффиксных деревьев определяет их важность при обработке информации. Всё вышесказанное и обосновывает актуальность исследования
Гипотеза исследования. Определение и реализация алгоритмов построения дерева суффиксов позволит в дальнейшем использовать их для решения сформулированных выше задач за линейное время, т.е. более эффективно.
Объект исследования– методы и алгоритмы работы со строками.
Предмет исследования – методы и алгоритмы построения суффиксных деревьев.
Цель исследования – реализовать алгоритмы построения суффиксных деревьев и оценить их эффективность.
Исходя из цели исследования были определены следующие задачи:
1. Изучить и проанализировать научную литературу по проблеме исследования.
2. Определить основные понятия теории суффиксных деревьев и представить их на конкретных примерах.
3. Показать логику работы алгоритмов построения суффиксных деревьев для определённых наборов строк.
4. Реализовать соответствующие алгоритмы и оценить результаты их работы.
5. Рассмотреть практические приложения суффиксных деревьев.
На защиту выносятся следующие положения:
1. Примеры, раскрывающие сущность суффиксных деревьев, и логику работы алгоритмов их построения для определённых наборов строк.
2. Реализация алгоритмов на языке программирования и оценка результатов их работы.
3. Практические примеры приложения суффиксных деревьев.
Квалификационная работа состоит из введения, трёх глав, заключения, списка литературы и приложений.
Глава 1. Суффиксные деревья: основные понятия и алгоритмы построения
Первый алгоритм для конструирования суффиксных деревьев за линейное время был предложен Вайнером в 1973 году, хотя он использовал термин дерево позиций. Другой алгоритм построения суффиксных деревьев за линейное время, более экономный по памяти, был предложен Мак-Крейгом несколько лет спустя. Недавно Укконен разработал принципиально иной алгоритм построениям суффиксных деревьев за линейное время, который обладает всеми преимуществами алгоритма Мак-Крейга (и с правильной точки зрения может рассматриваться как его, вариант), но допускает более простое истолкование. [1]
1.1 Определение суффиксного дерева
Прежде чем рассмотреть основные алгоритмы работы с суффиксными деревьями необходимо разобраться с основными понятиями. [3]
Определение 1. Строка (S) – это последовательность символов, взятых из заранее определенного алфавита. Каждый символ алфавита имеет свой уникальный номер.
Определение 2. Алфавит – конечное множество А различимых элементов, на котором определено отношение порядка.
Понятие подстрока строки S определяется как S[i..j] для любой пары таких чисел i и j, что 1 ? i ? j ? m, где m – количество символов в S (длина строки - |S|). Если же i>j, то подстрока S[i..j] считается пустой.
Определение 3. Подстрока – это часть строки, состоящая из некоторого количества смежных символов исходной строки.
Определение 4. Префикс строки S, заканчивающейся в позиции i, - это подстрока S[1..i].
Определение 5. Суффикс строки S, начинающейся в позиции i, - это подстрока S[i..m].
Пример 1. Рассмотрим строку "алгоритм", у нее есть следующие суффиксы:
Номер Суффикс
0 "алгоритм"
1 "лгоритм"
2 "горитм"
3 "оритм"
4 "ритм"
5 "итм"
6 "тм"
7 "м"
Первым суффиксом строки называется эта строка без первого символа.
Определение 6. Суффиксное дерево для m-символьной строки S — это ориентированное дерево с корнем, имеющее ровно m листьев, занумерованных от 1 до m. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки S (дуговой меткой). Никакие две дуги, выходящие из одной и той же вершины, не могут иметь пометок, начинающихся с одного и того же символа. Главная особенность суффиксного дерева заключается в том, что для каждого листа конкатенация меток дуг на пути от корня к листу i в точности составляет (произносит) суффикс строки S, который начинается в позиции i. То есть этот путь произносит S[i..m]. [1]
Пример 2. Для строки S=’xabxac’ суффиксное дерево выглядит следующим образом (рис.1):
Рис. 1
Но определение суффиксного дерева для S не гарантирует, что такое дерево действительно существует для любой строки S. Трудность состоит в том, что если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе.
Например, если удалить последний символ из строки ‘xabxac’, образовав строку ‘xabxa’, то суффикс ‘ха’ будет префиксом суффикса ‘xabxa’, так что путь, произносящий ‘ха’, не будет заканчиваться в листе.
Во избежание этой трудности предполагается, что последний символ строки S нигде больше в строку не входит. При таком условии никакой суффикс строки не сможет быть префиксом другого суффикса. Чтобы обеспечить это на практике, можно добавить в конце строки S какой-либо символ, не входящий в основной алфавит (из символов которого составлена строка). Чаще всего используется в качестве такого "завершающего" символа ‘$’. [1]
Тогда рассмотренная строка (Пример 2) будет выглядеть следующим образом – ‘xabxa$’, соответствующее ей суффиксное дерево (рис.2) –
Рис. 2
Ниже рассмотрим несколько способов построения суффиксных деревьев. Для начала опишем еще несколько понятий, необходимых для построения суффиксных деревьев.
Определение 7. Метка пути от корня до некоторой вершины — это конкатенация подстрок, помечающих дуги пути в порядке их прохождения.
Определение 8. Путевая метка вершины — это метка пути от корня Г до этой вершины.
Определение 9. Для любой вершины v суффиксного дерева строковой глубиной v называется число символов в путевой метке v.
Путь, который кончается в середине дуги (u, v), делит метку (u,v) в своей точке назначения. Определим метку этого пути как путевую метку u с добавлением символов дуги (u, v) до делящей дугу точки назначения.
Пример 3. На Рис.3 строка ‘ха’ помечает внутреннюю вершину w (так что вершина w имеет путевую метку ‘ха’), строка ‘а’ помечает вершину u, а строка хаbx помечает путь, который кончается внутри дуги (w, 1), т.е. внутри дуги, ведущей к листу 1.
Рис. 3
1.2. Алгоритмы построения суффиксных деревьев
1.2.1 Наивный алгоритм построения суффиксного дерева
Основная идея: сначала в дерево помещается простая дуга для суффикса S[l..m]$ (для всей строки); затем последовательно вводим в растущее дерево суффиксы S[i..m]$ для i от 2 до m. Пусть Ti, обозначает промежуточное дерево, в которое входят все суффиксы от 1 до i.
Приведем словесное описание алгоритма:
1) Дерево Т1 состоит из одной дуги, идущей от корня дерева к вершине, с номером 1. Эта дуга имеет метку S$.
2) Дерево Ti+1 строится из дерева Ti путем приписывания суффикса S[i+l..m]$:
2.1) Начиная из корня Ti найти самый длинный путь от корня, метка которого совпадает с префиксом строки S[i+l..m]$ (этот путь можно отыскать последовательным сравнением и поиском совпадений символов суффикса S[i+l..m]$ с символами вдоль единственного пути из корня до тех пор, пока не обнаруживается место, где очередного совпадения нет).
2.2) В какой-то точке совпадения прекратятся. Когда такая точка будет достигнута, то алгоритм останавливается либо в вершине w, либо в середине какой-то дуги.
Если совпадения прекратятся в середине дуги (u, v), то он разбивает дугу (u, v) на две дуги, вводя новую вершину, которую можно обозначить через w, сразу после последнего совпадающего символа S[i+1..m] и перед первым несовпадающим символом. Новая дуга (u, w) имеет меткой часть метки (u, v), которая совпадает с частью S[i+l..m], а новая дуга (w, u) помечена оставшейся частью метки (u, v).
2.3) Далее (независимо от того, создана вершина w заново или она уже существовала) алгоритм создает новую дугу (w, i+1), идущую из u; в новый лист с номером i+1, и эта дуга помечается частью суффикса S[i+l..m]$, не нашедшей совпадения.
Теперь дерево содержит единственный путь из корня к листу i+1, и этот путь имеет метку S[i+l..m]$. [1]
Рассмотрим работу этого метода на конкретном примере.
Пример 4. Построить суффиксное дерево Т для строки S=’xaxxa’.
Дополняем строку S символом $.
1 шаг – дерево Т1 (Рис.4)
Рис. 4
2 шаг – дерево Т2 (Рис.5)
Рассматривается суффикс ‘axxa$’.
Т.к. символы суффикса не совпали с символами метки дуги, ведущей к 1 листу, то из корня выйдет новая дуга с меткой ‘axxa$’ к листу 2.
Рис. 5
3 шаг – дерево Т3 (Рис.6)
Рассматривается суффикс ‘xxa$’
Первый символ данного суффикса совпадает с первым символом метки дуги, ведущей к 1 листу.
Вторые символы не совпадают поэтому на дуге, ведущей к 1 листу, создается внутренняя вершина, из которой выходят 2 дуги:
1 дуга, которая помечена оставшейся частью метки ‘xaxxa$’, т.е. ‘axxa$’.
2 дуга с оставшейся частью суффикса ‘xa$’, которая ведет к 3 листу.
Рис. 6
Проделываем действия аналогичные действиям 3 шага для суффиксов ‘xa$’, ‘a$’, ‘$’ (4-6 шаги).
4 шаг – дерево Т4 (Рис.7)
Рис. 7
5 шаг – дерево Т5 (Рис.8)
Рис. 8
6 шаг – дерево Т (Рис.9)
Рис. 9
1.2.2 Алгоритм Укконена для построения суффиксных деревьев
Алгоритм Укконена строит последовательность неявных суффиксных деревьев, последнее из которых преобразуется в настоящее суффиксное дерево строки S.
Определение 10. Неявное суффиксное дерево строки S — это дерево, которое получено из суффиксного дерева строки S$ удалением всех вхождений терминального символа $ из меток дуг дерева, удалением после этого дуг без меток, а также удалением после этого вершин, имеющих меньше двух детей.
Неявное суффиксное дерево префикса S[1..i] строки S получается аналогично из суффиксного дерева для S[1..i]$ удалением символов $, дуг и вершин, как описано выше.
Обозначим через Тi неявное суффиксное дерево строки S[1..i], где i изменяется от 1 до т.
Хотя неявное суффиксное дерево может иметь листья не для всех суффиксов, в нем закодированы все суффиксы S — каждый «произносится» символами какого-либо пути от корня этого неявного суффиксного дерева. Однако, если этот путь не кончается листом, то не будет маркера, обозначающего конец пути. Таким образом, неявные суффиксные деревья сами по себе несколько менее информативны, чем обычные суффиксные деревья. Будем использовать неявные деревья указанного типа как вспомогательные в алгоритме Укконена для того, чтобы получить настоящее суффиксное дерево для S.
Общее описание алгоритма Укконена
Алгоритм Укконена строит неявное суффиксное дерево Т, для каждого префикса S[1..i] строки S, начиная с T1 и увеличивая i на единицу до тех пор, пока не будет построено дерево Тт. Суффиксное дерево для S получается из Тт, и вся работа требует времени О(т).
Алгоритм Укконена делится на m фаз. В фазе i+1 дерево Ti+1 строится из Ti. Каждая фаза i+1 в свою очередь делится на i+1 продолжений, по одному на каждый из i+1 суффиксов S[1..i+l]. В продолжении с номером j фазы i+1 алгоритм сначала находит конец пути из корня, помеченного подстрокой S[j..i]. Затем он продолжает эту подстроку, добавляя к ее концу символ S(i + 1), если только S(i + 1) еще не существует. Таким образом, в фазе i+1 сначала помещается в дерево строка S[1..i+l], а за ней строки S[2..i+1], S[3..i+1], ... (соответственно, в продолжениях 1, 2, 3, ...). Продолжение i + 1 фазы i + 1 продолжает пустой суффикс строки S[1..i] — включает в дерево строку из одного символа S(i+1) (если только ее там не было). Дерево Т1 состоит из одной дуги, помеченной символом S(1).
Правила продолжения суффиксов
Для того, чтобы превратить изложенное выше общее описание алгоритма Укконена в конкретный алгоритм, необходимо точно указать, как выполнять продолжение суффикса. Пусть S[j..i]=? — суффикс S[1..i]. В продолжении с номером j, когда алгоритм находит конец суффикса ? в текущем дереве, алгоритм продолжает ? для того, чтобы обеспечить присутствие суффикса ?S(i+1) в дереве. Алгоритм действует по одному из следующих трех правил.
Правило 1. В текущем дереве путь ? кончается в листе. Это значит, что путь от корня с меткой ? доходит до конца некоторой «листовой» дуги (дуги, входящей в лист). При изменении дерева следует добавить к концу метки этой листовой дуги символ S(i + 1).
Правило 2. Ни один путь из конца строки ? не начинается символом
S(i + 1), но, по крайней мере, один начинающийся оттуда путь имеется.
В этом случае должна быть создана новая листовая дуга, начинающаяся в конце ? и помеченная символом S(i + 1). При этом, если ? кончается внутри дуги, должна быть создана новая вершина. Листу в конце новой листовой дуги сопоставляется номер j.
Правило 3. Некоторый путь из конца строки ? начинается символом
S(i + 1). В этом случае строка ?S(i + 1) уже имеется в текущем дереве, и поэтому ничего не требуется делать.
Реализация и ускорение
Ключевым моментом в реализации алгоритма Укконена является определение концов всех i+1 суффиксов S[1..i]. Действуя наивно, можно найти конец любого суффикса ? за время О(|? |), двигаясь от корня текущего дерева. При этом подходе продолжение j в фазе i+1 займет время O(i + 1—j), Ti+1 будет создано из Тi за О (i2) и Тт получится за время О(т3).
Сведем О(т3) к О(т2) с помощью нескольких наблюдений и приемов реализации. Каждый прием сам по себе выглядит как полезная эвристика для ускорения алгоритма, и, действуя по отдельности, они не могут уменьшить оценку времени для наихудшего случая. Результат достигается только при совместном их применении. Наиболее существенный элемент ускорения — это использование суффиксных связей.
Суффиксные связи: первое ускорение реализации
Определение 11. Пусть х? обозначает произвольную строку, где х — ее первый символ, а ? — оставшаяся подстрока (возможно, пустая). Если для внутренней вершины v с путевой меткой х? существует другая вершина s(v) с путевой меткой ?, то указатель из v в s(v) называется суффиксной связью.
Хотя из определения суффиксных связей не следует, что из каждой внутренней вершины неявного суффиксного дерева выходит суффиксная связь, на самом деле так и будет.
Теорема 1. В алгоритме Укконена любая вновь созданная внутренняя вершина будет иметь суффиксную связь с концом следующего продолжения.
Таким образом, суффиксные связи будут исходить из всех внутренних вершин изменяющегося дерева, кроме внутренней вершины, введенной последней. Она получит свою суффиксную связь в конце следующего продолжения.
Переходы по суффиксным связям при построении Тi+1
Заметим, что конец полной строки S[1..i] должен быть в листе дерева Тi, так как S[1..i] — самая длинная строка в нем. Следовательно, конец этого суффикса найти легко. Представим строку S[1..i] в виде х?, где х — один символ, а ? — оставшаяся подстрока (возможно, пустая), и пусть (v, 1) — дуга дерева, входящая в лист 1. Опишем подробно второе продолжение. Пусть ? обозначает дуговую метку дуги (v,1). Для того, чтобы найти конец ?, требуется пройти вверх от листа 1 до вершины v, далее по суффиксной связи из v в s(v), а затем от s(v) — вниз по пути (который может состоять больше чем из одной дуги) с меткой ?. Конец этого пути и является концом ?. В конце пути ? дерево изменяется по правилам продолжения суффикса.
При продолжении любой строки S[j..i] до S[j..i + 1] при j > 2 следуем той же общей идее. Начиная в конце строки S[j — 1..i] в текущем дереве, поднимаемся вверх не больше чем на одну вершину, попадая либо в корень, либо в вершину v, из которой выходит суффиксная связь. Далее, пусть ? — дуговая метка этой дуги; в случае, если v не корень, проходим суффиксную связь из v в s(v) и спускаемся по дереву из s(v) по пути, помеченному ?, к концу S[j..i]. И наконец, продолжаем суффикс до S[j..i+1] по правилам продолжения.
Алгоритм отдельного продолжения
Собирая вместе все эти фрагменты, реализующие использование суффиксных связей, можно записать продолжение j > 2 фазы i+1.
Использование суффиксных связей дает очевидное практическое улучшение за счет сокращения передвижений от корня в каждом продолжении, которые выполняются в наивном алгоритме. Однако это не улучшит оценку времени выполнения в наихудшем случае. Введем особый прием, который уменьшит оценку для алгоритма до (m2)
На шаге 2 продолжения j+1 алгоритм идет вниз из вершины s(v) по пути с меткой ? При буквальной реализации прохождение вдоль ? занимает время, пропорциональное |?|, числу символов в этом пути. Однако простой прием, именуемый скачком по счетчику, уменьшит время перехода до приблизительно пропорционального числу вершин в пути. Отсюда будет следовать, что время на все проходы вниз за фазу не превзойдет О(т).
Пусть g обозначает длину ?. Первый символ ? должен быть начальным только у одной дуги, выходящей из s(v). Пусть g' — число символов в этой дуге. Если g'
Эффект от использования скачков по счетчику будет в обеспечении перехода от вершины пути ? к другой вершине за константное время. Полное время прохода по пути становится при этом пропорциональным числу вершин, а не символов в нем.
Теорема 2. При использовании скачков по счетчику любая фаза алгоритма Укконена занимает время О(т).
Всего у нас т фаз, так что верна теорема, приведенная ниже.
Теорема 3. Суффиксные связи в алгоритме Укконена обеспечивают время работы O(m2).
Заметим, что временная граница для алгоритма О(т2) получена умножением временной оценки отдельной фазы О(т) на т (число фаз). Такое грубое умножение было необходимо, так как временной анализ проводился для отдельной фазы. После применения некоторых изменений в реализации, которые позволят провести временной анализ, выходящий за границы отдельных фаз, возможно достичь оценки времени работы O(т). [1]
Рассмотрим работу этого метода на конкретном примере.
Пример 5. Построить суффиксное дерево Т для строки S=’абвабабабб’.
Дополняем строку S символом $.
1 шаг – дерево Т1 (Рис.10)
Создаем лист с номером 1; дуга, идущая из корня имеет метку ‘а’.
Рис. 10
2 шаг – дерево Т2 (Рис.11)
Обрабатываем подстроку S[1..2]=’аб’. Эта подстрока имеет суффиксы ‘аб’, ‘б’.
Первый суффикс получается путем изменения метки ‘а’ на ‘аб’.
Второй суффикс создает лист с номером 2; дуга, идущая из корня имеет метку ‘б’.
Рис. 11
3 шаг – дерево Т3 (Рис.12)
Обрабатываем подстроку S[1..3]=’абв’. Эта подстрока имеет суффиксы ‘абв’, ‘бв’, ‘в’.
Обработка суффиксов аналогична обработке суффиксов на 2 шаге.
Рис. 12
4 шаг – дерево Т4 (Рис.13)
Обрабатываем подстроку S[1..4]=’абва’. Эта подстрока имеет суффиксы ‘абва’, ‘бва’, ‘ва’, ‘а’.
Первые три суффикса обрабатываются, как на 2 шаге построения. Последний суффикс является частью метки дуги, идущей к 1 листу, т.е. он уже представлен в дереве.
Рис. 13
5 шаг – дерево Т5 (Рис.14)
Обрабатываем подстроку S[1..5]=’абваб’. Эта подстрока имеет суффиксы ‘абваб’, ‘бваб’, ‘ваб’, ‘аб’, ‘б’.
Первые три суффикса обрабатываются, как на 2 шаге построения. Последние 2 суффикса уже представлены в дереве.
Рис. 14
6 шаг – дерево Т6 (Рис.15)
Обрабатываем подстроку S[1..6]=’абваба’. Эта подстрока имеет суффиксы ‘абваба’, ‘бваба’, ‘ваба’, ‘аба’, ‘ба’, ‘а’.
Первые три суффикса обрабатываются, как на 2 шаге построения. При обработке следующих двух суффиксов происходит создание суффиксных связей (на предыдущих шагах были следующие суффиксные связи: из корня в корень; суффиксные связи от листьев: от первого ко второму, от второго к третьему (Рис.14)).
При обработке суффикса ‘аба’ создается внутренняя вершина u, из которой исходит дуга в лист с меткой 4. При обработке суффикса ‘ба’ вновь создается внутренняя вершина v. Из двух последних действий видно, что суффиксная связь для вершины u равна v (S(u)=v).
Последний суффикс уже представлен в дереве.
Рис. 15
7, 8, 9 шаги - деревья Т7, Т8, Т9 (Рис.16)
Построение дерева происходит аналогично 5 шагу, т.е. происходит приписывание символов к меткам дуг, либо суффикс уже представлен в дереве.
Рис. 16
10 шаг - дерево Т10 (Рис.17)
Первые 5 суффиксов вводятся в дерево путем приписывания символа ‘б’ к уже имеющимся меткам дуг.
При обработке суффикса ‘абабб’ будет создана новая вершина на дуге, ведущей к 4 листу.
Рис. 17
Остановимся на обработке суффикса ‘бабб’. Требуется найти конец суффикса ‘баб’ в дереве. При обработке предыдущего суффикса была создана внутренняя вершина. Поднимаемся от нее вверх по дереву к ее отцу. Эта вершина-отец имеет суффиксную связь. Перейдем по ней, а не будем начинать с корня дерева, как в простом алгоритме. Часть суффикса ‘баб’ пройдена, и заведомо известно, что есть оставшаяся часть. Осталось выбрать дугу, идущую из вершины, в которую мы перешли по суффиксной связи. Оставшаяся часть суффикса может быть «исчерпана» меткой найденной дуги, а может быть и «не исчерпана». В первом случае срабатывает Правило 2, а во втором – выполняется переход вниз по дереву до тех пор, пока суффикс не будет обработан полностью. В любом случае создаются новая внутренняя вершина и лист, и к этой новой внутренней вершине пойдет суффиксная связь от вершины, образованной при обработке предыдущего суффикса.
При анализе суффиксов ‘абб’ и ‘бб’ новых внутренних вершин не создается (только вершины-листы), но суффиксные связи тоже определяются (Рис.18).
Рис. 18
11 шаг - дерево Т (Рис.19)
Все суффиксы строки S, кроме последнего вводятся в дерево путем приписывания символа ‘$’ к уже имеющимся меткам дуг.
Последний суффикс создает лист с номером 10; дуга, идущая из корня имеет метку ‘$’.
Рис. 19
1.3 Выводы по первой главе
1. В теоретической части выпускной работы определён набор основных определений: строка, алфавит, подстрока, префикс строки, суффикс строки, суффиксное дерево, метка пути, путевая метка, строковая глубина, неявное суффиксное дерево, суффиксная связь. Каждое определение проиллюстрировано примером.
2. Так же на конкретных примерах рассмотрены наивный алгоритм и алгоритм Укконена для построения суффиксных деревьев. Сделан вывод об их эффективности.
3. Кроме словесного описания для каждого алгоритма и соответствующего примера приведена графическая иллюстрация.
Глава 2. Программная реализация алгоритмов
построения суффиксных деревьев
2.1 Реализация наивного алгоритма построения суффиксного дерева на ЯП Паскаль
Для реализации наивного алгоритма была выбрана среда программирования Паскаль.
Для хранения суффиксного дерева выбрана динамическая структура дерево, описанная следующим образом:
Type PList = ^node;
node = Record
cnt:Integer;
d:Array[1..A] Of Record
first,last:Integer;
next:PList;
num:Integer;
End;
End;
Поле cnt – хранит в себе количество сыновей у вершины дерева.
Поле d – массив, элементы которого являются записями. Один элемент описывает отдельную вершину в дереве: поля firs, last – содержат в себе соответственно номер первого и последнего символов метки дуги; поле next указывает на сына; поле num содержит номер листа (если вершина является внутренней или корнем, то номер листа равен 0).
В данной программе используется 2 процедуры: процедура формирования суффиксного дерева, процедура вывода суффиксного дерева на экран.
Рис. 20
Временная сложность алгоритма О(п2) — это в предположении, что алфавит конечен, поэтому время обработки символа (или выбора дуги, выходящей из вершины) имеет постоянное значение (является константой). Действительно, мы обрабатываем m суффиксов, и для обработки каждого суффикса требуется выполнить количество операций, пропорциональное его длине.
2.2 Реализация алгоритма Укконена построения суффиксного дерева на ЯП Паскаль
Алгоритм Укконена также реализован на ЯП Паскаль.
Для хранения суффиксного дерева выбрана динамическая структура дерево:
Type PList = ^node;
node = Record
cnt:Integer;
d:Array[1..A] Of Record
first,last:Integer;
next:PList;
num:Integer;
End;
End;
Поле cnt – хранит в себе количество сыновей у вершины дерева.
Поле d – массив, элементы которого являются записями. Один элемент описывает отдельную вершину в дереве: поля firs, last – содержат в себе соответственно номер первого и последнего символов метки дуги; поле next указывает на сына; поле num содержит номер листа (если вершина является внутренней или корнем, то номер листа равен 0).
В данной программе используется 2 процедуры: процедура формирования суффиксного дерева, процедура вывода суффиксного дерева на экран.
Рис. 21
2.3 Выводы по второй главе
1. Программа, реализующая наивный алгоритм построения суффиксного дерева работает следующим образом:
? Вводится исходная строка.
? Далее строится дерево. Сначала в дерево вводится первый лист, соответствующий первому суффиксу строки; последующие суффиксы вводятся в дерево следующим образом: происходит поиск на совпадение первого символа суффикса и первого символа меток дуг, выходящих из вершин (поиск нужной дуги). Если такое совпадение нашлось, то происходит сравнение следующих символов суффикса и символов метки дуги, до тех пор, пока мы не найдем несовпадение. Если символы не совпадают, то в дерево вводится внутренняя вершина, у которой 2 «сына»: первый – часть оставшейся метки дуги, второй – символы суффикса, идущие после символа, не совпадающего с символами метки дуги.
? После построения дерева, результат выводится на экран в виде последовательностей символов, образующих суффиксы дерева.
2. Программа, реализующая алгоритм Укконена работает следующим образом:
? Вводится исходная строка.
? Далее строится дерево. Сначала в дерево вводится первый лист, состоящий из первого символа строки.
? Рассматриваем для исходной строки все подстроки, кроме первой подстроки, состоящей из первого символа. Для всех подстрок рассматриваем все суффиксы.
? Ищем соответствующую дугу. Здесь возможны три ситуации:
1) суффикс неявно представлен в дереве, т.е. не обрабатывается; 2) суффикс образуется обычным приписыванием последнего символа к метке дуги; 3) создается новая внутренняя вершина с суффиксной связью от вершины, образованной при обработке предыдущего суффикса. Эта связь поможет рационально обработать последующие суффиксы, если возникнет 2 ситуация. При ее возникновении необходимо подняться к отцу внутренней вершины, созданной последней. Эта вершина имеет суффиксную связь, перейдя по которой можно начать обработку суффикса не от корня, а от вершины, в которую ведет суффиксная связь. Суффиксные связи облегчают нахождение окончаний следующих суффиксов. После перехода по суффиксоной связи осуществляется так называемый «скачок по счетчику». Его смысл заключается в переходе от сравнения символов к сравнению длины меток дуг и оставшейся части суффикса, что позволяет осуществлять переходы от вершины-отца дерева к вершине-сыну до тех пор, пока не будет исчерпан суффикс.
? После построения дерева, результат выводится на экран в виде последовательностей символов, образующих суффиксы дерева.
Суффиксные связи в алгоритме Укконена обеспечивают время работы O(m2). Временная граница для алгоритма О(т2) получена умножением временной оценки отдельной фазы О(т) на т (число фаз). Такое грубое умножение было необходимо, так как временной анализ проводился для отдельной фазы. После применения некоторых изменений в реализации, которые позволят провести временной анализ, выходящий за границы отдельных фаз, возможно достичь оценки времени работы O(т).
Глава 3. Практическое применение суффиксных деревьев
Во введении работы перечисляются некоторые области применения суффиксных деревьев. В данной главе более подробно раскрыта задача о поиске подстроки в строке.
Идея поиска подстроки в строке.
Задан образец T длины m и текст S длины n, нужно найти все вхождения T в S за время О(n + m). Построим суффиксное дерево.
На первом шаге путем посимвольного сравнения находим выходящую из корня дугу, метка которой начинается с символа T[1], если такого совпадения не произошло => T не входит в S.
Затем осуществляем дальнейшие посимвольные сравнения Т с метками дуг.
При этом возможны три варианта:
1) Произошло несовпадение, в этом случае T не входит в S.
2) Полное совпадение символов, совпадение закончилось в вершине (последний символ Т совпал с последним символом очередной метки дуги) => единственное вхождение Т в S.
3) Полное совпадение символов, совпадение закончилось на каком-то на каком-то символе метки дуги => множественное вхождение T в S. Тогда фрагмент дерева, начиная с внутренней вершины, обходится методом поиска в глубину, чтобы найти метки листьев, указывающие на начальные позиции вхождений T в S.
Ключом к пониманию первого случая (когда все символы из T совпали с путем в S) служит такое наблюдение: T входит в S, начиная с позиции j, в том и только том случае, если T является префиксом S[j..n]. Но это происходит тогда и только тогда, когда T помечает начальную часть пути от корня до листа j. Именно по нему и проходит алгоритм сравнения.
Этот совпадающий путь единственен, так как никакие две дуги, выходящие из одной вершины, не имеют меток, начинающихся с одного и того же символа. И поскольку мы предположили, что алфавит конечен, работа в каждой вершине занимает константное время, а значит, время на проверку совпадения T с путем пропорционально длине T.
Задача поиска подстроки в строке реализована программно. При запуске программы сначала вводится строка-образец S, т.е. где будем искать, также вводится строка Т.
Для строки S строится суффиксное дерево. Затем осуществляется поиск строки Т в построенном суффиксном дереве, описанным выше способом.
В результате работы программы выводится сообщение о том входит или нет искомая строка в строку-образец. (Рис.22, 23)
Рис. 22
Рис. 23
.
Заключение
В данной выпускной квалификационной работе были рассмотрены некоторые алгоритмы, формирующие суффиксные деревья для конкретных строк.
Изучение и анализ соответствующих алгоритмов начинается с выделения набора основных определений, правил, теорем. В исследовании каждое из них, а так же работа рассмотренных алгоритмов проиллюстрированы на конкретных примерах, что позволяет понять механизм достаточно сложных абстрактных операций.
Что касается эффективности алгоритмов:
1. Для наивного алгоритма временная сложность О(п2) — это в предположении, что алфавит конечен, поэтому время обработки символа (или выбора дуги, выходящей из вершины) имеет постоянное значение (является константой).
2. Суффиксные связи в алгоритме Укконена обеспечивают время работы O(m2). Временная граница для алгоритма О(т2) получена умножением временной оценки отдельной фазы О(т) на т (число фаз). Такое грубое умножение было необходимо, так как временной анализ проводился для отдельной фазы. После применения некоторых изменений в реализации, которые позволят провести временной анализ, выходящий за границы отдельных фаз, возможно достичь оценки времени работы O(т).
Кроме того, в работе приведен практический пример приложения суффиксных деревьев для решения задачи поиска подстроки в строке.
Но суффиксные деревья применяются не только в областях близких к информатике, они также могут эффективно применяться и при изучении таких наук, как молекулярная биология для работы с молекулярными последовательностями (строками), где эффективность обработки информации играет не последнюю роль.
Таким образом, полученные результаты позволяют сделать вывод о том, что задачи, поставленные перед работой, выполнены и цель достигнута.
Библиографический список
1. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах: информатика и вычислительная биология: информатика и вычислительная биология [Текст]: пер. с англ. И. В. Романовского. – СПб.: Невский диалект; БХВ-Петербург, 2003. – 654 с; ил.
2. Гэри, М., Джонсон, Д. Вычислительные машины и труднорешаемые задачи [Текст]: пер. с. англ. — М.: Мир, 1982. – 416 с.
3. Окулов, С. М. Алгоритмы обработки строк [Текст] / С.М. Окулов. – М.: БИНОМ. Лаборатория знаний, 2009. – 255с.: ил.
4. Суффиксное дерево. http://ru.wikipedia.org/wiki/Суффиксное_дерево
5. Суффиксные деревья. http://www.intuit.ru/department/algorithms/algoconstran/8/
Приложение 1
Программный код Наивного алгоритма
program algoritm1;
const A=33;
Type PList = ^node;
node = Record
cnt:Integer; {Количество сыновей у вершины дерева}
d:Array[1..A] Of Record {Предполагаем, что алфавит конечен, есть отношение порядка}
first,last:Integer; {Номера первого и последнего символов подстроки - метки дуги}
next:PList; {Указатель на вершину - сына}
num:Integer; {Метка листа. Для внутренней вершины, включая корень, она имеет значение 0}
End;
End;
Var S:String;
n:Integer;
tree:PList;
Procedure TreeSuf1;
Var w,v: PList;
i,j,l,t,st:Integer;
bl:Boolean;
Begin
S:=S+'$';
n:=Length(S); {Первый шаг алгоритма - в корне дерева дается описание дуги, идущей в вершину с меткой "1"}
st:=1; {Номер листа}
New(tree);
Tree^.cnt:=1;
Tree^.d[1].first:=1;
Tree^.d[1].last:=n;
Tree^.d[1].next:=Nil;
Tree^.d[1].num:=st;
{Суффикс S[i..n] описываем (представляем) в дереве}
For i:=2 To n Do Begin
w:=tree;
t:=i;
bl:=False;
While Not bl Do Begin {Пока не сформирован лист, соответствующий суффиксу, выполняем действия цикла}
j:=1;
l:=0;
While (l=0)And(j<=w^.cnt) Do Begin {Просматриваем дуги, выходящие из вершины, на которую "смотрит" W^}
If S[w^.d[j].first]=S[t] Then l:=j; {Дуга найдена - первый символ суффикса совпадает с первым символом метки дуги}
j:=j+1;
End;
If l=0 Then Begin {Дуга не найдена - создаем новую вершину-лист, отцом которой является вершина w^}
w^.cnt:=w^.cnt+1;
st:=st+1;
bl:=True; {Суффикс обработан}
w^.d[w^.cnt].next:=Nil;
w^.d[w^.cnt].num:=st;
w^.d[w^.cnt].first:=t;
w^.d[w^.cnt].last:=n;
End
Else Begin {Дуга найдена - сравниваем символы суффикса и метки дуги}
j:=1;
While (w^.d[l].first+j<=w^.d[l].last) And (S[t+j]=S[w^.d[l].first+j]) Do
j:=j+1;
If w^.d[l].first+j<=w^.d[l].last Then
Begin {Создаем новую внутреннюю вершину}
st:=st+1;
New(v);
V^.cnt:=2; {У вершины два сына}
V^.d[1].next:=w^.d[l].next;{Новая метка дуги - совпадающая часть суффикса и старой метки дуги}
V^.d[1].num:=w^.d[l].num;
V^.d[1].first:=w^.d[l].first+j;
V^.d[1].last:=w^.d[l].last;
V^.d[2].next:=Nil;{Оставшаяся часть суффикса является меткой дуги, идущей к листу с номером обрабатываемого суффикса}
V^.d[2].num:=st;
V^.d[2].first:=t+j;
V^.d[2].last:=n;{Корректируем описание вершины - отца}
W^.d[l].next:=v;
W^.d[l].last:=w^.d[l].first+j-1;
W^.d[l].num:=0;
bl:=True; {Суффикс обработан}
End
Else Begin{Переходим к следующей вершине дерева - часть суффикса полностью совпала с меткой дуги}
t:=t+w^.d[l].last-w^.d[l].first+1;
w:=w^.d[l].next;
End;
End; {Конец обработки найденной дуги}
End; {Конец цикла по обработке суффикса}
End; {Конец цикла по суффиксам}
End;
Procedure Print(pt:Plist;k:integer);
var i,t1,t2:integer;
begin
if ptnil then
for i:=1 to pt^.cnt do begin
t1:=pt^.d[i].first;
t2:=pt^.d[i].last;
writeln(copy(s,t1,t2-t1+1):k);
print(pt^.d[i].next,k+10);
end;
end;
begin
writeln('Введите строку');
readln(S);
TreeSuf1;
Writeln;
Writeln('Суффиксное дерево');
Print(tree,length(s)+1);
readln;
end.
Приложение 2
Программный код алгоритма Укконена
program algoritm2;
const A=33;
Type PList = ^node;
node = Record
cnt:Integer;
parent:PList;
sufn:Plist;
d:Array[1..A] Of Record
first,last:Integer;
next:PList;
num:Integer;
End;
End;
Var S:String;
n:Integer;
tree:PList;
Procedure Form2;
Var w,v: PList;
i,j,l,t,st,k:Integer;
bl,bl1:Boolean;
Begin
S:=S+'$';
n:=Length(S);
st:=1;
New(tree); {Создаем первую вершину}
Tree^.cnt:=1;
Tree^.d[1].first:=1;
Tree^.d[1].last:=1;
Tree^.d[1].next:=Nil;
Tree^.d[1].num:=st;
For i:=2 To n Do Begin {Обрабатываем строки S[1..i] - изменяем дерево суффиксов}
k:=1; {При реализации Правила 1 значение k начинает изменяться не с 1}
bl:=False; {Признак того, что следующие суффиксы для больших значений k обрабатывать не следует (Правило 3)}
While (k<=i) and (Not bl) Do Begin {Обрабатываем суффикс S[k..i]}
w:=tree;
t:=k;
bl1:=false; {Признак обработки суффикса}
While Not bl1 do Begin
j:=1;
l:=0;{Поиск дуги, начинающейся с символа S[t]}
While (l=0)And(j<=w^.cnt) Do Begin
If S[w^.d[j].first]=S[t] Then l:=j; {Дуга найдена - первый символ суффикса совпадает с первым символом метки дуги}
j:=j+1;
End;
If l=0 Then Begin {Дуга не найдена - создаем новую вершину-сына у w^ (Правило 2)}
bl1:=true;{Суффикс обработан}
w^.cnt:=w^.cnt+1;
st:=st+1;
w^.d[w^.cnt].next:=Nil;
w^.d[w^.cnt].num:=st;
w^.d[w^.cnt].first:=t;
w^.d[w^.cnt].last:=i;
End
Else Begin {Дуга найдена - сравниваем символы суффикса и метки дуги}
j:=0;
While (w^.d[l].first+j<=w^.d[l].last) And ((t+j)<=i) and (S[t+j]=S[w^.d[l].first+j]) Do
j:=j+1;
If t+j=i+1 Then
Begin {Сравнение завершилось полным исчерпанием суффикса (Правило 3). Суффикс обработан}
bl:=true;
bl1:=true;
End
else if w^.d[l].first+j<=w^.d[l].last then Begin {Если метка дуги не закончилась, то надо создавать новую внутреннюю вершину (Правило 2)}
st:=st+1;
New(v);
V^.cnt:=2; {У вершины два сына}
V^.d[1].next:=w^.d[l].next;{Новая метка дуги - совпадающая часть суффикса и старой метки дуги}
V^.d[1].num:=w^.d[l].num;
V^.d[1].first:=w^.d[l].first+j;
V^.d[1].last:=w^.d[l].last;
V^.d[2].next:=Nil;{Оставшаяся часть суффикса является меткой дуги, идущей к листу с номером обрабатываемого суффикса}
V^.d[2].num:=st;
V^.d[2].first:=t+j;
V^.d[2].last:=i;{Корректируем описание вершины - отца}
W^.d[l].next:=v;
W^.d[l].last:=w^.d[l].first+j-1;
W^.d[l].num:=0;
bl1:=True; {Суффикс обработан}
End
Else
if w^.d[l].num0 then
Begin{Переходим к следующей вершине дерева - часть суффикса полностью совпала с меткой дуги}
w^.d[l].last:=w^.d[l].last+1;
bl1:=true;
End
else Begin
t:=t+w^.d[l].last-w^.d[l].first+1;
w:=w^.d[l].next;
End;
End;
End;
k:=k+1;
End;
End;
End;
Procedure Print(pt:Plist;k:integer);
var i,t1,t2:integer;
begin
if ptnil then
for i:=1 to pt^.cnt do begin
t1:=pt^.d[i].first;
t2:=pt^.d[i].last;
writeln(copy(s,t1,t2-t1+1):k);
print(pt^.d[i].next,k+10);
end;
end;
begin
writeln('Введите строку');
readln(S);
Form2;
writeln('Суффиксное дерево');
Print(tree,length(s)+1);
readln;
end.
Приложение 3
Программный код поиска подстроки в строке
program Poisk ;
const A=33;
Type PList = ^node;
node = Record
cnt:Integer;
d:Array[1..A] Of Record
first,last:Integer;
next:PList;
num:Integer;
End;
End;
Var S,T:String;
n:Integer;
tree:PList;
Procedure Form;
Var w,v: PList;
i,j,l,t,st:Integer;
bl:Boolean;
Begin
S:=S+'$';
n:=Length(S);
st:=1;
New(tree);
Tree^.cnt:=1;
Tree^.d[1].first:=1;
Tree^.d[1].last:=n;
Tree^.d[1].next:=Nil;
Tree^.d[1].num:=st;
For i:=2 To n Do Begin
w:=tree;
t:=i;
bl:=False;
While Not bl Do Begin
j:=1;
l:=0;
While (l=0)And(j<=w^.cnt) Do Begin
If S[w^.d[j].first]=S[t] Then l:=j;
j:=j+1;
End;
If l=0 Then Begin
w^.cnt:=w^.cnt+1;
st:=st+1;
bl:=True;
w^.d[w^.cnt].next:=Nil;
w^.d[w^.cnt].num:=st;
w^.d[w^.cnt].first:=t;
w^.d[w^.cnt].last:=n;
End
Else Begin
j:=1;
While (w^.d[l].first+j<=w^.d[l].last) And (S[t+j]=S[w^.d[l].first+j]) Do
j:=j+1;
If w^.d[l].first+j<=w^.d[l].last Then
Begin
st:=st+1;
New(v);
V^.cnt:=2;
V^.d[1].next:=w^.d[l].next
V^.d[1].num:=w^.d[l].num;
V^.d[1].first:=w^.d[l].first+j;
V^.d[1].last:=w^.d[l].last;
V^.d[2].next:=Nil;
V^.d[2].num:=st;
V^.d[2].first:=t+j;
V^.d[2].last:=n;
W^.d[l].next:=v;
W^.d[l].last:=w^.d[l].first+j-1;
W^.d[l].num:=0;
bl:=True;
End
Else Begin
t:=t+w^.d[l].last-w^.d[l].first+1;
w:=w^.d[l].next;
End;
End;
End;
End;
End;
Procedure Print(pt:Plist;k:integer);
var i,t1,t2:integer;
begin
if ptnil then
for i:=1 to pt^.cnt do begin
t1:=pt^.d[i].first;
t2:=pt^.d[i].last;
writeln(copy(s,t1,t2-t1+1):k);
print(pt^.d[i].next,k+10);
end;
end;
Procedure Obhod(t:Plist;k:integer);
Var i:integer;
begin
if t^.cnt=0 then writeln(t^.d[k].num) else
for i:=1 to t^.cnt do Obhod(t^.d[k].next,k);
end;
Procedure Poisk(tree:Plist;k:integer);
Var i,j:integer;f:boolean;
Begin
n:=length(S);
k:=1;
f:=false;
repeat
i:=1;
while (i<=tree^.cnt) and (S[tree^.d[i].first]T[k]) do i:=i+1;
if i>tree^.cnt then begin writeln ('Строка Т не встречается в строке S');
f:=true;
end
else begin
j:=1;
tree:=tree^.d[i].next;
while (tree^.d[i].first+j<=tree^.d[i].last) and (S[tree^.d[i].first+j]=T[k+j]) and (k+j<=n) do j:=j+1;
if k+j>n then begin
if tree^.d[i].num=0 then writeln(tree^.d[i].num)
else Obhod(tree,i);
f:=true;
end
else if tree^.d[i].first+j>tree^.d[i].last then k:=k+j
else begin
writeln('net')
f:=true;
end;
end;
until f;
end;
begin
writeln('Введите строку');
readln(S);
Form;
Writeln;
Writeln('Суффиксное дерево');
Print(tree,length(s)+1);
Writeln;
Writeln('Введите строку для поиска');
Readln(T);
Poisk(tree,1);
readln;
end.