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

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

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

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

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

Аннотация

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

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

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

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