Анализ и разработка способов индексирования текстов на основе обобщенных и неплотных суффиксных деревьев

• Автор: Андрианов, Игорь Александрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Санкт-Петербург
• Количество страниц: 160 с. : ил.

1.1 Обзор применений суффиксных деревьев для поиска в текстах

1.2 Суффиксные деревья основные понятия, определения и обозначения 1.3 Формулировка решаемых прикладных задач

1.3.1 Задача ускорения поиска по регулярным выражениям

1.3.2 Задача о поиске по сходству в программном коде

1.4. Анализ существующих алгоритмов и схем представления в памяти суффиксных деревьев
1.4.1 Обзор алгоритмов построения и способов представления суффиксных деревьев в оперативной памяти.

1.4.2 Алгоритм Укконена

1.4.3 Обзор алгоритмов построения и способов представления суффиксных деревьев во внешней памяти

1.5 Постановка задач дальнейшего исследования Выводы по главе

ГЛАВА 2. Разработка структур хранения обобщенных суффиксных деревьев, эффективных алгоритмов построения и поиска в них

2.1. Анализ и модификация способов представления узлов СД и ОСД в памяти

2.2. Повышение эффективности построения и использования СД путм перехода к алфавиту меньшего размера
2.2.1 Выбор размера нового алфавита
2.2.2 Построение СД при кодировании текста с помощью префиксных кодов
2.3 Реализация операций исходного ОСД на основе ОСД над кодированным текстом
2.3.1 Определение интерфейсных операций АТД ОСД
2.3.2 Реализация операций для кодов фиксированной длины
2.3.3 Реализация операций для префиксных кодов переменной длины Выводы по главе
ГЛАВА 3. Разработка алгоритмов построения и использования обобщенных суффиксных деревьев во внешней памяти.
3.1 Построение неплотных суффиксных деревьев с ограничениями на позиции суффиксов
3.2 Разработка алгоритма построения СД во внешней памяти на основе алгоритма линейного построения НСД
3.3 Адаптация алгоритма для случая исходных данных во внешней памяти
3.3.1 Модификация структуры дерева
3.3.2 Определение соотношения между размером буфера для исходных данные и памятью для НСД
3.4 Сравнение алгоритма построения СД во внешней памяти с аналогами Выводы по главе
ГЛАВА 4. Применение полученных результатов для практических задач
4.1 Применение индекса на основе ОСД для ускорения поиска по регулярным выражениям
4.1.1 Применение суффиксных деревьев для ускорения поиска по регулярным выражениям при использовании конечных автоматов
4.1.2 Использование граммного подхода для ускорения поиска по РВ
4.1.3 Адаптация граммного подхода к использованию ОСД
4.2 Применение индекса на основе ОСД для поиска по сходству в программном коде
4.2.1 Методика поиска по сходству в программном коде на основе сравнения промежуточных результатов компиляции
4.2.2 Использование обобщенных суффиксных деревьев для обнаружения совпадающих фрагментов текстов
4.2.3 Применение результатов поиска по сходству в автоматической проверяющей системе и для поиска дублирующегося кода
4.3 Реализация индексного метода доступа для СУБД
4.3.1 Применение высокоуровневых средств СУБД при реализации новых индексных методов доступа
4.3.2 Особенности программной реализации индекса
4.4 Анализ экспериментальных результатов
Выводы по главе 4
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Важным вопросом при построении ИПС является выбор минимального индексируемого элемента. Согласно Выбор минимальной индексирующей единицы зависит от того, насколько полно необходимо реализовать возможность . В большой коллекции, такой, как Интернет, нечеткий поиск требует больших накладных расходов и приводит к зашумленности результатов. Именно поэтому ПС всехмирной паутины используют поиск лишь с учетом грамматических форм. Для случая текстовых коллекций средних размеров, являющихся объектом диссертационного исследования, декомпозиция на основе подстрок вполне применима и позволяет осуществить ряд видов поиска, не реализуемых для словарных систем поиск по сходству, по регулярным выражениям и некоторые другие. Одной из наиболее универсальных структур данных, которые могут быть использованы в случае декомпозиции на основе подстрок, является суффиксное дерево. Подтвердим это конкретными примерами задач, для решения которых могут использоваться суффиксные деревья или их обобщения несколько десятков применений СД описано в , см. Самый простой вариант использования СД применение его для поиска подстроки. Сложность поиска подстроки р в строке б составляет 0росс, где р длина р, осс число вхождений . АхоКорасика . Операция поиска подстроки лежит в основе т. Соответственно, индекс на базе СД можно применять как альтернативу специализированным граммным индексам, например, в главе 4 данной диссертации это рассмотрено более подробно при решении одной из прикладных задач. Ещ одной задачей, эффективно решаемой с помощью СД, является поиск наибольшей общей подстроки двух строк. Интересно заметить, что ещ до появления аппарата суффиксных деревьев Д. Кнут высказывал предположение, что данная задача не может быть решена с линейной временной сложностью. С использованием же СД данная задача решается сравнительно легко. Вариант решения данной задачи для случая, когда дерево не помещается целиком в оперативную память, описывается в 8. СД применимы также и для поиска наибольшей общей подстроки более чем двух исходных строк с временной сложностью, пропорциональной их суммарной длине . Расширением предыдущей задачи является поиск общих подстрок длиной не менее заданного значения к. В работе К. Моностори и др. Кроме поиска наибольшей общей подстроки, для ряда приложений требуется поиск часто встречающихся подстрок заданного размера, т. С использованием СД данная задача также решается с линейной временной сложностью . Важной разновидностью информационного поиска является нечткий поиск ,2, т. Чангом и Лоулером , также основывается на СД. Ряд алгоритмов, базирующихся на суффиксных деревьях, используют следующий факт. Выполнив предварительную обработку построенного СД за линейное время, впоследствии для любых двух его узлов возможно за константное время находить узел их ближайшего общего предка . Известны несколько алгоритмов для этого описанный в , алгоритмы ШибераВишкина , ХарелаТарьяна , алгоритм, предложенный М. Фарахом и др. Это позволяет решать такие задачи, как поиск симметричных структур палиндромов 4, поиск подстрок, содержащих подстановочные символы т. В статье описывается построение индекса на основе СД для ускорения поиска по регулярным выражениям РВ и доказывается, что при этом среднее время поиска с помощью предложенного алгоритма асимптотически меньше длины исходного текста т. РВ пропорционально их длине. Ещ одним из применений СД является сжатие данных. Так,с помощью СД успешно реализуется известный метод сжатия Зива и Лемпела ,7, что дополнительно подтверждает высокую степень универсальности данной структуры для обработки текстов. Интересно, что кроме собственно сжатия, данный алгоритм находит применение для оценки энтропии исходных текстов, например, с целью их классификации . В последнее время суффиксные деревья находят применение в области, известной как ii. Так, в см. Образец зависимых близких слов это выражение вида , , С, выражающее правило если текст содержит подстроку а и следующую за ней подстроку с расстоянием между ними не более символов, то свойство С будет выполняться с высокой вероятностью.