Размещено на http://www.allbest.ru/



Оглавление

суффиксный индекс индексация алгоритм

Введение

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

1.1 Цель индексирования текста

1.2 Типы индексов

2. Проектирование предлагаемой структуры индекса

2.1 Обобщенное суффиксное дерево

2.2 Алгоритм построения ОСД

2.3 Терминальный символ для ОСД

2.4 Сокращения обращений к обобщенной строке

2.5 Алгоритм поиска ребра, содержащего искомую подстроку

2.6 Получение ИД строки из ОСД

2.7. Применение ОСД в Extensible Indexing СУБД Oracle

3. Реализация структуры индекса на основе суффиксного дерева

3.1 Реализация структуры индекса на языке Java

3.2 Реализация TYPE в СУБД Oracle

4. Исследование полученных результатов

Заключение

Список используемых источников



Введение

Сегодня огромную роль играют системы информационного поиска, позволяющие осуществлять быстрый поиск нужных сведений в огромном количестве информации. Подобные системы постоянно улучшаются как за счёт прогресса в области аппаратных средств, так и за счёт модернизации заложенных в них структур и алгоритмов. Совершенствуются и сами подходы к отбору информации, позволяя пользователю более гибко задавать то, что он хочет найти. Так, в дополнение к поиску слов и грамматических форм [1], развиваются возможности нечёткого поиска [2], использование в запросах шаблонов различного вида [3], поиск с учётом семантики [4] и др.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Разработан метод построения и использования обобщенных суффиксных деревьев в СУБД Oracle, основанный на алгоритме Укконена с применением в качестве терминального символа ROWID строки индексируемого столбца таблицы. Это позволяет однозначно отделить одну строку от другой при построении ОСД.

2. Также предложен способ хранения ОСД в таблице БД (в столбце типа BLOB), применив java сериализацию.

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

1. На основе выполненных исследований реализован индекс для ускорения поиска по подстроке. Для случая хранения данных в полях СУБД разработан и внедрен новый тип индекса. Особенность реализации заключается в том, что в индексе применен код на языке Java - в сети Интернет, подобных реализаций индексов для СУБД Oracle найдено не было, кроме информации о том, что код на Java может быть применен для этой задачи.

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

Апробация работы: на тему диссертационной работы было мной было опубликовано 2 статьи:

1. Применение суффиксных деревьев в поиске подстрок текста / II Международная научно-практическая конференция «Современная наука: актуальные вопросы, достижения и инновации» / 05.06.2018 г. Пенза, РФ

2. Исследование и разработка подходов к индексированию больших текстов в СУБД Oracle / Международный научно-практический журнал - «Теория и практика современной науки» / №12(42) Декабрь 2018

3. Разработка INDEXTYPE на языке Java для СУБД Oracle / Международный научно-практический журнал - «Теория и практика современной науки» / №7(49) Июль 2019

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



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

1.1 Цель индексирования текста

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

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

Развитие индексирования в документных системах происходило от ручного заполнения списка ключевых слов в системах первого поколения до автоматического полнотекстового индексирования сегодня, подразумевающего сохранение всех слов текста. Несмотря на большой пройденный путь говорить о полном решении проблемы, наверное, пока рано. Безусловно, удалось решить вопрос автоматического ввода документов в систему, но оставшиеся вопросы весьма омрачают картину. Число получаемых при поиске нерелевантных документов подчас достигает 90%, а размер индекса составляет в среднем не менее 40-60% объема документа. С учетом быстрого роста количества электронных документов острота этих проблем усиливается.

Методы индексирования документов

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

бинарное индексирование - не зависит от языка документа по причине бинарной или словарной индексации;

морфологическое индексирование - производится с учетом морфологии и семантики языка.

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

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

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

Большое количество “мусора” в индексе, т.е. слов, никак не характеризующих документ, а связывающих “ключевые” слова - а значит, возможное большое число нерелевантных документов при поиске при попадании шаблона на “мусор”.

Большой объем индекса за счет “мусора” - следовательно, расход ресурсов на его хранение и время на поиск по нему.

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

1.2 Типы индексов

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

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

Рисунок 1.1 Пример битовой карты

Достоинства индексов на основе битовых карт

1. Индексы на основе битовых карт обычно создаются быстрее, чем многие другие виды индексов.

2. Они могут быть крайне сжатыми в размерах (но это во многом зависит от конкретных данных).

3. Индексы на основе битовых карт крайне эффективны, если комбинировать несколько таких индексов по разным столбцам.

4. Каждая страница данных читается только 1 раз, независимо от сложности запроса и расположения данных в БД.

Недостатки и ограничения индексов на основе битовых карт

1. Идентификатор записи должен быть натуральным числом, т. о. невозможно совмещать индексы, основанные на битовых картах, с кластерными индексами.

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

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

HASH-ИНДЕКСЫ

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

Достоинства хеш-индексов

1. Быстрый поиск на точное равенство. По этому параметру хеш-индексы превосходят остальные типы индексов.

2. Небольшой размер индекса даже при индексации больших полей данных.

Недостатки и ограничения хеш-индексов

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

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

ИНДЕКСЫ НА ОСНОВЕ B-ДЕРЕВЬЯХ

Механизм классических B-деревьев был предложен в 1970 г. Бэйером и МакКрейтом [10]. В современных СУБД, B-деревья являются, пожалуй, самым распространенным методом доступа к данным.

B-дерево порядка p представляет собой совокупность иерархически связанных страниц внешней памяти (каждый узел дерева - страница), обладающая следующими свойствами [11]:

· Каждая страница содержит не более 2p элементов (идентификаторов строк с ключом).

· Каждая страница, кроме корневой, содержит не менее p элементов.

· Если внутренняя (не листовая) вершина B-дерева содержит m ключей, то у нее имеется m+1 страниц-потомков.

· Все листовые страницы находятся на одном уровне.

Достоинства индексов на основе B-деревьев

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

2. Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки. Т.е. B-дерево может обрабатывать запросы интервала данных, которые должны быть отсортированы в каком-нибудь порядке.

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

Недостатки и ограничения индексов на основе B-деревьев

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

2. Отсутствуют эффективные средства выборки данных (т.е. метода обхода дерева), упорядоченных по ключу, отличному от выбранного.

ИНДЕКСЫ НА ОСНОВЕ СУФФИКСНЫХ СТРУКТУР ДАННЫХ

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

В основе суффиксных поисковых структур лежит такая структура, как бор (рисунок 1.2).

Рисунок 1.2 Суффиксный бор

Множество возможных значений каждого символа называется алфавитом и обозначается У.

Как видно из рисунка 1.2, индексируемая строка «banana» дополнена терминальным символом вне алфавита ($). Такой прием используется, чтобы гарантировать взаимно однозначное соответствие между листьями бора и суффиксами строки [5].

Хотя время поиска подстроки является линейным, для построения бора требуется O(n2) операций, а для хранения - O(n2) памяти, что сильно ограничивает его практическое использование [12]. Для устранения недостатков бора обычно используется его сжатие. Для этого информация из узлов переносится на дуги, узлы степени 2 (за исключением корня) удаляются из дерева, а соответствующие дуги объединяются. Таким образом, каждая дуга в дереве соответствует некоторой подстроке индексируемого текста. Для такого сжатого бора используется термин суффиксное дерево (рисунок 1.3).

Рисунок 1.3 Суффиксное дерево

Суффиксное дерево T для строки s (где |s|=n) -- дерево с n листьями, обладающее следующими свойствами:

· каждая внутренняя вершина дерева имеет не меньше двух детей;

· каждое ребро помечено непустой подстрокой строки s;

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

· дерево должно содержать все суффиксы строки s, причем каждый суффикс заканчивается точно в листе и нигде кроме него.

Для суффиксных деревьев общие требования к памяти, по сравнению с бором, снижаются до O(n) [13], что расширяет возможности практического применения данной поисковой структуры.

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

Достоинства суффиксных структур данных

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

2. Высокая эффективность поиска строк (последовательностей символов) с логарифмической асимптотикой.

Недостатки суффиксных структур данных

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

2. Малое изменение (добавление, удаление или изменение одной записи) приводит к серьезной перестройке индекса [12], что ограничивает применение для динамических данных.

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

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



2. Проектирование предлагаемой структуры индекса

2.1 Обобщенное суффиксное дерево

Существует понятие обобщенного суффиксного дерева (ОСД) - это СД построенное над множеством строк текста.

Это главное отличие между ОСД и СД. Изначальное построение ОСД можно произвести построением СД следующим способом:

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

2) Далее все строки соединяются в одну и над ними строится суффиксное дерево (например Алгоритмом Укконена).

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

Также ОСД дает возможность удалить строку из себя, путем удаления листа u, соответствующего удаляемой строке. Если у родителя v листа u остался один потомок, то производится слияние ребер. Далее по суффиксной связи от v берется узел w и производится каннонизация. И так вплоть до корня дерева. Эта функция также не предусмотрена, по той же причине, которая была описана выше.



2.2 Алгоритм построения ОСД

Для нашей задачи важно построить ОСД минимум за линейное время, для этого существует несколько алгоритмов: алгоритм Вайнера (1973), алгоритм МакКрейга (1976), алгоритм Укконена (1995) и др.

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

Алгоритм Укконена (англ. Ukkonen's algorithm) -- алгоритм построения суффиксного дерева для заданной строки s за линейное время.

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

Общее описание алгоритма Укконена выглядит так:

Построить дерево T1

for i from 1 to m - 1 do begin {фаза i + 1}

for j from 1 to i + 1 begin {продолжение j}

найти в текущем дереве конец пути из корня с меткой S[j..i].

Если нужно, продолжить путь, добавив символ S(i + 1),

обеспечив появление строки S[j..i + 1] в дереве,

end;

end;[3]

При добавлении очередного суффикса возможны три варианта.

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

2. Если ребро есть и суффикс, который мы хотим добавить целиком лежит на нём, завершаем свою работу -- этот и дальнейшие суффиксы не являются уникальными.

3. Если ребро есть и суффикс не лежит на нём целиком, это значит, что нам нужно создать новую вершину посередине этого ребра, к которой подвесить старую вершину с конца ребра и новую вершину, соответствующую суффиксу. Стоит заметить, что ребро к новому листу в данный момент будет иметь длину, равную единице.[1]

Рассмотрим визуально как работает алгоритм Укконена, на примере слова “banana” (см. табл. 1)

Табл. 2.1

Построение СД алгоритмом Укконена (см. слева направо)

Получившиеся суффиксное дерево представлено на рисунке 2.1

Рисунок 2.1 Суффиксное дерево слова «bananna»

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

2.2 Проектирование суффиксного дерева

Обобщенное суффиксное дерево по определению строится над одной строкой S$, где S$ = s1$1 + s2$2 + … + si$i (i - кол-во строк).

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

Узлы будут представлены классом Node, а ребра - классом Edge.

Главный класс будет называться SuffixTree, который будет в себе содержать несколько полей: Массив узлов; Хэш-таблица ребер с ключом вида «индекс узла_код первого символа на ребре»; Хэш-таблица ребер с ключом - индекс конечного узла; Хэш-таблица терминальных строк, где ключ, порядковый номер строки в БД; Массив индексов начала терминальных строк, где индекс в массиве равен соответствующей ей строке в индексируемом столбце.

2.3 Терминальный символ для ОСД

ОСД строится алгоритмом Укконена, но для его применения в контексте СУБД, требуется внести некоторые изменение в алгоритм Укконена.

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

В качестве терминального символа можно применить последовательность символов, эта последовательность должна быть уникальна в рамках объединенной строки S$. Таким терминальным символом может быть значение rowId (для Oracle 11g длина rowId равна 18 символам), соответствующей строки в БД. Т.к. rowId всегда уникален, он соответствует требованиям к терминальному символу.

Таким образом, мы получаем rowId каждой строки, добавляем его в конец соответствующей строки, и объединяем строки в S$.

Для того, чтобы отметить суффиксы, которые начинаются с терминального символа (или с j символа терминального символа), будем сохранять индекс начала терминального символа в массив (размерность rowId определяется версией БД), где индекс ячейки в массиве - номер строки по порядку, значение ячейки - индекс начала терминального символа в C$.

После построения ОСД, просматриваем все суффиксы, если на исходящем ребре видим, что первый символ строки - это $, то помечаем ребро как valid = false; Таким образом, поиск по этому ребру дальше производится не будет.

Для быстрого ответа на вопрос, какой первый символ указан на ребре, применим бинарный поиск (сложность O(logN)). Массив с индексами начала $i у нас изначально отсортирован, значит такой поиск нам подойдет как нельзя лучше.

2.4 Сокращения обращений к обобщенной строке

При поиске подстроки в ОСД, нам требуется знать, соответствуют ли k символов на ребре искомой подстроке (или части искомой подстроки, если длина ребра меньше искомой подстроки).

Для того чтобы уменьшить количество обращений к обобщенной строке для сравнения символов, добавим в Edge хэш подстроки (int hash), которая в нем лежит. В случае если длина искомой подстроки S, равна или больше подстроки E, лежащей на ребре, то можно применить сравнение хэшей.

В случае если строка S в текущей фазе (под фазой подразумеваем i-ый переход по ребрам в процессе сравнения подстрок) больше подстроки E, сокращаем S на span символов с конца, высчитываем хэш S|i, n - span| и сравниваем его с хэшом E. Где span S|n| - E|n|.

При равной длине E и S, просто высчитываем хэш S и сравниваем с хешом E.

Хэш высчитывается каждый раз, когда создается новое ребро, либо, когда ребро разбивается, в процессе построения дерева.

2.5 Алгоритм поиска ребра, содержащего искомую подстроку

Хэш, о котором говорилось в п. 2.4 применяется в алгоритме поиска ребра, содержащего искомую подстроку. Словесно опишем этот алгоритм:

Если из корня (или узла i) не исходит ребра, начинающегося с первого символа искомой подстроки (или i-символа) - возвращается null. Иначе берем полученное ребро из хэш-таблицы, где ключ - startNodeIndex_intFirstChar.

Если длина подстроки ребра <= длине искомой подстроки, то высчитываем хэш искомой подстроки, как писалось в п.2.4., и сравниваем хэши. При совпадении возвращаем текущее ребро (если его длина меньше длины искомой подстроки). Иначе ищем подходящее ребро, исходящее из конечного узла текущего ребра. Далее алгоритм повторяется до тех пор, пока не будет установлено что искомая подстрока есть на ребрах ОСД или отсутствует.

2.6 Получение ИД строки из ОСД

Для того, чтобы идентифицировать те строки, которые содержат в себе подстроку S, требуется выполнить следующие действия:

1. Найти конечное ребро, которое соответствуют подстроке S (или его суффиксу, если искомая подстрока лежит на нескольких последовательных ребрах).

2. Из ребра Ei, на котором закончилось сравнение с S, спускаемся вниз по всем ребрам до тех пор, пока не достигнем листа (не достигнем $i).

3. Получить из листа значение его терминального символа.

Тут еще возможны следующие случаи:

Суффикс не был помечен как неверный, т.к. его начало содержится еще в какой-то из строк текста. Чтобы не получить в качестве ответа строку, в которой искомой подстоки нет, но она есть в его терминальном символе, мы на каждом дочернем ребре сверяем начальный символ (его индекс в S$) на принадлежность к $i. Если дочернее ребро начинается с первого символа $i, то такая строка нам подходит, т.к. это нам говорит о том, что S в строке i находится в конце текста.

Если же первый символ ребра соответствует $i(1,n), то можно сказать что S - подстрока $i (или S частично подстрока $i). Тогда строку i в перечень строк, подходящих под S, не попадает.

Когда первый символ ребра не соответствует $i, то такая строка соответствует запросу.

2.7 Хранение ОСД во внешней памяти

Для того, чтобы сохранить ОСД во внешней (постоянной) памяти, применим механизм сериализации java. Берется объект типа SuffixTree, сериализуется (переводится в массив байт) и сохраняется в новую таблицу БД в столбец с типом BLOB.

При первом запросе пользователя (в рамках сессии) к индексируемой таблице будет проверено, содержится ли объект SuffixTree в оперативной памяти СУБД, если нет, то будет произведена десериализация - чтение из таблицы поля BLOB, перевод его из массива байт в объект SuffixTree. Таким образом объект ОСД попадет в оперативную память и в дальнейшем ОСД будет браться оттуда.

2.8 Применение ОСД в Extensible Indexing СУБД Oracle

Индексы предметной области - по-английски в Oracle называется Extensible Indexing. Такие индексы позволяют создавать собственные индексные структуры, работающие так же, как и индексы, предлагаемые Oracle. Когда пользователь СУБД пишет CREATE INDEX с указанием вашего типа индекса (INDEXTYPE), Oracle выполнит код, написанный создателем INDEXTYPE, для генерации индекса. [15]

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

Extensible Indexing предоставляют возможность реализовать новый тип индекса, который пока еще не существует в базе данных. Например, если вы разрабатываете программное обеспечение, анализирующее графические изображения, которые хранятся в базе данных, и формируете сведения об этих изображениях, такие как найденные в них цвета, то можете создать собственный индекс на основе изображений. По мере добавления изображений в базу данных, ваш код вызывается для извлечения цветов из них и сохранения их в каком-нибудь месте (там, где пожелает создатель INDEXTYPE). Во время выполнения запроса, когда пользователь желает получить все изображения с конкретным цветом, Oracle обратится за ответом к вашему индексу.[15]

Обозначим, что нам требуется для создания такого индекса. Источником информации выступает англоязычная документация Oracle DB.

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

CREATE TYPE TextIndexMethods (

STATIC FUNCTION ODCIIndexCreate(...)...<функции ODCI интерфейса>);

Где TextIndexMethods - имя создаваемого типа.

Далее для TYPE TextIndexMethods создается BODY, в котором указанные на первом шаге методы реализуются. Создание BODY для созданного TYPE выглядит следующим образом:

CREATE TYPE BODY TextIndexMethods (...);

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

CREATE FUNCTION TextContains(Text IN VARCHAR2, Key IN VARCHAR2)

RETURN NUMBER AS

BEGIN

.......

END TextContains;

Тогда создание OPERATOR и INDEXTYPE будет выглядеть следующим образом:

CREATE OPERATOR Contains

BINDING (VARCHAR2, VARCHAR2) RETURN NUMBER USING TextContains;

CREATE INDEXTYPE TextIndexType

FOR Contains(VARCHAR2, VARCHAR2)

USING TextIndexMethods

WITH SYSTEM MANAGED STORAGE TABLES;

Тогда создание индекса будет выглядеть так:

CREATE INDEX ResumeIndex ON Employees(resume) INDEXTYPE IS TextIndexType;

Как видим, для создания предметного индекса нужно выполнить относительно малое число шагов. Основная работа связана с реализацией методов в BODY TYPE и с реализацией функции для оператора.

Как говорилось в этой главе, новый индекс, на основе ОСД, не будет поддерживать обновление/изменение индексируемой таблицы.

Поэтому такие методы нашего TYPE как: ODCIINDEXTRUNCATE, ODCIINDEXINSERT, ODCIINDEXDELETE, ODCIINDEXUPDATE - будут возвращать ошибку при попытке пользователя изменить индексируемую таблицу. Информация обо всех методах содержится в Приложении В.

Но такие методы как: ODCIINDEXCREATE (вызывается при создании индекса), ODCIINDEXDROP (вызывается при удалении индекса), ODCIINDEXSTART (вызывается перед началом сканирования индекса), ODCIINDEXFETCH (вызывается для сканирования индекса) - будут работать с java классом SuffixTree (кроме метода ODCIINDEXDROP). Для этого в Oracle существует механизм вызова java методов из методов PL/SQL. Такие методы обычно называют функциями-обёртками, т.к. они не делают ничего, кроме вызова внешних методов.

Метод ODCIINDEXCREATE будет вызывать функцию построения ОСД java для индексируемого столбца. Для того чтобы определить какая таблица и столбец требует построения индекса, СУБД самостоятельно передает в ODCIINDEXCREATE поле типа ODCIINDEXINFO, который содержит в себе информацию о нужной таблице, индексируемом столбце, имени индекса. Все это можно применить для обращения к нужному столбцу, далее конкатенации всех строк таблицы, создании ОСД и сохранении ОСД в новую таблицу для его хранения. Код будет приведен в главе 3 данной работы.

Метод ODCIINDEXDROP также содержит поле типа ODCIINDEXINFO, благодаря которому мы просто определим название таблицы с сохраненным ОСД, которую удалим средствами динамических запросов PL/SQL.

Метод ODCIINDEXSTART вызовет метод java, который считает ОСД из специальной таблицы, если ОСД нет в оперативной памяти СУБД.

Метод ODCIINDEXFETCH передает java методу поиска подстроки в ОСД искомую подстроку. От этого java-метода он ждет объект типа ODCIRIDLIST, представляющий собой массив rowId строк, удовлетворяющих запросу.

Стоит отметить, что все переводы из типов Oracle в тип Java и обратно, СУБД производит самостоятельно. Типы ODCIINDEXINFO, ODCIRIDLIST предоставлены jar библиотекой Oracle - odci.jar. Таким образом нам потребуется только подключить эту библиотеку в свой java проект командой import. В СУБД добавлять эту библиотеку не требуется, т.к. она уже там содержится изначально.

Выводы по главе 2: В данной главе, были сформулированы принципы построения ОСД, с учетом контекста его применения - в СУБД Oracle. Это такие принципы как: использование rowid (18 знаков) индексируемой строки в качестве терминального символа; способ получения всех rowid строк, содержащих искомую подстроку; построение ОСД алгоритмом Укконена над общей строкой, полученной посредством конкатенации всех строк (с терминальной строкой на конце) индексируемого столбца; сохранение ОСД в таблице БД. Рассмотрели правила создания Extensible Indexing (основываясь на документации СУБД Oracle) применимо к задаче данной работы. Выработали концепцию взаимодействия jvm с СУБД Oracle.



3. Реализация структуры индекса на основе суффиксного дерева

Реализация индекса на основе ОСД состоит из следующих этапов:

1. Написание процедуры построения ОСД алгоритмом Укконена на ЯП Java;

2. Написание функции для поиска подстроки в ОСД;

3. Написание функций сохранения и чтения ОСД из постоянной памяти (таблицы БД) на ЯП Java;

4. Написание функций-оберток в СУБД Oracle для функций из п.1, п.2, п.3;

5. Написание INDEXTYPE, реализующего интерфейс ODCIIndex в СУБД Oracle;

6. Написание функции и оператора поиска подстроки в СУБД Oracle;

7. Создание INDEX из INDEXTYPE;

3.1 Реализация структуры индекса на языке Java

ОСД состоит из узлов (вершин, листьев и одного корня) Node, и рёбер Edge.

Node содержит в себе суффиксную ссылку suffix_node и массив своих потомков children.

Edge содержит какую-то подстроку из S$ в виде индекса первого и последнего символа в S$ (first_char_index и last_char_index). Также содержит индекс Node, из которой он исходит и индекс Node на которой заканчивается (start_node и end_node). Признак валидности - valid. И хэш своей подстроки - hash.

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

Более полный листинг представлен в Приложении А, в этой главе приведем листинг некоторых частей программы.

В листинге 3.1 представлена функция добавления префикса в ОСД.

Листинг 3.1 - Процедура добавления префикса в ОСД

private void addPrefix(Suffix active, int last_char_index) {

int parent_node;

int last_parent_node = -1;

for (; ; ) {

Edge edge;

parent_node = active.origin_node;

if (active.explicit()) {

edge = Edge.find(active.origin_node, T[last_char_index]);

if (edge != null) {

break;

}

} else {

edge = Edge.find(active.origin_node, T[active.first_char_index]);

int span = active.last_char_index - active.first_char_index;

if (T[edge.first_char_index + span + 1] == T[last_char_index]) {

break;

}

parent_node = edge.splitEdge(active);

}

Edge new_edge = new Edge(last_char_index, N, parent_node);

new_edge.insert();

if (last_parent_node > 0) {

nodeArrayList.get(last_parent_node).suffix_node = parent_node;

}

last_parent_node = parent_node;

if (active.origin_node == 0) {

active.first_char_index++;

} else {

active.origin_node = nodeArrayList.get(active.origin_node).suffix_node;

}

active.canonize();

}

if (last_parent_node > 0) {

nodeArrayList.get(last_parent_node).suffix_node = parent_node;

}

active.last_char_index++;

active.canonize();

Процедура, приведенная в Листинге 3.1 выполняет основную работу по построению ОСД.

Во второй главе данной работы, говорилось о том, что требуется пометить ребра, исходящие из корня, начинающиеся с $i. Код отметки таких ребер приведен в Листинге 3.2.

Для отметки ребра, добавим в объект Edge поле boolean valid.

Листинг 3.2 - функция пометки ложных суффиксов

public static void markInvalidEdge() {
TreeSet<Integer> children = nodeArrayList.get(0).children;

Edge edge = null;

for (Integer curChild: children) {

edge = edgeByEndNodeMap.get(curChild);

if (isTerms(edge.first_char_index) != -1) {

edge.valid = false;

}

}

}

Код метода, который возвращает индекс $i (вызывается, например, в Листинге 3.2), если ребро начинается с терминальной строки, приведен в Листинге 3.3.

Листинг 3.3 - определение $i символа

private static int isTerms(int first_char_index) {

int first = 0;

int last = terms_first_index.length - 1;

int ind = (first + last) / 2;

while (first <= last) {

if ((terms_first_index[ind] <= first_char_index) && ((terms_first_index[ind] + 18 - 1) >= first_char_index)) {

return ind;

}

if (first_char_index > terms_first_index[ind]) {

first = ind + 1;

}

if (first_char_index < terms_first_index[ind]) {

last = ind - 1;

}

ind = (first + last) / 2;

}

return -1;

}

В главе 2, говорилось о применении хэша, для сравнения подстроки лежащей на ребре с искомой подстрокой (для исключения посимвольного сравнения с S$). Хэш применяется при поиске ребра с искомой подстрокой.

Листинг поиска ребра, содержащего искомую подстроку (с применением хэша) приведен в Листинге 3.4

Листинг 3.4 - поиск ребра с искомой подстрокой

public static Edge contains(String search) {

if (search == null || search.length() == 0) {

return null;

}

char[] searchArray = search.toCharArray();

int last_char_index = 0; //индекс в искомой строке

Edge edge = Edge.find(0, searchArray[last_char_index]);

if ((edge == null) || !edge.valid) {

return null;

}

while (last_char_index < search.length()) {

if (edge == null) {

return null;

}

int edge_length = edge.last_char_index - edge.first_char_index + 1;

if (((search.length() - last_char_index) == edge_length) && (search.substring(last_char_index).hashCode() == edge.hash)) {

return edge;

}

for (int i = edge.first_char_index; (i <= edge.last_char_index) && (last_char_index < search.length()); i++) {

if (isTerms(i) != -1) {

return null;

}

if (searchArray[last_char_index] != SuffixTree.T[i]) {

return null;

}

last_char_index++;

}

if (last_char_index < search.length()) {

edge = Edge.find(edge.end_node, searchArray[last_char_index]);

}

}

return edge;

}

Учитывая специфику применения ОСД, приведем метод, который считывает данные из индексируемого столбца, и создает для них ОСД. Метод начинается с получения всех данных индексируемого столбца, потом выполняется создание общей строки с терминальными символами (см. Листинг 3.5). Далее происходит построение ОСД, перевод его в бинарный вид и сохранение ОСД в новой таблице в БД (см. Листинг 3.6).

Листинг 3.5 - Построение S$ из индексируемого столбца

String querySelect = "SELECT ROWID, " + colName + " FROM " + tableName;

StringBuilder stringBuilder = new StringBuilder();

Statement statement = connection.createStatement();

ResultSet resultSet = statement.executeQuery(querySelect);

ArrayList<Integer> idnx_terms = new ArrayList<Integer>();

int[] index_terms;

int indx = 0;

int lastIndex = 0;

while (resultSet.next()) {

String text = resultSet.getString(2);

String rowId = resultSet.getString(1);

stringBuilder.append(text).append(rowId);

idnx_terms.add(lastIndex + text.length());

lastIndex += 18 + text.length();

termsMap.put(indx, rowId);

indx++;

}

Как видим, из Листинга 3.5, получение данных из индексируемого столбца происходит посредством применения реализации JDBC библиотеки Oracle. В процессе прохождения по ResultSet, добавляем строку, её ROWID (в роли $) в StringBuilder. При этом, попутно заполняем массив idnx_terms, который хранит в себе индексы начала $, а также хэш-таблицу с терминальными строками, где ключ - номер строки.

Листинг 3.6 - Построение ОСД и сохранение его в таблицу

SuffixTree suffixTree = new SuffixTree(stringBuilder.toString(), index_terms, termsMap);

byte[] bytes = toByteArray(suffixTree);

String indexTableName = schemaName + "." + indexName;

String queryCreateTable = "CREATE TABLE " + indexTableName + "_TAB (colName VARCHAR2(50), st BLOB, PRIMARY KEY (colName))";

statement.executeUpdate(queryCreateTable);

String queryInsertTable = "INSERT INTO " + indexTableName + "_TAB VALUES (?, ?)";

PreparedStatement preparedStatement = connection.prepareStatement(queryInsertTable);

Blob blob = BLOB.createTemporary(connection, false, BLOB.DURATION_SESSION);

blob.setBytes(1, bytes);

preparedStatement.setString(1, tableName + "_" + colName);

preparedStatement.setBlob(2, blob);

preparedStatement.execute();

3.2 Реализация TYPE в СУБД Oracle

Для того, чтобы СУБД Oracle могла работать с java кодом, одним из методов является вызов следующей команды: CREATE OR REPLACE AND COMPILE JAVA SOURCE NAMED "SuffixTree" AS <Код на java>. После этого код скомпилирован, и его можно использовать внутри СУБД. Мы намеренно не приводим код, его можно увидеть в приложении А данной работы.

Согласно главе 2, сначала определяем TYPE (см. Листинг 3.4)

Листинг 3.4 - Создание TYPE

create or replace TYPE suffixtree_im AS OBJECT

(

frids SYS.ODCIRIDLIST,

searchStr VARCHAR2(1000),

STATIC FUNCTION ODCIGETINTERFACES(ifclist OUT SYS.ODCIOBJECTLIST) RETURN NUMBER,

STATIC FUNCTION ODCIINDEXCREATE

(ia SYS.ODCIINDEXINFO, parms VARCHAR2, env SYS.ODCIEnv) RETURN NUMBER,

STATIC FUNCTION ODCIINDEXTRUNCATE (ia SYS.ODCIINDEXINFO,

env SYS.ODCIEnv) RETURN NUMBER,

STATIC FUNCTION ODCIINDEXDROP(ia SYS.ODCIINDEXINFO,

env SYS.ODCIEnv) RETURN NUMBER,

STATIC FUNCTION ODCIINDEXINSERT(ia SYS.ODCIINDEXINFO, rid ROWID,

newval NUMBER, env SYS.ODCIEnv) RETURN NUMBER,

STATIC FUNCTION ODCIINDEXDELETE(ia SYS.ODCIINDEXINFO, rid ROWID, oldval NUMBER,

env SYS.ODCIEnv) RETURN NUMBER,

STATIC FUNCTION ODCIINDEXUPDATE(ia SYS.ODCIINDEXINFO, rid ROWID, oldval NUMBER,

newval NUMBER, env SYS.ODCIEnv) RETURN NUMBER,

STATIC FUNCTION ODCIINDEXSTART(SCTX IN OUT suffixtree_im, ia SYS.ODCIINDEXINFO,

op SYS.ODCIPREDINFO, qi SYS.ODCIQUERYINFO,

strt NUMBER, stop NUMBER, searchStr VARCHAR2,

env SYS.ODCIEnv) RETURN NUMBER,

MEMBER FUNCTION ODCIINDEXFETCH(SELF IN OUT suffixtree_im, nrows NUMBER,

rids OUT SYS.ODCIRIDLIST, env SYS.ODCIEnv)

RETURN NUMBER,

MEMBER FUNCTION ODCIINDEXCLOSE(env SYS.ODCIEnv) RETURN NUMBER

);

Где frids - лист rowed строк, удовлетворяющих искомой подстоке; searchStr - искомая подстрока.

Далее реализуем объявленные в TYPE suffixtree_im функции в TYPE BODY (см. Листинг 3.7).

Листинг 3.7 - Реализация TYPE BODY suffixtree_im

create or replace TYPE BODY suffixtree_im

IS

STATIC FUNCTION ODCIGETINTERFACES(ifclist OUT SYS.ODCIOBJECTLIST)

RETURN NUMBER IS

BEGIN

ifclist:= SYS.ODCIOBJECTLIST(SYS.ODCIOBJECT('SYS','ODCIINDEX2'));

RETURN ODCICONST.SUCCESS;

END ODCIGETINTERFACES;

STATIC FUNCTION ODCIINDEXCREATE (ia SYS.ODCIINDEXINFO, parms VARCHAR2, env SYS.ODCIEnv) RETURN

NUMBER

IS

stmt VARCHAR2(4000);

BEGIN

DBMS_OUTPUT.PUT_LINE('Start create index');

stmt:= createIndex(ia);

DBMS_OUTPUT.PUT_LINE(stmt);

RETURN ODCICONST.SUCCESS;

END;

STATIC FUNCTION ODCIINDEXDROP(ia SYS.ODCIINDEXINFO, env SYS.ODCIEnv) RETURN NUMBER IS

stmt VARCHAR2(2000);

BEGIN

stmt:= 'DROP TABLE ' || ia.INDEXSCHEMA || '.' || ia.INDEXNAME || '_TAB';

EXECUTE IMMEDIATE stmt;

RETURN ODCICONST.SUCCESS;

EXCEPTION

WHEN OTHERS THEN

RETURN ODCICONST.SUCCESS;

END;

STATIC FUNCTION ODCIINDEXSTART(SCTX IN OUT suffixtree_im, ia SYS.ODCIINDEXINFO,

op SYS.ODCIPREDINFO, qi SYS.ODCIQUERYINFO,

strt NUMBER, stop NUMBER, searchStr VARCHAR2,

env SYS.ODCIEnv) RETURN NUMBER IS

stmt VARCHAR2(2000);

BEGIN

DBMS_OUTPUT.PUT_LINE(searchStr);

SCTX:= suffixtree_im(SYS.ODCIRIDLIST(), searchStr);

stmt:= readSt(ia);

DBMS_OUTPUT.PUT_LINE(stmt);

RETURN ODCICONST.SUCCESS;

END;

MEMBER FUNCTION ODCIINDEXFETCH(SELF IN OUT suffixtree_im, nrows NUMBER,

rids OUT SYS.ODCIRIDLIST, env SYS.ODCIEnv) RETURN NUMBER IS

BEGIN

DBMS_OUTPUT.PUT_LINE('Find ' || SELF.searchStr);

IF (SELF.frids.count > 0) THEN

RETURN ODCICONST.SUCCESS;

END IF;

rids:= containsStr(SELF.searchStr);

SELF.frids:= rids;

RETURN ODCICONST.SUCCESS;

END;

MEMBER FUNCTION ODCIINDEXCLOSE(env SYS.ODCIEnv) RETURN NUMBER IS

BEGIN

DBMS_OUTPUT.PUT_LINE('Close');

RETURN ODCICONST.SUCCESS;

END;

END;

Функции ODCIINDEXTRUNCATE, ODCIINDEXINSERT, ODCIINDEXDELETE, ODCIINDEXUPDATE не приведены, т.к. согласно главе 2, реализация индекса не поддерживает данные операции - все функции возвращают ODCICONST.ERROR.

Далее, согласно п.4 перечня шагов по созданию индекса, реализуем функции-обёртки, вызывающие определенные методы в JVM.

Это такие методы как:

1. containsStr(seacrh IN VARCHAR2) - возвращает лист rowid строк, содержащих искомую подстроку.

2. createIndex(ia IN SYS.ODCIINDEXINFO) - создает ОСД для инексируемого столбца, возвращает результат операции.

3. readSt(ia IN SYS.ODCIINDEXINFO) - читает ОСД из таблицы БД, если ОСД нет в оперативной памяти, возвращает служебную информацию о том, где производилось чтение (таблица/оперативная память).

Листинг методов приведен в Приложении Б.

Согласно п.6, реализуем функцию поиска подстроки containsTextFunc и оператор CONTAINS_OP, использующий функцию containsTextFunc (см. Листинг 3.8, 3.9).

Листинг 3.8 - Реализация функции поиска подстроки в строках таблицы



create or replace FUNCTION containsTextFunc(colText VARCHAR2, searchStr VARCHAR2, indexctx IN SYS.ODCIIndexCtx, scanctx IN OUT suffixtree_im, scanflg IN NUMBER)

RETURN NUMBER AS

frids SYS.ODCIRIDLIST;

size_list INTEGER;

BEGIN

DBMS_OUTPUT.PUT_LINE('containsTextFunc');

IF (indexctx.IndexInfo IS NOT NULL) THEN

DBMS_OUTPUT.PUT_LINE(searchStr);

frids:= scanctx.frids;

size_list:= frids.count;

DBMS_OUTPUT.PUT_LINE('Size list: ' || size_list);

FOR i in 1.. size_list LOOP

IF (indexctx.rid = frids(i)) THEN

RETURN 1;

END IF;

END LOOP;

RETURN 0;

ELSE

RAISE_APPLICATION_ERROR(-20101, 'A column that has a domain index of' ||

' Position indextype must be the first argument');

END IF;

END;

Где colText - название индексируемого столбца, searchStr - искомая подстрока, indexctx - контекст используемого индекса (неявный аргумент), scanctx - экземпляр нового TYPE suffixtree_im (неявный аргумент), scanflg - флаг сканирования (неявный аргумент). Примечание: неявным аргументом называем такой аргумент, который передает сама СУБД Oracle, это значит, что пользователю не надо его передавать явно.

Листинг 3.9 - Реализация оператора поиска подстроки в строках таблицы

CREATE OR REPLACE OPERATOR "SYSTEM"."CONTAINS_OP" BINDING

(VARCHAR2, VARCHAR2) RETURN NUMBER

WITH INDEX CONTEXT, SCAN CONTEXT "SYSTEM"."SUFFIXTREE_IM"

USING "CONTAINSTEXTFUNC"

Здесь мы командой «WITH INDEX CONTEXT, SCAN CONTEXT "SYSTEM"."SUFFIXTREE_IM"» определяем, чтобы названные выше аргументы (indexctx, scanctx, scanflg) передавались самой СУБД Oracle.

Теперь создаем новый INDEXTYPE contains_indextype, используя новый оператор CONTAINS_OP и TYPE suffixtree_im (см. Листинг 3.10).

Листинг 3.10 - Создание INDEXTYPE contains_indextype

CREATE INDEXTYPE contains_indextype

FOR contains_op(VARCHAR2, VARCHAR2)

USING suffixtree_im;

Когда contains_indextype создан, мы можем создать INDEX. Для примера берется таблица text_table со столбцом text (см. Листинг 3.11).

Листинг 3.11 - Создание INDEX text_index

CREATE INDEX text_index ON text_table(text)

INDEXTYPE IS contains_indextype;

Индекс успешно создан, теперь можно переходить к исследованию полученных результатов (Глава 4).

Выводы по Главе 3: В этой главе, мы реализовали алгоритм построения ОСД (на основе алгоритма Укконена) и поиска строк с заданной подстрокой в нем (алгоритмы были описаны в Главе 2 данной работы). Также встроили эту реализацию в СУБД Oracle, добавив функционал записи ОСД в таблицу, чтения из неё, а также добавив метод построения ОСД из строк индексируемого столбца. Для всего этого использовалась библиотека JDBC Oracle.

...