Для того чтобы уменьшить количество обращений к обобщенной строке для сравнения символов, добавим в 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) {