Оглавление
суффиксный индекс индексация алгоритм
Введение
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. Быстрый поиск на точное равенство. По этому параметру хеш-индексы превосходят остальные типы индексов.