УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Биоинформатика
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



   Главная / Дипломы / Обработка строк на основе суффиксных автоматов (версия для печати)


Обработка строк на основе суффиксных автоматов



© 2007 Д.A. Паращенко

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Бакалаврская работа
Исходные коды

Аннотация

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

В настоящей работе разработан достаточно простой алгоритм построения суффиксного дерева за линейное время, содержащий в качестве одного из своих этапов построение суффиксного автомата. Таким образом, помимо алгоритмов Вайнера, Мак-Крейта и Укконена предложен еще один алгоритм построения суффиксного дерева за линейное время. Кроме этого в работе проведено сравнение времени их работы, а также сложности их реализации.

Поясним как появилась идея использовать суффиксный автомат для решения рассматриваемой задачи. Ввиду того, что суффиксные деревья и суффиксные автоматы являются родственными структурами данных (суффиксный автомат является минимизированным суффиксным бором, а суффиксное дерево - сжатым суффиксным бором), то авторы посчитали целесообразным для решения строковых задач вместо суффиксных деревьев использовать суффиксные автоматы. Одним из преимуществ этого подхода является тот факт, что суффиксный автомат является более простой структурой данных, а алгоритм его построения значительно проще в реализации, чем алгоритм построения суффиксного дерева.

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




© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com