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 символов на ребре искомой подстроке (или части искомой подстроки, если длина ребра меньше искомой подстроки).