В Oracle был создан новый TYPE, который реализует функции интерфейса ODCIIndex, отвечающего за взаимодействие СУБД с пользовательским индексом. Также реализованы функции-обёртки PL/SQL, вызывающие соответствующие методы в JVM. Одним из завершающих этапов реализации было создание функции поиска подстроки в строках таблицы, использующей новый TYPE, а также создание оператора, использующего эту функцию. После чего был успешно создан пользовательский INDEXTYPE, а далее INDEX. При создании INDEX, ОСД было построено без ошибок, таким образом, считаем, что этап реализации нового типа индекса проведен успешно.

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

Для исследования, создадим индекс для таблицы text_table, столбца text (см. Листинг 3.11).

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

Для того, чтобы определить увидеть, что функция поиска строк, содержащих искомую подстроку, вызывается и отрабатывает верно, сделаем следующий запрос: select text from text_table where contains_op(text, 'they') = 1;

Запрос возвращает все строки, содержащие в себе подстроку «they». Результат выполнения запроса показан на рисунке 4.1.

Рис. 4.1 Результат поиска строк с подстрокой «they».

Результат верный, попробуем сделать еще один запрос, уже с другой подстрокой - «be»: select text from text_table where contains_op(text, 'be') = 1;

Результат также верен, он показан на рисунке 4.2.

Рис. 4.2 Результат поиска строк с подстрокой «be»

Согласно требованиям, к создаваемому индексу, таблица не может изменяться, проверим это, попытавшись удалить стоку из таблицы text_table. Результат выполнения запроса возвращает ошибку, означающую, что индекс не смог обновиться. Результат показан на рисунке 4.3.

Рис. 4.3 Результат запроса на удаления строки из индексируемой таблицы

Для получения оценки и плана запроса, выполним следующие команды:

set autotrace traceonly explain

select text from text_table where contains_op(text, 'a') = 1;

Результат показан на рисунке 4.4.

Рис. 4.4 Оценка запроса, применяющего пользовательский индекс

Для сравнения, выберем индекс Oracle Text, с его оператором contains(). Oracle Text поставляется с СУБД начиная с 11 версии. Для того чтобы построить индекс над таблицей text_table2 (копия text_table), выполним следующую команду:

CREATE INDEX docs_idx ON text_table2 (text) INDEXTYPE IS ctxsys.context;

Время построения индекса Oracle Text несколько ниже, (процентов на 20-25), но только потому, что jvm проводит сериализацию ОСД, а это достаточно затратная операция. Если провести сравнения, без сохранения ОСД, то индекс на основе ОСД, строится за время, меньшее чем Oracle Text, процентов на 5-10%.

Сравним полученные метрики нового индекса с метриками индекса Oracle Text. Запросы аналогичны приведенным выше, их результат показан на рисунке 4.5.

Рис. 4.5 Оценка запроса, применяющего oracle text индекс

Как видим из рисунков 4.4 и 4.5, планы запросов схожи, различие лишь в графе Cost - у пользовательского индекса стоимость чуть ниже, чем у Oracle Text. Скорость выполнения запросов у двух индексов, примерно одинаковы.

Выводы по главе 4: В данной главе, был протестирован новый тип индекса, на основе ОСД. Согласно полученным результатам запросов, делаем вывод, что алгоритм построения ОСД и поиска в нём работает корректно, т.к. вернувшиеся строки индексируемого столбца в действительности содержат искомую подстроку. Подтвердили эмпирическим путем, что скорость построения ОСД линейна, что соответствует теории. Установили, что Oracle Text затрачивает чуть больше ресурсов ЦПУ. Скорость индексов при поиске подстроки примерно одинакова. Однако Oracle Text строит индекс несколько быстрее, поскольку значительное время jvm тратит на сохранение ОСД.

Заключение

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

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

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

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

В Oracle был создан новый TYPE, который реализует функции интерфейса ODCIIndex, отвечающего за взаимодействие СУБД с пользовательским индексом. Также реализованы функции-обёртки PL/SQL, вызывающие соответствующие методы в JVM. Одним из завершающих этапов реализации было создание функции поиска подстроки в строках таблицы, использующей новый TYPE, а также создание оператора, использующего эту функцию. После чего был успешно создан пользовательский INDEXTYPE, а далее INDEX. При создании INDEX, ОСД было построено без ошибок, таким образом, считаем, что этап реализации нового типа индекса проведен успешно.

Выводы по главе 4: Был протестирован новый тип индекса, на основе ОСД. Согласно полученным результатам запросов, делаем вывод, что алгоритм построения ОСД и поиска в нём работает корректно, т.к. вернувшиеся строки индексируемого столбца в действительности содержат искомую подстроку. Подтвердили эмпирическим путем, что скорость построения ОСД линейна, что соответствует теории. Установили, что Oracle Text затрачивает чуть больше ресурсов ЦПУ. Скорость индексов при поиске подстроки примерно одинакова. Однако Oracle Text строит индекс несколько быстрее, поскольку значительное время jvm тратит на сохранение ОСД.

Для достижения поставленной цели в данной работе решены следующие задачи:

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

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

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

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

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

1. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Д. Гасфилд; Пер. с англ. СПб.: Невский Диалект; БХВ-Петербург, 2003. 654 с.

2. Gusfield, Dan. Strmat / Dan Gusfiels // http://www.cs.ucdavis.edu /~gusfield/strmat.html

3. Giegerich, Robert. Efficient implementation of lazy suffix trees / Robert Giegerich, Stefan Kurtz, Jens Stoye // In the Proc. of 3rd Intl. Workshop on Algorithm Engineering. Lecture Notes in Computer Science. Vol. 1668. 1999. P.30-42.

4. Андрианов И.А. Анализ и разработка способов индексирования текстов на основе обобщенных и неплотных суффиксных деревьев

5. Kurtz, S. Reducing the space requirements of suffix trees / S. Kurtz // Software - Practice and Experience. 1999. Vol. 29. P.1149-1171.

6. Смит Б. Методы и алгоритмы вычислений на строках = Computing Patterns in Strings. М.: Вильямс, 2006. 496 с.

7. Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер. с англ. И. В. Романовского. 2-е изд. СПб.: Невский Диалект, 2003. 654 с.

8. Окулов С. М. Алгоритмы обработки строк. М.: Бином, 2013. 255 с

9. Электронный источник: https://marknelson.us/posts/1996/08/01/suffix-trees.html - Fast String Searching With Suffix Trees

10. Ключаев, А.А., Матьяш, В.А., Щекин, С.В. Структуры и алгоритмы обработки данных: учебное пособие / А.А. Ключаев, В.А. Матьяш, С.В. Щекин. СПб.: СПбГУАП, 2003. 172 с.

11. Кузнецов, С.Д. Методы сортировки и поиска / С.Д. Кузнецов // http://citforum.ru/programming/theory/sorting/sorting1.shtml

12. Айткулов П.Г. Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных / П.Г. Айткулов; дис. … канд. техн. наук. Москва: Институт проблем управления им. В. А. Трапезникова РАН, 2010. 97 с.

13. Maab, M. Suffix Trees and their Applications / M. Maab // Technische Universi at M unchen. 1999.

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

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

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

Размещено на Allbest.ru