Содержание к диссертации
Введение
ГЛАВА 1. Анализ способов индексирования текстов на основе суффиксных деревьев. Постановка задач исследования 12
1.1 Обзор применений суффиксных деревьев для поиска в текстах 12
1.2 Суффиксные деревья: основные понятия, определения и обозначения 15
1.3 Формулировка решаемых прикладных задач 20
1.3.1 Задача ускорения поиска по регулярным выражениям 20
1.3.2 Задача о поиске по сходству в программном коде 24
1.4. Анализ существующих алгоритмов и схем представления в памяти суффиксных деревьев 28
1.4.1 Обзор алгоритмов построения и способов представления суффиксных деревьев в оперативной памяти. 28
1.4.2 Алгоритм Укконена . 30
1.4.3 Обзор алгоритмов построения и способов представления суффиксных деревьев во внешней памяти 37
1.5 Постановка задач дальнейшего исследования 42
Выводы по главе 1 45
ГЛАВА 2. Разработка структур хранения обобщенных суффиксных деревьев, эффективных алгоритмов построения и поиска в них 47
2.1. Анализ и модификация способов представления узлов СД и ОСД
в памяти 47
2.2. Повышение эффективности построения и использования СД путём перехода к алфавиту меньшего размера / 55
2.2.1 Выбор размера нового алфавита 61
2.2.2 Построение СД при кодировании текста с помощью префиксных кодов 64
2.3 Реализация операций исходного ОСД на основе ОСД над кодированным текстом 68
2.3.1 Определение интерфейсных операций АТД "ОСД" 68
2.3.2 Реализация операций для кодов фиксированной длины 72
2.3.3 Реализация операций для префиксных кодов переменной длины 77
Выводы по главе 2 80
ГЛАВА 3. Разработка алгоритмов построения и использования обобщенных суффиксных деревьев во внешней памяти . 81
3.1 Построение неплотных суффиксных деревьев с ограничениями на позиции суффиксов 81
3.2 Разработка алгоритма построения СД во внешней памяти на основе алгоритма линейного построения НСД 88
3.3 Адаптация алгоритма для случая исходных данных во внешней памяти 93
3.3.1 Модификация структуры дерева 93
м 3.3.2 Определение соотношения между размером буфера для исходных данные и памятью для НСД 95
3.4 Сравнение алгоритма построения СД во внешней памяти с аналогами 98
Выводы по главе 3 104
ГЛАВА 4. Применение полученных результатов для практических задач 106
4.1 Применение индекса на основе ОСД для ускорения поиска по регулярным выражениям 106
4.1.1 Применение суффиксных деревьев для ускорения поиска по регулярным выражениям при использовании конечных автоматов 106
4.1.2 Использование граммного подхода для ускорения поиска поРВ 112
4.1.3 Адаптация граммного подхода к использованию ОСД 115
4.2 Применение индекса на основе ОСД для поиска по сходству в программном коде 116
4.2.1 Методика поиска по сходству в программном коде на основе сравнения промежуточных результатов компиляции 116
4.2.2 Использование обобщенных суффиксных деревьев для обнаружения совпадающих фрагментов текстов 121
4.2.3 Применение результатов поиска по сходству в автоматической проверяющей системе и для поиска дублирующегося кода 122
Ofr 4.3 Реализация индексного метода доступа для СУБД PostgreSQL 126
4.3.1 Применение высокоуровневых средств СУБД при реализации новых индексных методов доступа 126
4.3.2 Особенности программной реализации индекса 129
4.4 Анализ экспериментальных результатов 132
Выводы по главе 4 135
Заключение 137
Список литературы
- Суффиксные деревья: основные понятия, определения и обозначения
- Повышение эффективности построения и использования СД путём перехода к алфавиту меньшего размера
- Разработка алгоритма построения СД во внешней памяти на основе алгоритма линейного построения НСД
- Применение суффиксных деревьев для ускорения поиска по регулярным выражениям при использовании конечных автоматов
Введение к работе
В современном обществе важнейшую роль играют системы информационного поиска (ИПС), позволяющие осуществлять эффективный поиск нужных сведений в море информации. Подобные системы постоянно совершенствуются как за счёт прогресса в области аппаратных средств, так и за счет модернизации заложенных в них структур и алгоритмов. Совершенствуются и сами подходы к отбору информации, позволяя пользователю более гибко задавать то, что он хочет найти. Так, в дополнение к поиску слов и грамматических форм [35], развиваются возможности нечёткого поиска [37], использование в запросах шаблонов различного вида [53], поиск с учётом семантики [31] и др.
Как видим, направлений поиска очень много. Поэтому уточним само понятие информационного поиска и конкретизируем направление исследования.
Согласно ГОСТ 7.73-96 [24], информационный поиск - это "действия, методы и процедуры, позволяющие осуществлять отбор определённой информации из массива данных". В данной работе речь идет о полнотекстовом поиске, который в ГОСТ определен как "автоматизированный документальный поиск, при котором в качестве поискового образа документа используется его полный текст или существенные части текста".
Некоторые виды поиска, например, словарный, на сегодняшний момент хорошо проработаны теоретически и реализованы в огромном количестве поисковых программ. Несколько хуже обстоит дело с другими видами поиска, которые не менее важны и востребованы на практике - поиск по различным шаблонам, нечеткий поиск, в том числе по сходству длинных фрагментов текста и др. Все эти задачи не предполагают естественного разбиения текста на некоторые составные единицы (слова, строки и т.п.), т. е. сам термин «текстовый документ» рассматривается в широком смысле как произвольная последовательность
7 символов, например, обычный текст на естественном языке, html-документ, исходный текст компьютерной программы, её исполняемый код и др.
Вопросам проектирования структур данных и алгоритмов таких видов информационного поиска посвящены работы Р.Баеза-Ятеса, Г.Гоннета, Д.Гасфилда, Э.Укконена, С.Куртца и др. Из отечественных публикаций на эту тему можно выделить фундаментальные работы В.М.Глушкова по теории автоматов, а также работы Л.М.Бойцова, Е.В.Андриенко, О.С.Бартунова, Т.Г.Сигаева и др., посвященные непосредственно информационному поиску.
Существуют различные способы хранения текстовой информации, например, в виде коллекций файлов, документо-ориентированных и фактографических базах данных. В любом случае, для ускорения или даже обеспечения возможности выполнения поиска необходимо выполнить . предварительную обработку текста с целью создания дополнительной структуры для поддержки поиска. Подобные структуры называются индексами и могут располагаться как во внешней, так и в оперативной памяти.
Имеется большое количество способов организации индексов, использующих различные структуры данных и алгоритмы. Одним из перспективных подходов является использование структур данных на основе суффиксных деревьев (СД) [5]. СД представляет собой одну из наиболее универсальных структур данных для поддержки поиска в текстах - известно не менее нескольких десятков задач поиска, эффективно решаемых с её помощью. , Однако, в силу своей универсальности СД имеют сравнительно высокие требования к памяти. Поэтому представляется целесообразным использовать данную структуру для индексирования коллекций документов средних размеров (до нескольких гигабайт).
Исследование, выполненное в настоящей работе, направлено на разработку индексов для эффективной реализации поиска на основе СД. В качестве практических задач, которые решены на основе выполненных теоретических разработок, рассматривается поиск по шаблонам, заданным в виде регулярных
8 выражений, а также поиск по сходству фрагментов программного кода. Возможны и другие применения разработанных структур и алгоритмов. Результаты исследования применены при разработке нового вида индекса для свободно распространяемой СУБД PostgreSQL и внедрены в реальные прикладные системы. Целью диссертационной работы является повышение эффективности поиска путем индексирования исходных текстов с использованием обобщенных и ' неплотных суффиксных деревьев. Для достижения поставленной цели в данной диссертационной работе решаются следующие задачи:
1. Анализ существующих подходов к решению рассматриваемых задач;
анализ работ, посвященных построению и использованию индексов на основе
суффиксных деревьев.
2. Исследование обобщенных и неплотных суффиксных деревьев,
разработка структур и алгоритмов для эффективной реализации индексов для
случаев как оперативной, так и внешней памяти.
3. Применение полученных теоретических результатов для решаемых задач
поиска.
Программная реализация индексов; получение экспериментальных данных, сравнение их с теоретическими оценками; сравнение полученных реализаций с аналогами.
Внедрение полученных результатов в деятельность конкретных организаций.
В соответствии с вышесказанным объектом исследования являются коллекции текстовых документов средних размеров (до нескольких гигабайт для современных типовых средств вычислительной техники).
В качестве предмета исследования выступают способы организации и алгоритмы обработки индексов на основе обобщенных и неплотных суффиксных деревьев.
В качестве методов исследования в работе использовались методы теории множеств, теории графов, анализа алгоритмов, теории автоматов,
математического анализа. Кроме того, применялись методы разработки программного обеспечения с использованием объектно-ориентированного подхода.
Научная новизна работы заключается в следующем:
1. Разработан метод эффективного построения и использования обобщенных
суффиксных деревьев, основанный на кодировании символов исходного текста с
помощью алфавита существенно меньшего размера. Временная сложность
построения ОСД уменьшается с 0(п-|2|) до 0(n-log(|L|)), поиска подстроки - с
O(m-jZj) до 0(m-log(|X|)), где п - длина текста, m - длина подстроки, |Е| - размер
исходного алфавита. Требования к памяти не изменяются.
Предложено использовать оптимальные префиксные коды с целью дополнительного снижения временной сложности построения дерева и поиска в нем, а также увеличения возможного размера входных данных. Для построения дерева над сжатым текстом модифицирован алгоритм Каркайнена и Укконена.
Обоснована целесообразность использования неплотных суффиксных деревьев применительно к решаемым задачам поиска в целях ускорения построения индексов и внесения управляемости в расход памяти. Предложено обобщение алгоритма Укконена для построения неравномерно неплотных суффиксных деревьев, доказана его корректность, получены асимптотические оценки сложности.
Предложен способ построения обобщенных суффиксных деревьев во внешней памяти, значительно менее чувствительный к отличиям реальных входных данных от теоретического среднего случая и сравнимый с аналогами по другим параметрам.
Практическая значимость результатов диссертации заключается в следующем:
1. На основе выполненных исследований реализованы индексы для ускорения поиска по регулярным выражениям и поиска по сходству фрагментов
10 текста как для оперативной, так и для внешней памяти. Для случая хранения данных в полях СУБД разработан и внедрен новый вид индекса для одной из СУБД с открытым исходным кодом.
Предложено объединение двух различных подходов к индексированию для ускорения поиска по регулярным выражениям и их реализация на основе обобщенных суффиксных деревьев. Расширен класс т.н. префиксных регулярных выражений, поиск на соответствие которым в суффиксном дереве выполняется с гарантированной эффективностью.
Предложена и реализована методика выполнения поиска по сходству в исходном программном коде, основанная на предобработке кода на промежуточном языке с помощью суффиксных деревьев после выполнения трансляции.
Разработано прикладное ПО, позволяющее существенно сократить время поиска по сравнению с известными программными продуктами, решающими аналогичные задачи.
Прикладные результаты данной работы внедрены в НОУ "УЦ "Мезон" и ООО "Вологодский трубопрокатный завод". Для НОУ «УЦ «Мезон» улучшена фильтрация электронных сообщений по наборам регулярных выражений и реализовано дополнение к автоматической проверяющей системе для поиска подозрительно похожего программного кода. В ООО "Вологодский трубопрокатный завод" данные результаты применены для поиска дублирующегося программного кода в разрабатываемом ПО, а также для ускорения поиска по LIKE-шаблонам в текстовых полях СУБД.
Кроме того, результаты диссертационной работы используются в учебном процессе кафедры автоматики и вычислительной техники Вологодского государственного технического университета в автоматической проверяющей системе и при преподавании курсов "Структуры и алгоритмы обработки данных", "Программирование на языке высокого уровня".
11 Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. В первой главе определяются и уточняются цели диссертационной работы, выполняется анализ работ в данной области, определяются направления и конкретные задачи диссертационного исследования. Во второй главе рассматриваются вопросы разработки эффективной структуры хранения, алгоритмов построения и использования обобщенных суффиксных деревьев. Третья глава посвящена построению суффиксных деревьев во внешней памяти. В четвертой главе рассматривается применение полученных результатов к решению прикладных задач. В приложениях приведены псевдокоды алгоритмов, описано применение результатов работы к задаче поиска наибольшей общей подстроки, приведены копии актов о внедрении результатов диссертационной работы.
Суффиксные деревья: основные понятия, определения и обозначения
Рассмотрим некоторую строку s в алфавите Е. Её длину будем обозначать через s. Запись s[i..j] соответствует подстроке s с позиций і по j, где 1 і j [s. Префиксом s называется любая подстрока s вида s[l..i],. i js. В случае i s мы имеем собственный префикс. Аналогично, суффиксом s называется любая подстрока s вида s[i..Js], при і 1 мы имеем собственный суффикс.
Определение 1.1 Луч ("trie") над множеством строк S представляет собой дерево, вершины которого нагружены символами из Z, Никакие два дочерних узла не могут быть нагружены одним и тем же символом. Любой строки s є S соответствует единственный путь от корня, конкатенация символов на вершинах которого даёт s. Это свойство выполняется также и для любого префикса любой строки.
Таким образом, можно сказать, что луч объединяет общие префиксы заданных строк. Пример показан на рисунке 1.1. Если никакая строка в S не является собственным префиксом другой, то каждой строке s є S будет однозначно соответствовать лист в дереве, конкатенация символов на пути к которому даёт s. При этом эффективно решается задача принадлежности строки данному множеству.
Чтобы узнать, принадлежит ли строка v множеству S, нужно, начиная от корня луча, перемещаться по нему в соответствии с символами в строке v. Если в результате мы оказались в листе и использовали все символы из v, то v є S, и не принадлежит в противном случае. Время работы данного алгоритма составляет 0(v) (считая размер алфавита константой) независимо от того, насколько велико множество S.
Чтобы гарантировать, что никакая строка не является собственным префиксом другой строки, применяется следующий приём: к каждой строке справа дописывается специальный символ, отсутствующий в алфавите. Такой символ называется терминальным, в дальнейшем для его обозначения будет использоваться знак $.
Определение 1.2 Суффикспым лучом называется луч, построенный над множеством (или, в общем случае, над некоторым подмножеством) суффиксов исходной строки.
Пример суффиксного луча показан на рисунке 1.2. Для того, чтобы гарантировать взаимно однозначное соответствие между листьями луча и ; суффиксами s, s дополнена терминальным символом $.
В суффиксном луче удобным образом представлены все подстроки исходной строки. Чтобы определить, встречается ли строка t в качестве подстроки s, достаточно проверить, существует ли такой путь от корня, конкатенация символов на котором даёт t Предположим, этот путь существует и заканчивается в вершине v. Тогда для получения всех позиций вхождения t в s необходимо обойти все листья в поддереве с корнем в v, при этом длины путей от корня до листьев определят позиции вхождений t в s (относительно конца строки s).
Недостатком суффиксного луча является его размер - порядка п2 вершин в худшем случае. Кроме собственно затрат памяти, такой размер не даёт перспектив уменьшения нижней границы времени работы алгоритмов построения суффиксного луча - она равна 2(п2). Соответственно, для уменьшения требований к памяти и снижения нижней границы времени построения обычно применяют сжатый вариант суффиксного луча - суффиксное дерево.
Определение 1.3 Суффиксное дерево представляет собой сжатый вариант суффиксного луча, в котором информация из узлов перенесены на дуги, узлы степени 2 (за исключением корня) удалены из дерева, а соответствующие дуги объединены. Т.о., каждая дуга в дереве соответствует некоторой подстроке исходного текста. Для экономии места вместо самой подстроки хранятся её начальная и конечная позиция в исходной строке в виде упорядоченной пары i,j .
Повышение эффективности построения и использования СД путём перехода к алфавиту меньшего размера
Существует достаточно большое количество работ, рассматривающих суффиксные деревья с разных точек зрения: построение во внешней и оперативной памяти, способы хранения структуры дерева, применение СД для конкретных задач. Однако, достаточно небольшое количество работ посвящено исследованию особенностей работы с ОСД, которые являются основой разрабатываемых индексов.
Отличие ОСД от обычного СД заключается не только в том, что оно строится над набором текстов (что уже существенно), но и в наличии двух дополнительных операций - вставки и удаления строк в процессе работы. В частности, это влечёт необходимость в исследовании способов компактного представления содержимого узлов обычных СД применительно к ОСД: - какие изменения потребуется в них внести, - возможно ли реализовать при этом дополнительные операции ОСД. Важным вопросом при использовании суффиксных деревьев является способ представления в памяти структуры дерева, т.е. дуг дерева и суффиксных связей. Основной проблемой при представлении дуг, выходящих из узла дерева, является то, что СД - сильноветвящееся дерево, где максимальное число детей любого внутреннего узла равно размеру алфавита, минимальное = 2. При работе с реальными текстовыми, html- и исполняемыми файлами алфавит составляет десятки — сотни символов, и это существенно влияет на эффективность выполнения операций с деревом в зависимости от выбранного способа представления.
Существует несколько способов представления дуг, выходящих из узла дерева: а). Хранить в каждом узле массив, размер которого равен размеру алфавита, для представления всех возможных дуг, которые могут выходить из данного узла б). Организовывать в каждом узле небольшое поисковое дерево или альтернативную структуру для представления исходящих из него дуг в). Хранить детей узла в связном списке г). Использовать некоторую схему хеширования.
Подходы а) и б) чрезмерно требовательны к памяти и по этой причине на практике, как правило, не используются (лишь для очень специфических задач). В основном, применяются подходы в) и г). Их преимущества и недостатки приведены в таблицах 1.1 и 1.2.
Таким образом, оба способа представления СД эффективны лишь для специфических подмножеств его операций. В нашем же случае разрабатываемые индексы будут использоваться: а), для решения различных задач поиска, б), для реальных текстов со сравнительно большими размерами алфавитов.
Следовательно, актуальной задачей является разработка способа представления дерева, при котором основной набор операций выполняется эффективно как с точки зрения временной, так и пространственной сложности.
Ещё" одним важным вопросом, требующим дальнейшего исследования, является построение ОСД в условиях внешней памяти. Как отмечается выше, существующие алгоритмы носят вероятностный характер и, хотя они хорошо работают для "средних" - случайно сгенерированных и близких к ним данных, но для встречающихся на практике текстов время работы может отличаться Щ. существенно. Для примера можно посмотреть на рис. 3.8 из главы 3 - из диаграммы видно, насколько резко отличается время работы алгоритма PWOTD при построении СД над случайной подборкой html-файлов и архивом выпусков одного из электронных журналов, содержащих большое число повторяющихся подстрок.
Выводы по главе 1 1. Выбор минимальной индексируемой единицы в значительной степени определяет возможности ИПС. Декомпозиция на основе подстрок позволяет обеспечить возможности поиска, нереализуемые при пословной декомпозиции т 2. Индексирование текстов на основе суффиксных деревьев и их расширений позволяет эффективно решать большой круг задач обработки текстов. Две из них - ускорение поиска по регулярным выражениям и реализация поиска по сходству в исходном коде — являются прикладными задачами, решаемые в данной диссертации.
При построении и использовании СД для реальных текстовых данных имеется ряд вопросов и ограничений, решению которых посвящены следующие две главы диссертационной работы:
a. Основные схемы компактного представления в памяти обычных СД нуждаются в исследовании на применимость для ОСД и соответствующей адаптации.
b. Существующие способы представления деревьев в оперативной памяти при использовании алфавитов неконстантного размера позволяют эффективно выполнять лишь отдельные подмножества операций над СД.
c. Алгоритмы построения обобщенных суффиксных деревьев в оперативной памяти непригодны для данных больших объёмов в случае использования внешней памяти. Используемые для этого вероятностные алгоритмы имеют в худшем случае квадратичную сложность, и для реальных данных время их работы зачастую многократно отличается от теоретического среднего случая.
Разработка алгоритма построения СД во внешней памяти на основе алгоритма линейного построения НСД
Несмотря на применение описанных в предыдущей главе способов компактного представления СД, на практике далеко не всегда возможна работа с СД в оперативной памяти — размер исходных данных может быть слишком велик.
При этом рассматриваемый ранее алгоритм Укконена (и его альтернативы) становится неприменимым в связи с резким - на несколько порядков -уменьшением скорости его работы. Такое замедление связано с тем, что в процессе работы алгоритма необходим доступ к узлам уже построенной части дерева. Но обращения к этим узлам носят характер, близкий к случайному [71], и какие-либо стратегии кэширования (LRU, MRU [40] и др.) оказываются неэффективными.
Одним из решений данной проблемы является использование алгоритмов построения СД, при работе которых не требуется возвратов к уже построенным узлам. В качестве типичного представителя такого алгоритма выступает алгоритм WOTD [71] и его модификация PWOTD [100] (см. главу 1). В качестве недостатков данного алгоритма можно выделить следующее (см. главу 1):
1. Временная сложность построения дерева составляет уже не О(п), а 0(п2) в худшем случае и 0(n-logn) - в среднем.
2. Нет возможности использовать существующие реализации построения дерева в оперативной памяти — требуется реализовывать новый алгоритм с нуля и в дальнейшем поддерживать оба варианта.
Заметим (по второму недостатку), что использовать алгоритм WOTD и для случая оперативной памяти мы не можем также по той причине, что при его работе не создаются суффиксные связи, которые нам необходимы для задачи поиска по сходству.
В диссертации предлагается другой подход - строить дерево последовательным построением отдельных независимых поддеревьев, помещающихся в оперативную память (как в [100] или [76]), но при этом построение каждого дерева выполнять с использованием алгоритма Укконена.
Для этого достаточно заметить, что НСД, построенное над суффиксами исходной строки, которые начинаются с одного и того же префикса, является поддеревом СД, построенного над всей исходной строкой. При этом, как показано
Клиффордом и др. [61] (см. выше), такое поддерево может быть построено за линейное время с использованием расширенного алгоритма Укконена. Полный набор таких неплотных суффиксных деревьев, построенных для всех возможных префиксов одинаковой длины к, в совокупности образует полное суффиксное дерево. Пример показан на рисунке 3.4.
В [61] данный подход использовался для того, чтобы распараллелить построение и использование суффиксных деревьев. Но его можно применить для последовательного построения и записи на диск частей дерева, если преодолеть следующий недостаток. Длина префикса к в [61] выбирается таким образом, чтобы самые крупные из поддеревьев помещались в оперативную память (по крайней мере, большая их часть). Для реальных текстов, HTML- и бинарных файлов объёмом до нескольких гигабайт наиболее подходящим выбором является значение 3. Но при этом значительная часть поддеревьев будет иметь размер, на порядки меньший, чем размер доступной памяти. Так, для реальных HTML-данных объёмом около 200 мегабайт и длине префикса = 3 средний размер одного поддерева составляет лишь несколько килобайт, а их количество, соответственно, оказывается чрезмерно большим (см. для примера гистограмму на рис. 3.7.). Для построения же каждого поддерева способом [61] требуется выполнение полного прохода по всему исходному тексту.
В диссертации предлагается за один проход по тексту строить поддеревья максимального размера, которые ещё помещается в оперативную память (наподобие того, как это делается в алгоритме Хант - см. раздел 1.4.). Для этого используется доказанное выше утверждение 3.3. Согласно ему, построение всех поддеревьев результирующего дерева можно выполнить за 0(р-п), где р - число проходов, п - размер исходных данных. Значение р можно приближенно определить как р=Т/М, где jT - размер результирующего дерева, М - размер доступной оперативной памяти для построения его частей. Обозначим через m среднее число байт, приходящееся на один суффикс поддерева. I огда р = , и общая стоимость построения будет равняться М-п
Определенным недостатком предложенного подхода является необходимость полного прохода по тексту для построения каждого поддерева, даже если они имеют сравнительно небольшой размер (вследствие малого количества свободной памяти). Для того, чтобы преодолеть данный недостаток, воспользуемся приёмом, предложенным в программном продукте TDD для построения СД [101]. Перед началом выполнения основного алгоритма всё множество суффиксов разделяется на подмножества, задающие, к каким поддеревьям они относятся. Позиции суффиксов каждого такого подмножества
запоминаются - например, в файле или БД. Тем самым, при выполнении очередного прохода становится доступной упорядоченная последовательность позиций суффиксов, которые войдут в строящееся поддерево.
Применение суффиксных деревьев для ускорения поиска по регулярным выражениям при использовании конечных автоматов
В работе Баеза-Ятеса и др. [53] показана возможность использования суффиксных лучей для ускорения поиска по регулярным выражениям (на практике вместо суффиксного луча целесообразно использовать его сжатый варинт - суффиксное дерево). Для этого регулярное выражение преобразуется в соответствующий детерминированный конечный автомат. Далее в построенном автомате удаляются все переходы, выходящие из заключительного состояния, после чего удаляются недостижимые состояния (если таковые появились).
Для выполнения поиска считается, что начальное состояние автомата соответствует корню луча. Далее выполняется обход луча со следующими ограничениями: (а) если из текущей вершины луча v выходит дуга, нагруженная некоторым символом с и (б) из состояния автомата, соответствующей вершине v, тоже есть переход по этому символу, то одновременно выполняется переход как в дереве, так и в автомате. При этом состояние автомата ставится в соответствие новой вершине луча.
Если в ходе работы алгоритма автомат оказывается в заключительном состоянии, это означает, что найден очередной набор вхождений РВ в текст: каждый лист поддерева, в корне которого мы находимся, соответствует одному вхождению. Пример показан на рисунке 4.1.
Повышение скорости поиска достигается за счёт того, что совпадающие подстроки в луче слиты вместе, в результате чего обрабатываются только один раз. В [53] выполнен достаточно нетривиальный анализ временной сложности поиска и показано, что в среднем она составляет: где r = log2X 1Д = maxid il), t = maxj(m,-l, для которых Щ =Х),Х\- собственные значения матрицы инцидентности Н графа автомата, nij - их кратности. Основная значимость данного результата заключается в том, что временная сложность поиска в луче по регулярному выражению оказывается в среднем сублинеарной.
Существенным недостатком описанного подхода является тот факт, что не все регулярные выражения близки к "среднему случаю". Так, на практике достаточно часто встречаются РВ, содержащие подвыражения . и т.п. При этом возможна необычная ситуация, когда поиск с использованием индекса будет выполняться за 0(п2), тогда как без индекса - всего лишь за О(п). Для примера возьмем регулярное выражение вида . а и текст, где символ а вообще отсутствует. При поиске такого выражения потребуется обойти практически всё дерево. Поскольку в процессе обхода просматриваются все символы на дугах, то общее время работы составит 0(п ).
Для решения этой проблемы в [53] предложен ряд эвристик, позволяющих при необходимости переходить от использования индекса к традиционному поиску. Кроме того, в [53] выделен класс регулярных выражений, поиск по которым гарантированно и в худшем случае вьшолняется за время, пропорциональное их длине. Авторы назвали их префиксными регулярными выражениями.
Определение 4.1 Префиксное регулярное выражение (PRE) рекурсивно определяется следующим образом [53]: 0 - PRE, означает пустое множество слов G (пустая строка) - PRE, означает множество {є} Для каждого символа а є X выражение а является PRE и задаёт множество {а} Если р и q - PRE, задающие множества Р и Q, г — произвольное регулярное выражение, задающее множество R, такое что с є R, и х є X, то следующие выражения являются PRE: о pq (объединение) - задаёт множество PuQ о хр (конкатенация с символом слева) — задаёт множество хР о рг (конкатенация с є-регулярньїм выражением справа) - задаёт множество . PR о р (замыкание Клини) — задаёт множество Р . Например, выражение ab(bc [d+f(ab)) - префиксное, тогда как аХ Ь таковым не является.
Определение 4.2 Основное свойство PRE [53] заключается в том, что существует уникальный конечный набор ключевых слов (prewords), таких, что: для любого другого слова в языке одно из этих слов является его собственным префиксом никакое ключевое слово не является собственным префиксом другого ключевого слова
Для проверки того, является ли выражение PRE, и поиска его ключевых слов, в [53] предложен рекурсивный алгоритм, описанный в виде набора правил, по которым несложно выполнить программную реализацию - он представлен в таблице 4.1.
Найденные ключевые слова объединяются в луч (пример луча над набором слов см. в главе I). Размер луча линейно зависит от длины исходного регулярного выражения. Построенный луч рассматривается как конечный автомат и используется для поиска по РВ описанным выше образом. Поиск в суффиксном . луче на соответствие префиксному регулярному выражению q не зависит от размера луча и выполняется за время 0([q).
Можно заметить, что префиксные регулярные выражения - лишь подмножество выражений, для которых может быть реализован высокоэффективный поиск по лучу. Например, выражение a(bjc)d+ является префиксным, тогда как похожее выражение (ab)cd+ - не является. При этом несложно придумать выражение, задающее тот же самый язык, но являющееся префиксным - например, (acbc)d+. Кроме того, даже РВ, задающие конечные языки, могут не являться префиксными - например, выражение (ab)(cjd).
В диссертации предлагается расширить класс префиксных регулярных выражений - включить в него все выражения, для которых выполняется основное свойство согласно определению 4.2. Будем называть такие выражения расширенными префиксными выражениями (EPRE).
Но, в отличие от PRE, где количество ключевых слов составляет 0(длина выражения), теперь в худшем случае зависимость будет экспоненциальной. Например, для выражения q= (ab)(ab)(ab)...(ab) количество ключевых слов равно 21ч /5. Поэтому на практике будем работать только с подмножеством EPRE, для которых это количество остаётся в приемлемых пределах. Пусть К — максимальное количество слов, которое является приемлемым для выполнения поиска в луче. К можно рассматривать как некоторый настраиваемый параметр, специфичный для конкретного приложения. Если в процессе извлечения ключевых слов из регулярного выражения их количество превысит К, будем полагать, что поиск в луче нельзя выполнить с требуемой эффективностью, и переключаться на алгоритм, описанный в следующем разделе.
