Анализ и разработка способов индексирования текстов на основе обобщенных и неплотных суффиксных деревьев тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Андрианов, Игорь Александрович

• Андрианов, Игорь Александрович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Андрианов, Игорь Александрович

Список сокращений

ВВЕДЕНИЕ

ГЛАВА 1. Анализ способов индексирования текстов на основе суффиксных деревьев. Постановка задач исследования

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

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

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

1.3.2 Задача о поиске по сходству в программном коде 24 1.4. Анализ существующих алгоритмов и схем представления в памяти суффиксных деревьев

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

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

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

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

Выводы по главе

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

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

2.2. Повышение эффективности построения и использования СД путём перехода к алфавиту меньшего размера /

2.2.1 Выбор размера нового алфавита

2.2.2 Построение СД при кодировании текста с помощью префиксных кодов 64 2.3 Реализация операций исходного ОСД на основе ОСД над кодированным текстом

2.3.1 Определение интерфейсных операций АТД "ОСД"

2.3.2 Реализация операций для кодов фиксированной длины

2.3.3 Реализация операций для префиксных кодов переменной длины 77 Выводы по главе

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

3.1 Построение неплотных суффиксных деревьев с ограничениями на позиции суффиксов

3.2 Разработка алгоритма построения СД во внешней памяти на основе алгоритма линейного построения НСД

3.3 Адаптация алгоритма для случая исходных данных во внешней памяти

3.3.1 Модификация структуры дерева

3.3.2 Определение соотношения между размером буфера для исходных данные и памятью для НСД

3.4 Сравнение алгоритма построения СД во внешней памяти с аналогами 98 Выводы по главе 3 10'

ГЛАВА 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 Реализация индексного метода доступа для СУБД PostgreSQL

4.3.1 Применение высокоуровневых средств СУБД при реализации новых индексных методов доступа

4.3.2 Особенности программной реализации индекса 129 4.4 Анализ экспериментальных результатов

Выводы по главе

Введение диссертации (часть автореферата) на тему «Анализ и разработка способов индексирования текстов на основе обобщенных и неплотных суффиксных деревьев»

В современном обществе важнейшую роль играют системы информационного поиска (ИПС), позволяющие осуществлять эффективный поиск нужных сведений в море информации. Подобные системы постоянно совершенствуются как за счёт прогресса в области аппаратных средств, так и за счёт модернизации заложенных в них структур и алгоритмов. Совершенствуются и сами подходы к отбору информации, позволяя пользователю более гибко задавать то, что он хочет найти. Так, в дополнение к поиску слов и грамматических форм [35], развиваются возможности нечёткого поиска [37], использование в запросах шаблонов различного вида [53], поиск с учётом семантики [31] и др.

Как видим, направлений поиска очень много. Поэтому уточним само понятие информационного поиска и конкретизируем направление исследования.

Согласно ГОСТ 7.73-96 [24], информационный поиск - это "действия, методы и процедуры, позволяющие осуществлять отбор определённой информации из массива данных". В данной работе речь идет о полнотекстовом поиске, который в ГОСТ определен как "автоматизированный документальный поиск, при котором в качестве поискового образа документа используется его полный текст или существенные части текста".

Некоторые виды поиска, например, словарный, на сегодняшний момент хорошо проработаны теоретически и реализованы в огромном количестве поисковых программ. Несколько хуже обстоит дело с другими видами поиска, которые не менее важны и востребованы на практике - поиск по различным шаблонам, нечеткий поиск, в том числе по сходству длинных фрагментов текста и др. Все эти задачи не предполагают естественного разбиения текста на некоторые составные единицы (слова, строки и т.п.), т. е. сам термин «текстовый документ» рассматривается в широком смысле как произвольная последовательность символов, например, обычный текст на естественном языке, html-документ, исходный текст компьютерной программы, её исполняемый код и др.

Вопросам проектирования структур данных и алгоритмов таких видов информационного поиска посвящены работы Р.Баеза-Ятеса, Г.Гоннета, Д.Гасфилда, Э.Укконена, С.Куртца и др. Из отечественных публикаций на эту тему можно выделить фундаментальные работы В.М.Глушкова по теории автоматов, а также работы Л.М.Бойцова, Е.В.Андриенко, О.С.Бартунова, Т.Г.Сигаева и др., посвященные непосредственно информационному поиску.

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

Имеется большое количество способов организации индексов, использующих различные структуры данных и алгоритмы. Одним из перспективных подходов является использование структур данных на основе суффиксных деревьев (СД) [5]. СД представляет собой одну из наиболее универсальных структур данных для поддержки поиска в текстах - известно не менее нескольких десятков задач поиска, эффективно решаемых с её помощью. Однако, в силу своей универсальности СД имеют сравнительно высокие требования к памяти. Поэтому представляется целесообразным использовать данную структуру для индексирования коллекций документов средних размеров (до нескольких гигабайт).

Исследование, выполненное в настоящей работе, направлено на разработку индексов для эффективной реализации поиска на основе СД. В качестве практических задач, которые решены на основе выполненных теоретических разработок, рассматривается поиск по шаблонам, заданным в виде регулярных выражений, а также поиск по сходству фрагментов программного кода. Возможны и другие применения разработанных структур и алгоритмов. Результаты исследования применены при разработке нового вида индекса для свободно распространяемой СУБД PostgreSQL и внедрены в реальные прикладные системы.

Целью диссертационной работы является повышение эффективности поиска путем индексирования исходных текстов с использованием обобщенных и неплотных суффиксных деревьев. Для достижения поставленной цели в данной диссертационной работе решаются следующие задачи:

1. Анализ существующих подходов к решению рассматриваемых задач; анализ работ, посвященных построению и использованию индексов на основе суффиксных деревьев.

2. Исследование обобщенных и неплотных суффиксных деревьев, разработка структур и алгоритмов для эффективной реализации индексов для случаев как оперативной, так и внешней памяти.

3. Применение полученных теоретических результатов для решаемых задач поиска.

4. Программная реализация индексов; получение экспериментальных данных, сравнение их с теоретическими оценками; сравнение полученных реализаций с аналогами.

5. Внедрение полученных результатов в деятельность конкретных организаций.

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

В качестве предмета исследования выступают способы организации и алгоритмы обработки индексов на основе обобщенных и неплотных суффиксных деревьев.

В качестве методов исследования в работе использовались методы теории множеств, теории графов, анализа алгоритмов, теории автоматов, математического анализа. Кроме того, применялись методы разработки программного обеспечения с использованием объектно-ориентированного подхода.

Научная новизна работы заключается в следующем:

1. Разработан метод эффективного построения и использования обобщенных суффиксных деревьев, основанный на кодировании символов исходного текста с помощью алфавита существенно меньшего размера. Временная сложность построения ОСД уменьшается с 0(п-|1|) до 0(n-log(|I|)), поиска подстроки - с 0(m-|S|) до 0(m-log(|2|)), где п - длина текста, m - длина подстроки, |1| - размер исходного алфавита. Требования к памяти не изменяются.

2. Предложено использовать оптимальные префиксные коды с целью дополнительного снижения временной сложности построения дерева и поиска в нем, а также увеличения возможного размера входных данных. Для построения дерева над сжатым текстом модифицирован алгоритм Каркайнена и Укконена.

3. Обоснована целесообразность использования неплотных суффиксных деревьев применительно к решаемым задачам поиска в целях ускорения построения индексов и внесения управляемости в расход памяти. Предложено обобщение алгоритма Укконена для построения неравномерно неплотных суффиксных деревьев, доказана его корректность, получены асимптотические оценки сложности.

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

Практическая значимость результатов диссертации заключается в следующем:

1. На основе выполненных исследований реализованы индексы для ускорения поиска по регулярным выражениям и поиска по сходству фрагментов текста как для оперативной, так и для внешней памяти. Для случая хранения данных в полях СУБД разработан и внедрен новый вид индекса для одной из СУБД с открытым исходным кодом.

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

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

4. Разработано прикладное ПО, позволяющее существенно сократить время поиска по сравнению с известными программными продуктами, решающими аналогичные задачи.

Прикладные результаты данной работы внедрены в НОУ "УЦ "Мезон" и ООО "Вологодский трубопрокатный завод". Для НОУ «УЦ «Мезон» улучшена фильтрация электронных сообщений по наборам регулярных выражений и реализовано дополнение к автоматической проверяющей системе для поиска подозрительно похожего программного кода. В ООО "Вологодский трубопрокатный завод" данные результаты применены для поиска дублирующегося программного кода в разрабатываемом ПО, а также для ускорения поиска по LIKE-шаблонам в текстовых полях СУБД.

Кроме того, результаты диссертационной работы используются в учебном процессе кафедры автоматики и вычислительной техники Вологодского государственного технического университета в автоматической проверяющей системе и при преподавании курсов "Структуры и алгоритмы обработки данных", "Программирование на языке высокого уровня".

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Андрианов, Игорь Александрович

Выводы по главе 4

1. Поиск дублирующихся подстрок в откомпилированном коде позволяет: а), выявлять такие изменения в исходном коде, как изменение форматирования, смена имен идентификаторов, вставка неиспользуемых переменных или кода, простые изменения конструкций языка на альтернативные и др. б). При этом легко выполняется адаптация к новым языкам программирования и их диалектам,

2. Проанализирован способ Баеза-Ятеса к ускорению поиска по РВ, расширен класс префиксных РВ, поиск которых выполняется с гарантированной эффективностью. Предложены дополнения в алгоритм Баеза-Ятеса и Гоннета [53] для распознавания таких выражений,

3. Проанализирован граммный способ к ускорению поиска по РВ и показано, что в качестве структуры данных индекса может выступать ОСД. Такая замена даёт определённые преимущества: объединение двух подходов, эффективных для разных подмножеств РВ, на основе одной структуры данных и базовых алгоритмов работы с ней; возможность реализации динамического обновления индекса при изменении входных данных,

4. Разработан индекс для СУБД PostgreSQL, ускоряющий поиск по РВ в среднем более чем на порядок и при этом поддерживающий динамическое изменение данных. С целью сокращения затрат на реализацию предложен и использован подход, основанный на применении высокоуровневых средств СУБД для управления не только исходными данными, но и данными индексной структуры,

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

6. Внедрение полученных результатов в реальные информационные системы доказывает их практическую применимость и значимость.

ЗАКЛЮЧЕНИЕ

В диссертационной работе проведена разработка структур хранения, а также эффективных алгоритмов построения и использования обобщенных суффиксных деревьев для случаев как оперативной, так и внешней памяти. Можно выделить следующие основные результаты:

1. Кодирование исходного текста с использованием алфавита меньшей мощности позволяет снизить временную сложность построения суффиксного дерева с 0(п-|Е|) до 0(n.log(|E|)), поиска подстроки - с 0(m-|E|) до 0(m-log(|E|)), где п -длина текста, ш - длина подстроки, Щ - размер алфавита. Соответственно ускоряется и время поиска по дереву. Требования к оперативной памяти при этом остаются прежними.

2. Использование оптимальных префиксных кодов позволяет дополнительно снизить сложность построения дерева и поиска в нем в соответствии со степенью сжатия исходного текста. Для построения такого дерева предложена модификация алгоритма Каркайнена-Укконена.

3. Обобщен алгоритм Укконена для построения неравномерно неплотных суффиксных деревьев. По сравнению с существующим подходами множество суффиксов, входящее в дерево, может быть задано более гибко.

4. Суффиксное дерево, построенное над закодированным текстом, эквивалентно оригинальному дереву (построенному над исходным текстом). Множество элементарных операций оригинального дерева может быть физически реализовано над деревом в новом алфавите, причем с меньшей временной сложностью.

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

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

7. Реализован новый вид индекса для конкретной СУБД с открытым исходным кодом для ускорения поиска по регулярным выражениям.

8. Реализовано программное обеспечение для выполнения поиска по сходству в программном коде.

Полученные в работе результаты позволили эффективно реализовать новый вид индекса, который может служить основой для решения широкого круга вопросов обработки текстов. Успешное внедрение результатов в существующие системы доказывает их практическую значимость и применимость для рассмотренных прикладных задач.

В качестве направлений дальнейших исследований можно выделить изучение способов реализации суффиксных деревьев во внешней памяти на основе исследований Фараха, исследование вопроса об эффективном построении неплотных суффиксных деревьев с произвольными позициями суффиксов, применение построенного индекса на базе ОСД для выполнения других видов информационного поиска.

Список литературы диссертационного исследования кандидат технических наук Андрианов, Игорь Александрович, 2005 год

1. Андрианов, И.А. Средства контроля знаний в обучающих средах / И.А.Андрианов, В.Р. Габитова // X юбилейная Междунар. студенч. школа-семинар: тез. докл, г. Судак, 14-21 мая 2002 г. М., 2002. - Т. 1. -С. 305 - 306.

2. Андрианов, И.А. Подходы к разработке легкоуправляемых сайтов / И.А. Андрианов, С.Ю. Ржеуцкая // Молодые исследователи региону: материалы Всерос. науч. конф. студентов и аспирантов, г. Вологда, 19-20 апр. 2003 г. -Вологда, 2003. - С. 148 - 149.

3. Андрианов, И.А. Построение индексов для расширенного поиска по текстовым полям / И.А. Андрианов // Интеллектуальные системы: материалы шестого Междунар. симп., г. Саратов, 29 июн. 2 июл. 2004 г. -М., 2004. - С. 279 - 282.

4. Андрианов, И.А. Опыт проведения занятий по программированию в форме оп-Нпе-соревнований / И.А. Андрианов, С.Ю. Ржеуцкая //

5. Модернизация образования. Региональный аспект: материалы второй Всерос. науч.-метод. конф., г. Вологда, 11-12 мар. 2004 г. Вологда, 2004. - С. 199 - 200.

6. Андрианов, И.А. Применение неплотных суффиксных деревьев для поиска наибольшей общей подстроки / И.А. Андрианов // Методы и системы обработки информации / Муромский ин-т (филиал) Владимирского гос. ун-та. М., 2004. - С. 77 - 82.

7. Андрианов, И.А. Применение GIST индексов для ускорения поиска по шаблонам / И.А.Андрианов // Молодые исследователи регионам: материалы Всерос. науч. конф. студентов и аспирантов, г. Вологда, 21-22 апреля 2005 г. - Вологда, 2005. - С. 271 - 272.

8. Ахо, А. Компиляторы. Принципы, технологии, инструменты / Альфред Ахо, Равви Сети, Джеффри Ульман; Пер. с англ. М.: Изд-во Вильяме, 2003. -768 с.

9. Ахо, А. Структуры данных и алгоритмы / Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман; Пер. с англ. М.: Издательский дом "Вильяме", 2000.-384 с.

10. Бакнелл, Д. Фундаментальные алгоритмы и структуры данных в Delphi / Джулиан Бакнелл; Пер. с англ. СПб.: ООО "ДиаСофтЮГГ, 2003. - 560с.

11. Бартунов, О.С. Написание расширений для PostgreSQL с использованием GiST. / О.С. Бартунов, Т.Г. Сигаев // http://www.sai.msu.su/~megera/postgres/talks/gisttutorial.html

12. Бартунов, О.С. Научная сеть: алгоритмы и структуры данных / О.С. Бартунов, Т.Г. Сигаев //http://www.sai.msu.su/~megera/postgres/gist/doc/algo.shtml

13. Бартунов, О.С., Сигаев Т.Г. Tsearch2 full text extension for PostgreSQL / О.С. Бартунов, Т.Г. Сигаев //http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/

14. Бойцов JI.M. Синтез системы автоматической коррекции, индексации и поиска текстовой информации / JI.M. Бойцов; Дис. . канд. техн. наук. М.: Московская академия рынка труда и информационных технологий, 2003. -144 с.

15. Бойцов, JI.M. Часто задаваемые вопросы по нечеткому поиску (поиску по сходству) / JI.M. Бойцов // http://itman.narod.ru/ir/faq/fzfaq.html

16. Вирт, Н. Алгоритмы и структуры данных/ Н. Вирт; Пер. с англ. М.: Издат-во "Вильяме", 1998 -368 с.

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

18. ГОСТ 7.73-96 СИБИД. Поиск и распространение информации. Термины и определения взамен ГОСТ 7.27-80; введ. 01.01.1998.

19. Дейт, К. Дж. Введение в системы баз данных / К. Дж. Дейт; Пер с англ. -Киев; М.: Диалектика, 1998. 784 с.

20. Касьянов, В.Н. Графы в программировании: обработка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев СПб.: БХВ-Петербург, 2003. -1104 с.

21. Кнут, Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы/ Д. Кнут; Пер. с англ. М.: Изд-во "Вильяме", 2000. - 720 с.

22. Кнут, Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы/ Д. Кнут; Пер. с англ. М.: Изд-во "Вильяме", 2000. - 500 с.

23. Кнут, Д. Искусство программирования для ЭВМ. Т.З. Сортировка и поиск/ Д. Кнут; Пер. с англ. М.: Изд-во "Вильяме", 2000. - 832 с.

24. Кормен, Т. Алгоритмы: построение и анализ / Т.Кормен, Ч.Лейзерсон, Р.Ривест М.: МЦНМО; Бином, 2004. - 960 с.

25. Ландэ, Дмитрий. Семантический web: от идеи к технологии / Дмитрий Ландэ //http://www.visti.net/~dwl/art/sw/indexl .html

26. Меньшиков, Ф. Олимпиадные задачи по программированию / Ф. Меньшиков СПб.: Питер, 2005. - 320 с.

27. Опалева, Э.А. Языки программирования и методы трансляции / Э.А. Опалева, В.П. Самойленко СПб.: БХВ-Петербург, 2005. - 480 с.

28. Себеста, Р. Основные концепции языков программирования / Роберт У. Себеста; Пер. с англ. М.: Изд-во "Вильяме", 2001. - 672 с.

29. Сегалович, И. Как работают поисковые системы / Мир Internet. 2002. -№10(73).

30. Седжвик, Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. Часть 1-4 / Р. Седжвик: Пер. с англ. К.: Издательство "ДиаСофт", 2002 - 688.

31. Сизиков, Е.В. Структура поискового индекса, основанного на нечетком сравнении терминов / Перспективные информационные технологии и интеллектуальные системы. 2004. - №3(19). - С. 53 - 63.

32. Скиена, С. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям / Стивен С. Скиена, Мигель А. Ревилла; Пер. с англ. М.: КУДИЦ-Образ, 2005. - 415 с.

33. Страуструп, Б. Язык программирования С++. Специальное издание. / Бьерн Страуструп; Пер. с англ. СПб.: Невский диалект; Бином, 2004. -1104 с.

34. Таненбаум, Э. Современные операционные системы / Э. Таненбаум; Пер. с англ. СПб.: Питер, 2005. - 1040 с.

35. Ульман, Дж. Введение в теорию автоматов, языков и вычислений / Дж. Ульман, Р. Мотвани, Дж. Хопкрофт; Пер. с англ. М.: Изд-во "Вильяме",2002. -528 с.

36. Уорсли, Дж. PostgreSQL. Для профессионалов (+CD-ROM) / Дж. Уорсли, Дж. Дрейк; Пер с англ. — СПб. Литер, 2003. 496 с.

37. Фридл, Дж. Регулярные выражения. 2-е изд. / Дж. Фридл. СПб.: Питер,2003.-464 с.

38. Хаффман, Д.А. Метод построения кодов с минимальной избыточностью / Кибернетический сб. М., 1961. - Вып.З. С.79-87.

39. Хусаинов, Б.С. Структуры и алгоритмы обработки данных. Примеры на языке С / Б.С. Хусаинов М: "Финансы и статистика", 2004. - 464 с.

40. Шень, А. Программирование: теоремы и задачи / А. Шень М.: МЦНМО, 2004.-296 с.

41. Andersson, A. Efficient implementations of suffix trees / A.Andersson, # S.Nilsson // Software Practice and Experience. 1995. - Vol. 25.- P. 129-141.

42. Andersson, Andre. Suffix trees on words / Andre Andersson, Jesper N. Larsson, Kurt Swanson // 7th Annual Symp. on Combinatorial Pattern Matching. Lecture Notes in Computer Science. 1996. - Vol. 1075. - P. 102-115.

43. Aoki, Paul M. Implementation of extended indexes in POSTGRES / Paul M. Aoki //ACM SIGIR Forum. 1991. Vol. 25. P. 2-9.

44. Apostolico, A. The myriad virtues of subword trees / A. Apostolico // Combinatorics on Words / Eds.: A.Apostolico, Z.Galil. Springer-Verlag/ 1985.-Vol. 112. - P.85-96.Щ

45. Arimura, Hiroki. Быстрый алгоритм для обнаружения оптимальных образцов в больших базах данных / Hiroki Arimura, Atsushi Wataki, Ryoichi Fujino, Setsuo Arikawa; Пер с англ. // http://pogorskiy.narod.ru/arimura.htm

46. Baeza-Yates, Ricardo. Fast text searching for regular expressions or automaton searching on tries/ Ricardo A. Baeza-Yates, Gaston G. Gonnet // J. ' ACM.- 1996. Vol. 43.- P. 915-936.

47. Baker, B. A theory of parameterized pattern matching: algorithms and applications / B. Baker // Proc. of the 25th ACM Symp. on the Theory of Computing. 1993. - P. 71- 80

48. Bedathur, Srikanta J. Engineering a fast online persistent suffix tree construction / Srikanta J. Bedathur, Jayant R. Haritsa // In Proc. of the 20th IEEE Intl. Conf. on Data Engineering (ICDE). 2004.

49. Bender, Michael A. The LCA problem revisited / Michael A. Bender, M. . Ф Farach-Colton // In the Proc. of the 4th Latin American Symp. on Theoretical1.formatics. Lecture Notes in Computer Science. 2000. - Vol. 1776. - P. 88-94.

50. Boyer, R.S. A fast string searching algorithm / R.S. Boyer, J.S. Moore // Comm. ACM. 1977. - Vol. 20.- P. 762-772.

51. Blumer, A. Complete inverted files for efficient text retrieval and analysis / A. Blumer, J. Blumer, D. Haussler, R. McConnell, D. Ehrenfeucht // J. ACM. 1987. -P. 578-595.

52. Chang, W.I. Sublinear expected time approximate string matching and biological applications / W.I. Chang, E.L. Lawler //Algorithmica. 1994. Vol. 12. P. 327-244.

53. Cho, Junghoo. A fast regular expression indexing engine / Junghoo Cho, Sridhar Rajagopalan // In Proc. of the 18th Intl. Conf. on Data Engineering (ICDE'02). 2002.

54. Clifford, R. Distributed and Paged Suffix Trees for Large Genetic Databases / R. Clifford, M. Sergot // Proc. 14th Annual Symposium on Combinatorial Pattern Matching. 2003. - P. 70-82.

55. Clough, Paul. Plagiarism in natural and programming languages: an overview of current tools and technologies / Paul Clough // Department of Computer Science, University of Sheffield. 2000. http://www.dcs.shef.ac.uk/~cloughie/papers/Plagiarism.pdf

56. Crochemore, Maxime. Jewels of stringology / Maxime Crochemore, Wojciech Rytter// World Scientific Publishing Co, Pte. Ltd. 2002.

57. Duccasse, Stephane. Lightweight detection of duplicated code a language-independent approach / Stephane Duccasse, Oscar Nierstrasz, Matthias Rieger // I AM. Techreport IAM-04-002. - 2004.

58. Enbody, RJ. / R.J. Enbody, H.C. Du // ACM Computing Surveys (CSUR). -1988. Vol. 20.

59. Farach, M. On the entropy of DNA: algorithms and measurements based on memory and rapid convergence / M. Farach, M. Noordewier, S. Savari, L. Shepp, A. Wyner, J. Ziv // Proc. 6th ACM-SIAM Symp. on Discrete Algs. 1995. -P. 48-57.

60. Farach-Colton, M. On the sorting-complexity of suffix tree construction / M. Farach-Colton, P. Ferrgaina, S. Muthukrishnan // J. ACM. 2000. - Vol. 46.-P. 987-1011.

61. Farach, M. Optimal suffix tree construction with large alphabets / M. Farach // Foundations of Computer Science (FOCS'97). 1997. - P. 137-143.

62. Finkel, Raphael A. Quad Trees: A Data Structure for Retrieval on Composite Keys / Raphael A. Finkel, Jon Louis Bentley //Acta Informatica Vol. 4. 1974-P. 1-9.

63. Gennick, J. Oracle regular expressions pocket reference / J. Gennick, P. Linsley // O'Reilly. 2003. - 64 p.

64. Giegerich, Robert. Efficient implementation of lazy suffix trees / Robert Giegerich, Stefan Kurtz, Jens Stoye // In the Proc. of 3rd Intl. Workshop on Algorithm Engineering. Lecture Notes in Computer Science. Vol. 1668. - 1999. - P.30-42.

65. Giegerich, R. From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction / R. Giegerich, S. Kurtz // Algorithmica. -1997.-Vol. 19. P. 331-353.

66. Grier, S. A Tool that Detects Plagiarism in PASCAL Programs / S. Grier // SIGSCE Bulletin. Vol. 13. - no. 1. - 1981.

67. Gusfield, Dan. Strmat / Dan Gusfiels // http://www.cs.ucdavis.edu /~gusfield/strmat.html

68. Guttman, A. R-trees: a dynamic index structure for spatial searching / A. Guttman // In Proc. of the ACM SIGMOD Intl.Conf. on Management of data. -1984.-P. 47-57.

69. Hunt, Ela. A database index to large biological sequences / Ela Hunt, Malcolm P. Atkinson, Robert W. Irving // Proc. of the 27th International Conf. on Very Large Data Bases. 2001. - P. 139-148.

70. Jacquet, Philippe. Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach / Philippe Jacquet, Wojciech Szpankowski //INRIATR-1106.-1989.

71. Johnson, J. H. Using textual redundancy to understand change / J. H. Johnson // in Proc. of CASCON '95. 1995. - p. CD ROM.

72. Halstead M. H. Elements of Software Science / M. H. Halstead // Elsevier North-Holland. 1977.

73. Harel, D. Fast algorithms for finding nearest common ancestors / D. Harel, R.E. Tarjan // SIAM J. Comput. 1984. - Vol. 13. - P. 338-355.

74. Hellerstein, Joseph M. The RD-tree: an index structure for sets / Joseph M. Hellerstein // University of Wisconsin at Madison. Technical Report №1252. -1994.

75. Karkkainen, Juha. Sparse suffix trees / Juha Karkkainen, Esko Ukkonen. // Proc. of the 2nd Annual International Conf. on Comput. and Combinatorics. Lecture Notes in Computer Science. 1996. - Vol. 1090 - P. 219-230.

76. Kilpelainen, Pekka. Biosequence algorithms. Lecture 8: applications of suffix trees / Pekka Kilpelainen // University of Kuopio, Department of Computer Science. Spring, 2005. http://www.cs.uku.fi/~kilpelai/BSA05/lectures/ slides08.pdf

77. Krishnan, P. Estimating alphanumeric selectivity in the presence of wildcards / P. Krishnan, Jeffrey Scott Vitter, Bala Iyer // Proc. ACM SIGMOD International Conf. on Management of Data. 1996. - P. 282-293.r

78. Kurtz, S. Reducing the space requirements of suffix trees / S. Kurtz // Software Practice and Experience. - 1999. - Vol. 29. - P.l 149-1171.

79. Kurtz, S. Fundamental algorithms for a declarative pattern matching system / S. Kurtz // Report 95-03. Technische Fakult. at der Universit. at Bielefeld. Bielefeld. FRG. 1995.

80. Larsson, Jesper N. Attack of the mutant suffix trees / Jesper N. Larsson // Licentiate thesis, January 1998. http://citeseer.ist.psu.edu/larsson98attack.html

81. McCreight, E.M. A space-economical suffix tree construction algorithm / E.M. McCreight//J. ACM. 1976. - Vol. 23. - P. 262-272.

82. Manber, U. Suffix arrays: a new method for on-line search / U. Manber, G.Myers // SIAM J.Comput. 1993. - Vol. 22. - P. 935-948.

83. Meek, Colin. OASIS: an online and accurate technique for local-alignment searches on biological sequences / Colin Meek, Jignesh M. Patel, Shruti Kasetty // Proc. of the 29th VLDB Conf. 2003.

84. Monostori, Krisztian. Efficiency of data structures for detecting overlaps in digital documents / Krisztian Monostori, Arkady Zaslavsky, Heinz Schmidt // Proc. of the 24th Australasian conf. on Comput. 2001. P. 140-147.

85. Mozgovoy, Maxim. Plagiarism detection reduced to string matching / Maxim Mozgovoy // http://www.cs.joensuu.fi/edtech/mw/material/ plagarticle.pdf

86. Navarro, Gonzalo. Fast regular expression search / Gonzalo Navarro, Mathieu Raffinot // In the Proc. of the 3rd Intl. Workshop on Algorithm Engineering. Lecture Notes in Computer science. 1999. - Vol. 1668. - P. 198-212.

87. Navarro, Gonzalo. A practical q-gram index for text retrieval allowing errors / Gonzalo Navarro, Ricardo Baeza-Yates // CLEI Electronic Journal Vol. 1. -1998. http://www.clei.cl

88. PostgreSQL documentation // http://www.postgresql.org/docs/

89. Schieber, B. On finding lowest common ancestors: simplifications and parallelization / B. Schieber, U. Vishkin // SIAM J. Comput. 1988. - Vol. 17. -P. 1253-1262.

90. Shirani, Dr. S. Multimedia Communications / Dr. S. Shirani // McMaster University. Course number: ECE 728. 2004. http://www.ece.mcmaster.ca/ ~shirani/multi04/multi 04.htm

91. Smyth, Bill. Computing patterns in strings / Bill Smyth // McMaster University, Curtin University of Technology. 2003.

92. Tata, Sandeep. Practical suffix tree construction / Sandeep Tata, Richard A. Hankins, Jignesh M. Patel // Proc. of the VLDB Conf. 2004. - P. 36-47.

93. Tata, Sandeep. TDD suffix tree construction software / Sandeep Tata, Richard A. Hankins, Jignesh M. Patel // http://www.eecs.umich.edu/tdd/

94. Ukkonen, E. Approximate string-matching over suffix trees / E. Ukkonen // Proc. 4th Symp. on Combinatorial Pattern Matching. Lecture Notes in Computer Science. -Springer. 1993. Vol. 684. - P. 228-242.

95. Ukkonen, E. On-line construction of suffix trees / E. Ukkonen // Algorithmica. 1995. - Vol. 14. - P. 249-260.

96. Weiner, P. Linear pattern matching algorithms / P. Weiner // Proc. of the 14th IEEE Symp. on Switching and Automata Theory. 1973. - P. 1-11.

97. Wu, Sun. Fast text searching: allowing errors / Sun Wu, Udi Manber // Comm. of the ACM. 1992. - Vol. 35. - P. 83-91.

98. Wu, S. Agrep — A Fast Approximate Pattern-Matching Tool / S. Wu, U. Manber// Usenix Winter 1992. Technical Conference. San-Francisco. - January 1992.-P. 153-162.

99. Ziv, J. Compression of individual sequences via variable length coding / J. Ziv, A. Lempel // IEEE trans, on Info. Theory. 1978. - Vol. 24. - P.530-536.