В 1973 году Питером Вайнером была предложена новая структура данных — суффиксное дерево. Суффиксное дерево оказалось необычайно полезной структурой данных — в частности, с помощью суффиксных деревьев Вайнеру удалось опровергнуть гипотезу Дональда Кнута о том, что наибольшее общее подслово двух слов нельзя найти за линейное время. Мы начнем с краткого введения в суффиксные деревья.
Оставшаяся часть времени будет посвящена трем задачам.
Первая задача, которую мы рассмотрим, состоит в поиске документов, содержащих вхождения некоторого образца. Мы поймем, как решать эту задачу с использованием оптимального времени и памяти [1].
Вторая и очень важная задача — задача построения суффиксных деревьев. Конечно, еще Вайнер показал, что суффиксные деревья можно строить за линейное время. Впоследствии, было предложено еще несколько алгоритмов построения суффиксных деревьев, в том числе, знаменитый алгоритм Укконена. Все эти алгоритмы читают слово буква за буквой и на каждом шаге достраивают текущее дерево так, чтобы получить суффиксное дерево прочитанной части слова. Недостаток этих алгоритмов состоит в том, что на один шаг в худшем случае можно потратить линейное время. Существует ли алгоритм, который на каждый шаг тратит лишь константу времени — открытая проблема. Мы обсудим лучший из существующих алгоритмов [2].
В свете большого количества приложений суффиксных деревьев очень важно хорошо понимать их свойства. В частности, хотелось бы научиться определять, является ли заданное дерево суффиксным деревом. Эта задача, последняя из тех, что мы рассмотрим, еще открыта. Тем не менее, существуют подходы, позволяющие решить эту задачу при условия наличия некоторой дополнительной информации. О них мы и поговорим [3].
