Регистрация / Вход
Прислать материал

Суффиксное дерево

Сведения об участнике
ФИО
Быкова Екатерина Павловна
Вуз
Федеральное государственное бюджетное образовательное учреждение высшего образования «Бурятский государственный университет»
Тезисы (информация о проекте)
Область наук
Информационные технологии и вычислительные системы
Раздел области наук
Информатика
Тема
Суффиксное дерево
Резюме
Суффиксное дерево – мощная структура данных, позволяющая эффективно решать большое количество сложных поисковых задач.
В данной работе рассмотрены стандартные, часто применимые на практике строковые задачи и алгоритмы их решения, основанные на создании текстового индекса в виде суффиксного дерева.
Продемонстрирована эффективность использования суффиксного дерева при решении строковых задач. На примере конкретной задачи показаны значительные преимущества работы суффиксного дерева в сравнении с более простыми строковыми структурами.
Представлена программная реализация часто встречающегося на практике приложения суффиксного дерева – поиск всех вхождений образцов в тексте.
Ключевые слова
суффиксное дерево, строковые структуры
Цели и задачи
Целью данной работы является изучение суффиксного дерева и его приложений, оценка эффективности алгоритмов, основанных на использовании суффиксного дерева.
Задачи: 
1. Описать теоретические основы суффиксного дерева.
2. Рассмотреть стандартные строковые задачи и алгоритмы их решения, основанные на создании текстового индекса в виде суффиксного дерева.
3. Провести анализ эффективности работы этих алгоритмов.
4. Написать программную реализацию использования суффиксного дерева при решении конкретной задачи, и продемонстрировать быстродействие суффиксного дерева в сравнении с более простыми строковыми алгоритмами и конструкциями.
Введение

Эффективные структуры данных и алгоритмы для обработки строк и последовательностей являются актуальным объектом исследования в настоящее время. Это объясняется потребностями практики в разработке информационно-поисковых систем, при решении многих задач анализа геномных данных в биоинформатике и других областях, где требуется быстрая обработка большого количества длинных строк.

Для ускорения или даже обеспечения возможности решения строковых задач предварительно строится так называемый текстовый индекс. Текстовый индекс – это дополнительная структура данных, которая в компактном виде хранит информацию о тексте.

Одним из перспективных подходов организации текстовых индексов является использование суффиксных деревьев.

Методы и материалы

Первая и вторая главы работы имеют теоретический характер.

Первая глава посвящена анализу предметной области, подробно рассмотрены теоретические основы суффиксных деревьев, а именно:

1) дано и подробно разобрано определение суффиксного дерева;

2) рассмотрен вопрос об объеме занимаемой им памяти;

3) рассмотрен алгоритм построения суффиксного дерева, на котором будет основана программная реализация решений задач в данной работе.

 

Во второй главе описываются стандартные, часто применимые на практике строковые задачи:

1) поиск вхождений образца;

2) поиск наибольшей общей подстроки;

3) поиск документов по образцу.

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

 

В третьей главе представлена практическая часть данной работы. Здесь применяются методы из области алгоритмов обработки слов.

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

Далее представлена программная реализация одного из приложений - поиска вхождений образца. При реализации решения данной задачи используются теоретические сведения из первых двух глав.  

Описание и обсуждение результатов

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

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

В работе представлена программная реализация решения задачи на языке программирования С++ в среде Microsoft Visual Studio Express 2013.

Результаты тестирования таковы: для длины слова 5000 программа работает в худшем случае за 0,015 сек. По решению поставленной задачи можно судить о скорости построения суффиксного дерева. Данная реализация работает достаточно быстро. При грубой оценке можно сказать, что она построит суффиксное дерево для строки из 100000000 символов всего за 5 минут.

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

Используемые источники
Лифшиц Ю. Построение суффиксного дерева за линейное время. Лекция № 1 курса «Алгоритмы для Интернета» / Ю. Лифшиц – 2006.
Простое суффиксное дерево / 2015. URL: https://habrahabr.ru/post/258121/
Свиньин С. Применение равномерно разреженных суффиксных деревьев для задач обработки строк/ C. Свиньин, И. Андрианов – 2014.
Сжатое суффиксное дерево/ 2016. URL: https://neerc.ifmo.ru/wiki/index.php?title=Сжатое_суффиксное_дерево
Стариковская Т. Cуффиксные деревья: новые идеи и открытые проблемы / Т. Стариковская – 2014. URL: https://compscicenter.ru/media/slides/2014_2014_spring/2014_02_23_ 2014 _2014_spring.pdf
Стариковская Т. Эффективные алгоритмы для некоторых задач обработки слов / Т. Стариковская – Москва, 2013.
Суффиксное дерево. Алгоритм Укконена. / 2015. URL: http://codeforces.com/blog/entry/16780?locale=ru
Information about the project
Surname Name
Bykova Ekaterina
Project title
Suffix tree
Summary of the project
Suffix tree - a powerful data structure that allows you to deal effectively with a large number of complex search tasks.
This paper discusses the standard string problems and algorithms for their solution using suffix tree.
The research shows the effectiveness of using suffix tree for solving string problems. In the particular example shown significant advantages of suffix tree in comparison with simpler string structures.
Also represented software implementation of a problem of finding all occurrences of the text samples. This problem is very common in practice.
Keywords
suffix tree, string structures