Выводы по Главе 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