Введение
ГЛАВА 1. Анализ способов индексирования текстов на основе суффиксных деревьев. Постановка задач исследования 12
1.1 Обзор применений суффиксных деревьев для поиска в текстах 12
1.2 Суффиксные деревья: основные понятия, определения и обозначения 15
1.3 Формулировка решаемых прикладных задач 20
1.3.1 Задача ускорения поиска по регулярным выражениям 20
1.3.2 Задача о поиске по сходству в программном коде 24
1.4. Анализ существующих алгоритмов и схем представления в памяти суффиксных деревьев 28
1.4.1 Обзор алгоритмов построения и способов представления суффиксных деревьев в оперативной памяти. 28
1.4.2 Алгоритм Укконена . 30
1.4.3 Обзор алгоритмов построения и способов представления суффиксных деревьев во внешней памяти 37
1.5 Постановка задач дальнейшего исследования 42
Выводы по главе 1 45
ГЛАВА 2. Разработка структур хранения обобщенных суффиксных деревьев, эффективных алгоритмов построения и поиска в них 47
2.1. Анализ и модификация способов представления узлов СД и ОСД
в памяти 47
2.2. Повышение эффективности построения и использования СД путём перехода к алфавиту меньшего размера / 55
2.2.1 Выбор размера нового алфавита 61
2.2.2 Построение СД при кодировании текста с помощью префиксных кодов 64
2.3 Реализация операций исходного ОСД на основе ОСД над кодированным текстом 68
2.3.1 Определение интерфейсных операций АТД "ОСД" 68
2.3.2 Реализация операций для кодов фиксированной длины 72
2.3.3 Реализация операций для префиксных кодов переменной длины 77
Выводы по главе 2 80
ГЛАВА 3. Разработка алгоритмов построения и использования обобщенных суффиксных деревьев во внешней памяти . 81
3.1 Построение неплотных суффиксных деревьев с ограничениями на позиции суффиксов 81
3.2 Разработка алгоритма построения СД во внешней памяти на основе алгоритма линейного построения НСД 88
3.3 Адаптация алгоритма для случая исходных данных во внешней памяти 93
3.3.1 Модификация структуры дерева 93
м 3.3.2 Определение соотношения между размером буфера для исходных данные и памятью для НСД 95
3.4 Сравнение алгоритма построения СД во внешней памяти с аналогами 98
Выводы по главе 3 104
ГЛАВА 4. Применение полученных результатов для практических задач 106
4.1 Применение индекса на основе ОСД для ускорения поиска по регулярным выражениям 106
4.1.1 Применение суффиксных деревьев для ускорения поиска по регулярным выражениям при использовании конечных автоматов 106
4.1.2 Использование граммного подхода для ускорения поиска поРВ 112
4.1.3 Адаптация граммного подхода к использованию ОСД 115
4.2 Применение индекса на основе ОСД для поиска по сходству в программном коде 116
4.2.1 Методика поиска по сходству в программном коде на основе сравнения промежуточных результатов компиляции 116
4.2.2 Использование обобщенных суффиксных деревьев для обнаружения совпадающих фрагментов текстов 121
4.2.3 Применение результатов поиска по сходству в автоматической проверяющей системе и для поиска дублирующегося кода 122
Ofr 4.3 Реализация индексного метода доступа для СУБД PostgreSQL 126
4.3.1 Применение высокоуровневых средств СУБД при реализации новых индексных методов доступа 126
4.3.2 Особенности программной реализации индекса 129
4.4 Анализ экспериментальных результатов 132
Выводы по главе 4 135
Заключение 137
Список литературы
