Введение

Дерево, содержащее все суффиксы заданного текста.

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

История

Концепция была впервые введена. Вместо суффикса, Вайнер хранил в своем трие идентификатор префикса для каждой позиции, то есть, кратчайшую строку, начинающуюся в и встречающуюся только один раз в . Его алгоритм D принимает несжатый трие для и расширяет его в трие для . Таким образом, начиная с тривиального трие для , трие для может быть построен последовательными вызовами алгоритма D; однако, общее время выполнения остается. Алгоритм Вайнера B поддерживает несколько вспомогательных структур данных, чтобы достичь общего времени выполнения, линейного по размеру построенного трие. Последний все еще может содержать узлов, например, для . Алгоритм Вайнера C, наконец, использует сжатые трие для достижения линейного общего размера хранилища и времени выполнения. Дональд Кнут впоследствии охарактеризовал последний как "Алгоритм 1973 года" по словам своего студента Вогана Пратта. В учебнике результаты Вайнера были воспроизведены в упрощенной и более элегантной форме, вводя термин "позиционное дерево". был первым, кто построил (сжатый) трие из всех суффиксов . Хотя суффикс, начинающийся в , обычно длиннее, чем идентификатор префикса, их представления путей в сжатом трие не отличаются по размеру. С другой стороны, МакКрейт мог обойтись без большинства вспомогательных структур данных Вайнера; остались только суффиксные ссылки. еще больше упростил конструкцию. Он предоставил первую онлайн-конструкцию деревьев суффиксов, теперь известную как алгоритм Укконена, с временем выполнения, соответствующим самым быстрым алгоритмам того времени. Эти алгоритмы являются линейными по времени для алфавита постоянного размера и имеют наихудшее время выполнения в общем случае. дал первый алгоритм построения дерева суффиксов, который оптимален для всех алфавитов. В частности, это первый алгоритм с линейным временем для строк, взятых из алфавита целых чисел в полиномиальном диапазоне. Алгоритм Фараха стал основой для новых алгоритмов построения как деревьев суффиксов, так и суффиксных массивов, например, для внешней памяти, сжатых, компактных и т.д.

Параллельное строительство

Были предложены различные параллельные алгоритмы для ускорения построения суффиксного дерева. Недавно был разработан практический параллельный алгоритм для построения суффиксного дерева с объемом работы (последовательным временем) и длиной критического пути. Алгоритм демонстрирует хорошую масштабируемость при параллельном выполнении на многоядерных машинах с общей памятью и способен проиндексировать геном человека объемом около 3 ГБ менее чем за 3 минуты, используя 40-ядерный компьютер.