автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Анализ и разработка способов индексирования текстов на основе обобщенных и неплотных суффиксных деревьев

На правах рукописи

АНАЛИЗ И РАЗРАБОТКА СПОСОБОВ ИНДЕКСИРОВАНИЯ ТЕКСТОВ НА ОСНОВЕ ОБОБЩЕННЫХ И НЕПЛОТНЫХ СУФФИКСНЫХ ДЕРЕВЬЕВ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2005

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

Научный руководитель - кандидат технических наук, доцент Ржеуцкая С. Ю.

Официальные оппоненты - доктор технических наук, профессор Геппенер В.В.

кандидат технических наук Тупицин A.B.

Ведущая организация - Вологодский научно-координационный центр ЦЭМИ РАН

государственного электротехнического университета "ЛЭТИ" имени В.И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета

Защита состоится диссертационного

Я" 2005 года bV

совета ' Д 212.238.01

™ часов на заседании Санкт-Петербургского

Автореферат разослан 2005г.

Ученый секретарь диссертационного совета

Пантелеев М.Г.

200&-4 18624

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

РОС. НАЦИОНАЛЬНАЯ ВИБЛИОТСКА I С.Оетефрг ООА 09 Ш>

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

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

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

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

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

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

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

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

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

Основные научные положения, выносимые на заштгу.

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

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

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

4. Способ построения обобщенных суффиксных деревьев во внешней памяти.

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались и получили положительную оценку на следующих конференциях, симпозиумах и семинарах: X юбилейная международная студенческая школа-семинар (Судак, МГИЭМ, 2002 г.); Всероссийская научная конференция студентов и аспирантов "Молодые исследователи - регионам" (Вологда, ВоГТУ, 2003, 2004, 2005 гг.); IV Международная научно-техническая конференция "Повышение эффективности теплообменных процессов и систем" (Вологда, ВоГТУ, 2004 г.); VI Международный симпозиум "Интеллектуальные системы" (Саратов, СГТУ, 2004 г.); вторая Всероссийская научно-техническая конференция "Модернизация образования. Региональный аспект" (Вологда, ВоГТУ, 2004 г.); XI Международная конференция "Современные технологии обучения: международный опыт и российские традиции "СТО-2005" (Санкт-Петербург, СПбГЭТУ (ЛЭТИ), 2005 г.); Всероссийская научно-практическая конференция "Образование, наука, бизнес: особенности регионального развития и интеграции" (Череповец, филиал ИМИТ СПбГПУ, 2005 г.); XVI Международная конференция "Применение новых технологий в образовании" (Троицк, Байтик, 2005 г.).

Публикации. По теме диссертации опубликовано 13 научных работ, из них - 6 статей и тезисы к 7-ми докладам на международных и всероссийских научно-тенических конференциях.

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы, включающего 107 наименований, и трёх

приложений. Основная часть работы изложена на 138 страницах машинописного текста. Работа содержит 34 рисунка и 13 таблиц.

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

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

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

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

Рис. 1. Пример обобщенного неплотного суффиксного дерева для строк {'аЬсаЬе$','ЬсаЬсе#'}. В дерево включены только суффиксы, начинающиеся с символов 'а' и 'Ь\ Дуги нагружены подстроками исходной строки (дерево слева), реально на дугах хранят позиции подстрок в исходных строках (дерево справа). Пунктиром показаны суффиксные связи.

Пример обобщенного и одновременно неплотного СД показан на рис. 1. Использование сокращения "СД' в дальнейшем будет означать, что результаты применимы также к ОСД и НСД, если явно не сказано обратное.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

В работе отмечается, что такие структуры могут применяться для решения большого количества задач, связанных с обработкой текстовой информации - в настоящее время известны десятки различных применений. Поскольку основным недостатком СД являются сравнительно высокие требования к памяти (10-15 байт на входной символ), то делается вывод: СД могут быть использованы как в высокой степени универсальный и расширяемый индекс для текстовой информации в информационных системах со средними объёмами данных.

Далее сформулированы практические задачи, решаемые автором в данной работе. Первая задача заключается в ускорении поиска по регулярным выражениям (далее РВ). РВ - гибкий и удобный способ для извлечения информации. Например, для поиска документов, содержащих ссылки на трЗ-файлы и адреса электронной почты в домене га, можно написать следующие (для примера несколько упрощенные) выражения:

'<а\з+11геЯл>]\.трЗ', '\\у+@^+(Лш+>»\.ги'. Вторая задача практического плана, для решения которой применяются результаты диссертационного исследования, заключается в поиске по сходству программного кода. Данная задача в первую очередь направлена на поиск подозрительно похожих решений в дистанционном лабораторном практикуме по программированию. Однако, результаты могут бьгть использованы и для поиска дублирующегося кода в разрабатываемых программных проектах, а также других задачах.

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

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

• основные схемы компактного представления в памяти обычных СД напрямую неприменимы для случая ОСД в связи с возможностью динамического изменения данных в таких деревьях;

• существующие способы представления деревьев в оперативной памяти для реальных данных с алфавитами большого размера позволяют эффективно выполнять лишь отдельные подмножества операций над СД - см. табл. 1. Следует также учитывать, что представление на базе хеширования имеет примерно на 50% большие требования к памяти;

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

Таблица 1. Асимптотические оценки реализации отдельных операций над СД с

Операции / способ представления в памяти Построение Поиск нужной дуги, выходящей из заданного узла Перечисление дуг, исходящих из узла (для реализации обхода)

Хеширование О(п) 0(1) О(И)

Связные списки 0(п-|2|), где |Е| - размер алфавита О0Ч) О(0, где / -количество дуг

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

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

$

Исходный текст а ь а $

Кодированный текст 01100001 01100010 01100001 00100100

Начала суффиксов для НСД А А А А

Рис 2. Пример НСД над текстом в двоичном представлении

Временная сложность построения снижается при этом с 0(п-|Х|) до 0(п-1о£(|£|)).

Дальше во второй главе рассматривается вопрос выбора размера алфавита, в котором будет выполняться построение дерева. Переход к бинарному алфавиту представляется нецелесообразным, так как при этом число внутренних узлов в любом СД с п листьями будет равняться в точности п-1. Для алфавитов же ббльших размеров число внутренних узлов составляет порядка 0,6п-0,8п. Теоретическая оценка среднего числа внутренних узлов дерева в зависимости от размера исходного алфавита получена в работе В. Шпанковски, она имеет вид:

ЕЦ, =£-(1 + Л(1о8")) + 0(1),

к

где п - размер текста, Ъ, - энтропия: А, = -¿1р, 1оё(р,) Данная формула

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

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

Рис. 3. График типичной зависимости числа внутренних узлов в СД от размера к исходного алфавита (слева) и времени построения СД от к (справа)

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

• повышается скорость построения дерева в соответствии со степенью сжатия;

• соответственно увеличивается размер входных данных, которые могут

разместиться в оперативной памяти для построения СД без обращения к низкоскоростной внешней памяти.

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

Пусть Т - оригинальное ОСД, Т* - ОСД, построенное над данными в новом алфавите. В работе выделено множество из 11 базовых элементарных операций АТД "Обобщенное суффиксное дерево" (примеры операций приведены в таблице 2) и показано, что каждая такая операция над Т физически может реализовываться над Т", причём с менее высокой стоимостью. Для каждой из операций описывается алгоритм её реализации над Т' для случая как кодов фиксированной длины, так и префиксных кодов.

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

Таблица 2 Примеры базовых элементарных операций, определенных для ОСД в исходном алфавите и реализуемых для ОСД в новом алфавите. Обозначения: GST - обобщенное

Операция Пример применения Описание

find_child: GST® Pos ®Е -» Pos q:= tree.find_child (P,a) Входные данные: р - позиция в Т' некоторого узла и в Т, символ а е Г (где Т-исходное дерево, X -исходный алфавит, Т'-дерево в новом алфавите). Результаты- Если v узла и существует такой сын v. что дуга u-»v начинается с символа а, то q -позиция узла v в Т', иначе q = NULL (пустая позиция)

suffixlink' GST ® Pos -> Pos tree.su ffixlink(p) Входные данные: позиция р соответствует узлу и в Т. Результаты' позиция q в Т\ соответствующая узлу u suffixlink в Т (переход по суффиксной связи)

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

Т' (часть дерева справа) Для примера исходным символам соответствуют коды: 'а'-»'1201', 'Ь'->'1202\ 'у->'132Г, 'z'-»-'1322\ Узлы дерева Т однозначно отображаются в позиции на дугах дерева Т'.

В третьей главе доказывается следующее утверждение, являющееся основой предлагаемого далее способа построения ОСД во внешней памяти. Пусть дана строка s длины п и функция f(s,j)->{true, false}, возвращающая true, если суффикс s[j..n] должен быть включен в неплотное суффиксное дерево. Функция f должна удовлетворять следующим ограничениям: а). Её результат зависит только от подстроки s[j-l..j+k-l], где к - некоторая константа, б). Функция f вычисляется за константное время. Тогда возможно построить соответствующее НСД с временной сложностью 0(nlog(|£|)) и пространственной сложностью 0(|Т|), где |Т| - размер конечного результата.

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

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

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

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

По аналогии с работой Е. Хант, построение дерева разбивается на независимые построения отдельных его поддеревьев. Однако, предложенный подход для построения поддеревьев использует уже не вероятностный алгоритм с квадратичным в худшем случае временем работы, а модифицированный алгоритм Укконена. Время построения одного поддерева составляет О(п) независимо от входных данных (опуская зависимость от алфавита, т.к. для случая внешней памяти она не столь критична). Приведенное выше утверждение даёт возможность задавать подмножества суффиксов, входящие в поддеревья так, чтобы строящиеся поддеревья имели одинаковый заранее определённый размер. Если М - размер доступной оперативной памяти, m - среднее число байт на один суффикс поддерева, п - длина исходного текста, то при п<М алгоритм требует выполнения

П'Ш

-проходов по исходным данным, на каждом из которых строится одно

М-п

поддерево. Общая стоимость построения будет равна 0( -——)).

М-п

Далее в диссертации рассматривается возможность использования данного алгоритма для случая, когда п близко к М или превосходит его. Как и для других алгоритмов построения СД во внешней памяти, последовательность обращений к исходным данным носит псевдослучайный характер. Это ограничивает их возможный размер: он должен быть сравним с размером оперативной памяти (на практике превышать его не более чем в 1.5 - 2 раза).

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

б(Л0 = (^+1)х(п-М + тЫ)

Пример графика данной зависимости изображен на рис. 5.

о

'I 32000 000 г о

£ 5 28 000 000 2 о о *

£ 11 24000 000

д- 20 000 000 II11II11 111 111 1111111 11 [ 111 111 11 300000 19000003500000 5100000 N - число суффиксов в поддереве

Рис. 5. Иллюстрация зависимости числа обращений к диску от размера строящихся поддеревьев

Размер поддерева, для которого число обращений к диску минимально, тогда можно найти как:

[-гт>Вп(-п + М)]°'5

N =-

п»В

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

и

себе свойства как суффиксных, так и деревьев цифрового поиска. В результате:

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

• при выполнении каждой фазы алгоритма Укконена удаётся избежать обращений к исходному тексту для всех ев продолжений, кроме первого;

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

Полученная в итоге программная реализация превосходит известные аналоги для реальных текстовых данных и оказывается сравнимой с ними для случайно сгенерированных и близких к ним последовательностей Для сравнения был взят алгоритм PWOTD, широко применяемый для построения СД во внешней памяти, и его реализация в виде утилиты TDD, используемой для исследований в области вычислительной биологии в университете г. Мичиган. Пример экспериментальных результатов сравнения приведен на рис. 6. Время выполнения TDD оказалось примерно в 3 раза меньше на случайно сгенерированных символьных последовательностях. Однако, выполненная автором реализация показала примерно на 50% более высокую производительность на случайно сформированной коллекции HTML-текстов и на несколько порядков более высокую - на подборке выпусков одного из электронных журналов. Последнее можно объяснить тем, что журнальные статьи в HTML-формате содержали более высокое число повторяющихся подстрок - похожие участки HTML-кода, повторяющиеся названия, URL-адреса и др. Данный факт не оказывает влияния на наш алгоритм, но оказывается очень существенным для квадратичного в худшем случае алгоритма PWOTD.

Рис 6. Результаты экспериментального сравнения предложенной реализации и реализации алгоритма Р\УО'ГО

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

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

Первая из них заключается в разработке индекса для ускорения поиска по регулярным выражениям (РВ). В работе выполнен обзор существующих подходов к построению таких индексов. Один из подходов, предложенный Баеза-Ятесом и др., заключается в применении построенного по РВ конечного автомата не к исходным текстам, а к индексу на основе СД. В результате среднее время поиска оказывается сублинейным. Альтернативный подход, предложенный Чо и др., использует тот факт, что из многих РВ можно извлечь отдельные подстроки (граммы) с низкой селективностью (т.е. встречающиеся в небольшой доле исходных документов). На их основе строится сокращенное синтаксическое дерево (см. рис. 7), которое используется для выполнения поиска. Найденные документы требуют дополнительной проверки на соответствие исходному РВ.

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

• возможность совместного использования двух описанных подходов, эффективных для разных классов РВ, используя одну и ту же структуру данных и базовые алгоритмы работы с ней;

• возможность динамического обновления индекса (в оригинальной статье Чо и др. индекс предполагается статическим, и способы эффективной его модификации при изменении данных не предусмотрены);

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

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

• для любого другого слова языка одно из них является его собственным префиксом;

• никакое ключевое слово не является собственным префиксом другого. Однако, класс префиксных РВ не охватывает многие практически важные

выражения, поиск по которым может быть выполнен с высокой эффективностью. Например, выражение 'а(Ь|с)<1+' является префиксным, тогда как похожее выражение '(а|Ь)с<1+' - не является. В связи с этим предложено расширить данный класс выражений, включив в него РВ, для которых выполняется приведённое свойство и при этом поиск требует не более 0(тК) операций, где т - длина РВ, К - максимальное количество ключевых слов (параметр настройки). Соответственно дополнено определение расширенных РВ и модифицирован алгоритм их

АШ

Рис.7. Сокращенное синтаксическое дерево для регулярного выражения 'ау1.*@.*(у81и)уо5Ш)\

идентификации - см. табл. 3.

Таблица 3. Алгоритм проверки, является ли регулярное выражение расширенным префиксным (ЕРЯЕ), и определение его ключевых слов (ргелУог(Ь)_

выражение ЕРКЕ(выражение) рге\уогсЬ(выражение)

0 True 0

Е True <Е>

х 6 Е True {X}

r|s EPRE(r) и EPRE(s) prewords(r) и prewords(s)

Rs а). ( г - выражение, задающее конечный язык и EPRE(s)) или б). ( EPRE(r) и е 6 L(s)) prewords(r)prewords(s)

г* True <е}

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

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

Таблица 4. Простые изменения в исходном коде не влияют иа конечный результат

Первый текст Второй текст

Исходный for(int 0; i<20; i++) int k=0 , i= 0;

код { с+=а; a*=2 ; ) while(i<20)

( c+= -а; Ч++; a*=2; i++; }

Откомпили хог edx. edx xor edx, edx

ро ванный ез : add ecx. eax 02: add ecx. eax

код mov ebx, eax mov ebx, eax

add ebx. ebx add ebx. ebx

mov eax. ebx mov eax. ebx

@5 : inc edx inc edx

cmp edx. 20 cmp edx, 20

jl short 03 jl short 02

Таким образом, задача сводится к поиску совпадающих фрагментов в текстах, которая эффективно решается с помощью ОС Д (работы Моностори и др.)

Предложенная методика была реализована для поиска подозрительно похожих

решений в автоматизированной проверяющей системе. При этом были выделены два способа контроля поступающего решения - сравнение с решениями сдаваемой задачи либо со всеми решениями в базе данных (предполагая заимствование участков кода из разных мест).

В первом случае ОСД, используемое для поиска по сходству, строится для относительно небольшого количества решений и кэшируются в оперативной памяти. Это позволяет выполнять проверку за время 0(m+k), где m - длина проверяемого решения, к - результирующее количество совпадений.

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

Проверка в реальных условиях проводилось на проверяющей системе, используемой в ВоГТУ для проведения лабораторных работ по программированию. Результаты показали, что сравнение поступающего решения только с решениями данной задачи выполняется значительно меньше секунды при количестве сравниваемых решений около 100, со всеми решениями (несколько тысяч) - порядка одной секунды (без учета времени компиляции). Данные результаты являются вполне приемлемыми и показывают наличие достаточных резервов для дальнейшего наращивания объёмов данных.

Далее в работе исследуются особенности реализации индексного метода доступа на основе ОСД для СУБД PostgreSQL. Проанализированы основные способы внедрения новых индексных методов доступа в данную СУБД -разработка индексов "с нуля", используя соответствующие интерфейсы, и применение обобщенных деревьев поиска информации (GIST). Сделан вывод, что текущая реализация GIST не предоставляет требуемых возможностей для реализации ОСД, и предложен вариант реализации новых видов индексов, позволяющий упростить их разработку, особенно для программистов - не специалистов по особенностям внутренней работы СУБД. Суть подхода состоит в применении для хранения и доступа к индексным данным высокоуровневых средств самой СУБД, что позволяет использовать готовые средства обеспечения корректного параллельного доступа к индексу, размещения данных в дисковых страницах, компрессии и др. Важным моментом является то, что по своему использованию новые виды индексов не отличаются от встроенных в СУБД.

На основе данного варианта реализации разработан индекс для PostgreSQL, позволяющий ускорять поиск по шаблонам в виде РВ для текстовых полей. При хранении ОСД разбивается на отдельные поддеревья, занимающие 1-3 дисковых страниц, над которыми, в свою очередь, строится индекс стандартными средствами СУБД. В итоге выполнение поиска для низкоселективных запросов требует чтения всего лишь нескольких дисковых станиц.

Важным вопросом для любого индекса является возможность его модификации для приведения в соответствии с изменившимися данными и стоимость такой операции. Модификация ОСД при вставке/удалении записи длины m выполняется в среднем за время 0(m log(m)). Непосредственное выполнение такой операции при каждом изменении данных неприемлемо для большинства приложений ввиду ощутимых задержек. Поэтому использован другой вариант - в структуру индекса

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

Результаты тестирования показали более чем десятикратное среднее ускорение поиска по сравнению с использованием стандартных средств СУБД. При этом поиск отдельных РВ выполняется быстрее на 2 порядка и более. Платой за такое ускорение служит объём созданного индекса, который с учётом возможностей сжатия данных, предоставляемых СУБД, превышает объём входных данных в 1012 раз.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

1. Кодирование символов исходного текста с использованием алфавита меньшего размера позволяет снизить зависимость от размера алфавита времени построения суффиксного дерева и поиска в нём с линейной до логарифмической. Требования к оперативной памяти при этом не изменяются.

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

3. Андрианов, И.А. Структуры данных для повышения эффективности выполнения специальных видов поиска /И.А. Андрианов, В.Н. Минин // Молодые исследователи - региону: материалы Всерос. науч. конф. студентов и аспирантов, г. Вологда, 22-23 апр. 2004 г. - Вологда, 2004. - С. 154 - 155.

4. Андрианов, И.А. Один пример использования неплотных суффиксных деревьев для обработки текстов / И.А. Андрианов II Повышение эффективности теплообменных процессов и систем: материалы IV Международной науч.-техн. конф., г. Вологда, 25-27 окт. 2004 г. - Вологда, 2004. - С. 304 - 307.

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

6. Андрианов, И.А. Подходы к организации подсистемы поиска по сайту в условиях хостинга с ограниченными возможностями / И.А. Андрианов // Моделирование, оптимизация и интенсификация производственных процессов и систем: материалы Междунар. науч.-техн. конф., г. Вологда, 19-21 мая 2004 г. -Вологда, 2004. - С. 270 - 273.

7. Андрианов, И.А. Опыт проведения занятий по программированию в форме оп-Нпе-соревнований / И.А. Андрианов, С.Ю. Ржеуцкая // Модернизация образования. Региональный аспект: материалы второй Всерос. науч.-метод. конф., г. Вологда, 11-12 мар. 2004 г. - Вологда, 2004. С. 199 - 200.

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

9. Андрианов, И.А. Использование высокоуровневых интерфейсов для разработки индексных методов доступа в СУБД PostgreSQL / И.А. Адрианов // Образование, наука, бизнес: особенности регионального развития и интеграции: тр. Всерос. науч.-практ. конф., г. Санкт-Петербург, 26-27 мая 2005 г. - СПб., 2005. - С. 230 -235.

10. Андрианов, И.А., Проблема поиска по регулярным выражениям в текстовых базах данных / И А Андрианов, В Н. Минин // Образование, наука, бизнес: особенности регионального развития и интеграции: тр. Всерос. науч.-практ. конф., г. Санкт-Петербург, 26-27 мая 2005 г - СПб., 2005. - С 284 - 287.

11. Андрианов, И.А Применение обобщенных суффиксных деревьев для анализа программного кода при обучении программированию / И.А. Андрианов // Применение новых технологий в образовании: материалы XVI Междунар. конф., г. Троицк, 28-29 июня 2005 г. - Троицк, 2005. - С 11 -12.

12. Андрианов, И.А. Одна задача обработки исходных текстов в автоматизированных системах обучения программированию / И.А.Андрианов, В.Н Минин // Современные технологии обучения: международный опыт и российские традиции «СТО-2005»: материалы XI Междунар. конф., г. Санкт-Петербург, 20 апр. 2005 г. - СПб., 2005. - С. 102 -104

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

Ю22 136

РНБ Русский фонд

2006-4 18624

Подписано в печать 03.11.2005. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл.печ. л. 1,0. Тираж 100 экз. Заказ № 390.

Отпечатано в РИО ВоГТУ 160035, Вологда, ул. Ленина, 15

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

ВВЕДЕНИЕ

ГЛАВА 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. Реализовано программное обеспечение для выполнения поиска по сходству в программном коде.

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

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

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.