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

редактировать

Дерево суффиксов для текста BANANA. Каждая подстрока заканчивается специальным символом $. Шесть путей от корня к листьям (показаны в виде прямоугольников) соответствуют шести суффиксов A$, NA$, ANA$, NANA$, ANANA$ и BANANA$. Цифры на листьях указывают начальную позицию соответствующего суффикса. При построении используются суффиксные ссылки, нарисованные пунктиром.

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

Построение такого дерева для струны требует времени и пространства линейно по длине. После построения можно быстро выполнить несколько операций, например, поиск подстроки в, поиск подстроки, если допустимо определенное количество ошибок, поиск совпадений для шаблона регулярного выражения и т. Д. Суффиксные деревья также предоставляют одно из первых решений для линейного времени. для самой длинной общей проблемы с подстрокой. За это ускорение приходится платить: для хранения дерева суффиксов строки обычно требуется значительно больше места, чем для хранения самой строки. ${\ displaystyle S}$ $S$ ${\ displaystyle S}$ $S$ ${\ displaystyle S}$ $S$

СОДЕРЖАНИЕ

1 Определение
2 История
3 Функциональность
4 Приложения
5 Реализация
6 Параллельная конструкция
7 Внешняя конструкция
8 См. Также
9 Примечания
10 Ссылки
11 Внешние ссылки

Определение

Дерево суффиксов для строки длины определяется как дерево, такое что: ${\ displaystyle S}$ $S$ ${\ displaystyle n}$ $п$

На дереве ровно n листьев, пронумерованных от до. ${\ displaystyle 1}$ $1$ ${\ displaystyle n}$ $п$
За исключением корня, каждый внутренний узел имеет не менее двух дочерних узлов.
Каждое ребро помечено непустой подстрокой. ${\ displaystyle S}$ $S$
Никакие два ребра, начинающиеся из узла, не могут иметь строковые метки, начинающиеся с одного и того же символа.
Строка, полученная путем объединения всех строковых меток, найденных на пути от корня до листа, обозначает суффикс для от до. ${\ displaystyle i}$ $я$ ${\ displaystyle S [i..n]}$ ${\ displaystyle S [i..n]}$ ${\ displaystyle i}$ $я$ ${\ displaystyle 1}$ $1$ ${\ displaystyle n}$ $п$

Поскольку такое дерево существует не для всех строк, оно дополняется терминальным символом, который не отображается в строке (обычно обозначается). Это гарантирует, что ни один суффикс не является префиксом другого, и что будут листовые узлы, по одному для каждого из суффиксов. Поскольку все внутренние некорневые узлы являются ветвящимися, таких узлов может быть не более n - 1, а всего n + ( n - 1) + 1 = 2 n узлов ( n листьев, n - 1 внутренних некорневых узлов, 1 корень). ${\ displaystyle S}$ $S$ $ ${\ displaystyle n}$ $п$ ${\ displaystyle n}$ $п$ ${\ displaystyle S}$ $S$

Суффиксные ссылки являются ключевой особенностью старых алгоритмов построения линейного времени, хотя в большинстве новых алгоритмов, основанных на алгоритме Фараха, суффиксные ссылки отсутствуют. В полном суффиксном дереве все внутренние некорневые узлы имеют суффиксную ссылку на другой внутренний узел. Если путь от корня к узлу представляет собой строку, где - одиночный символ, а является строкой (возможно, пустой), он имеет суффиксную ссылку на внутренний узел, представляющий. См., Например, суффиксную ссылку от узла к узлу на рисунке выше. Суффиксные ссылки также используются в некоторых алгоритмах, работающих на дереве. ${\ displaystyle \ chi \ alpha}$ $\ чи \ альфа$ ${\ displaystyle \ chi}$ $\ чи$ ${\ displaystyle \ alpha}$ $\альфа$ ${\ displaystyle \ alpha}$ $\альфа$ ANANA

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

История

Эта концепция была впервые введена Вайнером (1973). Вместо того, чтобы суффикс S [ я. . п ], Веинер хранится в его синтаксическом дереве префикса идентификатор для каждой позиции, то есть, самую короткая строка, начиная с I и происходящей только один раз в S. Его алгоритм D берет несжатое дерево для S [ k +1.. n ] и расширяет его в дерево для S [ k. . n ]. Таким образом, начиная с тривиального дерева для S [ n. . n ], дерево для S [1.. n ] может быть построено путем n -1 последовательных вызовов алгоритма D; однако общее время выполнения составляет O ( n ²). Алгоритм Вайнера B поддерживает несколько вспомогательных структур данных для достижения линейного времени выполнения по размеру созданного дерева. Последние по-прежнему могут быть O ( n ²) узлами, например, для S = a ⁿ b ⁿ a ⁿ b ⁿ $. Алгоритм Вайнера C, наконец, использует сжатые попытки для достижения линейного общего размера хранилища и времени выполнения. Дональд Кнут впоследствии охарактеризовал последний как «Алгоритм 1973 года». Текст книга Аха, Хопкрофт amp; Ульман (1974, Sect.9.5) воспроизведены результаты Weiner в упрощенном и более элегантной форме, вводя термин дерева позиции.

McCreight (1976) была первой, чтобы построить (сжатый) все синтаксическое дерево суффиксов S. Хотя суффикс, начинающийся с i, обычно длиннее, чем идентификатор префикса, их представления пути в сжатом дереве не различаются по размеру. С другой стороны, МакКрайт мог обойтись без большинства вспомогательных структур данных Вайнера; остались только суффиксные ссылки.

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

Фарач (1997) дал первый алгоритм построения суффиксного дерева, оптимального для всех алфавитов. В частности, это первый алгоритм линейного времени для строк, взятых из алфавита целых чисел в полиномиальном диапазоне. Алгоритм Фараха стал основой для новых алгоритмов построения как суффиксных деревьев, так и суффиксных массивов, например, во внешней памяти, сжатой, сжатой и т. Д.

Функциональность

Суффиксное дерево для строки длины может быть построено во времени, если буквы происходят из алфавита целых чисел в полиномиальном диапазоне (в частности, это верно для алфавитов постоянного размера). Для более крупных алфавитов время выполнения определяется сначала сортировкой букв, чтобы привести их в диапазон размера ; в общем, на это нужно время. Приведенные ниже затраты даны в предположении, что алфавит постоянный. ${\ displaystyle S}$ $S$ ${\ displaystyle n}$ $п$ ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$ ${\ Displaystyle О (п)}$ $На)$ ${\ Displaystyle О (п \ журнал п)}$ $O (п \ войти п)$

Предположим, что суффиксное дерево было построено для строки длины или что обобщенное суффиксное дерево было построено для набора строк полной длины. Ты можешь: ${\ displaystyle S}$ $S$ ${\ displaystyle n}$ $п$ ${\ Displaystyle D = \ {S_ {1}, S_ {2}, \ точки, S_ {K} \}}$ $D = \ {S_1, S_2, \ точки, S_K \}$ ${\ displaystyle n = n_ {1} + n_ {2} + \ cdots + n_ {K}}$ ${\ displaystyle n = n_ {1} + n_ {2} + \ cdots + n_ {K}}$

Искать строки:
- Проверить, является ли строка длины подстрокой во времени. ${\ displaystyle P}$ $п$ ${\ displaystyle m}$ $м$ ${\ Displaystyle О (м)}$ $O (м)$
- Найдите первое вхождение паттернов общей длины в виде подстрок во времени. ${\ Displaystyle P_ {1}, \ точки, P_ {q}}$ $P_1, \ точки, P_q$ ${\ displaystyle m}$ $м$ ${\ Displaystyle О (м)}$ $O (м)$
- Найдите все вхождения паттернов общей длины как подстроки во времени. ${\ displaystyle z}$ $z$ ${\ Displaystyle P_ {1}, \ точки, P_ {q}}$ $P_1, \ точки, P_q$ ${\ displaystyle m}$ $м$ ${\ Displaystyle О (т + г)}$ $О (т + г)$
- Искать регулярное выражение P во времени, ожидаемом сублинейно в. ${\ displaystyle n}$ $п$
- Найдите для каждого суффикса шаблона длину самого длинного совпадения между префиксом и подстрокой во времени. Это называется статистикой соответствия для. ${\ displaystyle P}$ $п$ ${\ Displaystyle P [я \ точки м]}$ $P [i \ dots m]$ ${\ displaystyle D}$ $D$ ${\ Displaystyle \ Theta (м)}$ $\ Theta (м)$ ${\ displaystyle P}$ $п$
Найдите свойства строк:
- Найдите самые длинные общие подстроки в строке и по времени. ${\ displaystyle S_ {i}}$ $S_ {i}$ ${\ displaystyle S_ {j}}$ $S_j$ ${\ displaystyle \ Theta (n_ {i} + n_ {j})}$ $\ Тета (n_i + n_j)$
- Найдите все максимальные пары, максимальные или сверхмаксимальные повторы во времени. ${\ Displaystyle \ Theta (п + г)}$ $\ Тета (п + г)$
- Найдите разложение Лемпеля – Зива по времени. ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$
- Найдите самые длинные повторяющиеся подстроки во времени. ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$
- Найдите наиболее часто встречающиеся подстроки минимальной длины по времени. ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$
- Найдите самые короткие строки из тех, которые не встречаются во времени, если такие строки есть. ${\ displaystyle \ Sigma}$ $\Сигма$ ${\ displaystyle D}$ $D$ ${\ Displaystyle О (п + г)}$ $О (п + г)$ ${\ displaystyle z}$ $z$
- Найдите самые короткие подстроки, встречающиеся только один раз. ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$
- Найдите для каждого из них самые короткие подстроки, которые не встречаются где-либо еще во времени. ${\ displaystyle i}$ $я$ ${\ displaystyle S_ {i}}$ $S_ {i}$ ${\ displaystyle D}$ $D$ ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$

Суффиксное дерево может быть подготовлено для постоянного поиска наименьшего общего предка между узлами во времени. Затем можно также: ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$

Найдите самый длинный общий префикс между суффиксами и in. ${\ displaystyle S_ {i} [п..n_ {i}]}$ $S_i [p..n_i]$ ${\ displaystyle S_ {j} [q..n_ {j}]}$ $S_j [q..n_j]$ ${\ Displaystyle \ Theta (1)}$ $\ Тета (1)$
Найдите образец P длины m с не более чем k несовпадениями по времени, где z - количество совпадений. ${\ displaystyle O (kn + z)}$ $O (kn + z)$
Найдите все максимальные палиндромы за или время, если допускаются промежутки в длине или если допускаются несоответствия. ${\ displaystyle z}$ $z$ ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$ ${\ Displaystyle \ Theta (gn)}$ $\ Theta (gn)$ ${\ displaystyle g}$ $грамм$ ${\ Displaystyle \ Theta (kn)}$ $\ Theta (кн)$ ${\ displaystyle k}$ $k$
Найти все тандемные повторы в и К -mismatch тандемных повторов в. ${\ displaystyle z}$ $z$ ${\ Displaystyle О (п \ журнал п + г)}$ $О (п \ журнал п + г)$ ${\ Displaystyle О (кн \ журнал (п / к) + г)}$ $О (кн \ журнал (п / к) + г)$
Найдите самые длинные общие подстроки по крайней мере строк в течение в времени. ${\ displaystyle k}$ $k$ ${\ displaystyle D}$ $D$ ${\ Displaystyle к = 2, \ точки, К}$ $к = 2, \ точек, К$ ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$
Найдите самую длинную палиндромную подстроку данной строки (используя обобщенное суффиксное дерево строки и его обратное) за линейное время.

Приложения

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

Строка поиска, в O (м) сложности, где т есть длина подстроки (но с начальным O (N) время, необходимое для построения дерева суффиксов для строки)
Поиск самой длинной повторяющейся подстроки
Нахождение самой длинной общей подстроки
Поиск самого длинного палиндрома в строке

Деревья суффиксов часто используются в приложениях биоинформатики для поиска закономерностей в последовательностях ДНК или белков (которые можно рассматривать как длинные строки символов). Способность эффективно искать несоответствия можно считать их самой сильной стороной. Деревья суффиксов также используются при сжатии данных ; их можно использовать для поиска повторяющихся данных и на этапе сортировки преобразования Барроуза – Уиллера. Варианты схем сжатия LZW используют суффиксные деревья ( LZSS ). Суффиксное дерево также используется в кластеризации суффиксного дерева, алгоритме кластеризации данных, используемом в некоторых поисковых системах.

Выполнение

Если каждый узел и ребро могут быть представлены в пространстве, все дерево может быть представлено в пространстве. Общая длина всех строк на всех ребрах дерева равна, но каждое ребро может быть сохранено как позиция и длина подстроки S, что дает общее использование пространства компьютерными словами. Наихудший случай использования пространства суффиксного дерева проявляется в слове Фибоначчи, дающем полные узлы. ${\ Displaystyle \ Theta (1)}$ $\ Тета (1)$ ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$ ${\ Displaystyle О (п ^ {2})}$ $О (п ^ {2})$ ${\ Displaystyle \ Theta (п)}$ $\ Theta (п)$ ${\ displaystyle 2n}$ $2n$

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

Стоимость поиска ребенка на данном персонаже.
Стоимость вставки ребенка.
Стоимость включения всех дочерних узлов узла (деленная на количество дочерних узлов в таблице ниже).

Пусть σ - размер алфавита. Тогда у вас есть следующие расходы:

{\ displaystyle {\ begin {array} {r | lll} amp; {\ text {Lookup}} amp; {\ text {Insertion}} amp; {\ text {Traversal}} \\\ hline {\ text {Списки братьев и сестер / несортировано массивы}} amp; O (\ sigma) amp; \ Theta (1) amp; \ Theta (1) \\ {\ text {Побитовые родственные деревья}} amp; O (\ log \ sigma) amp; \ Theta (1) amp; \ Theta (1) \\ {\ text {Хеш-карты}} amp; \ Theta (1) amp; \ Theta (1) amp; O (\ sigma) \\ {\ text {Сбалансированное дерево поиска}} amp; O (\ log \ sigma) amp; O (\ log \ sigma) amp; O (1) \\ {\ text {Сортированные массивы}} amp; O (\ log \ sigma) amp; O (\ sigma) amp; O (1) \\ {\ text {Хеш-карты + списки родственников}} amp; O (1) amp; O (1) amp; O (1) \ end {array}}}

{\ displaystyle {\ begin {array} {r | lll} amp; {\ text {Lookup}} amp; {\ text {Insertion}} amp; {\ text {Traversal}} \\\ hline {\ text {Списки братьев и сестер / несортировано массивы}} amp; O (\ sigma) amp; \ Theta (1) amp; \ Theta (1) \\ {\ text {Побитовые родственные деревья}} amp; O (\ log \ sigma) amp; \ Theta (1) amp; \ Theta (1) \\ {\ text {Хеш-карты}} amp; \ Theta (1) amp; \ Theta (1) amp; O (\ sigma) \\ {\ text {Сбалансированное дерево поиска}} amp; O (\ log \ sigma) amp; O (\ log \ sigma) amp; O (1) \\ {\ text {Сортированные массивы}} amp; O (\ log \ sigma) amp; O (\ sigma) amp; O (1) \\ {\ text {Хеш-карты + списки родственников}} amp; O (1) amp; O (1) amp; O (1) \ end {array}}}

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

Большой объем информации на каждом ребре и узле делает суффиксное дерево очень дорогим, занимая примерно в 10-20 раз объем памяти исходного текста в хороших реализациях. Массив суффиксов уменьшает это требование к фактору 8 (для массива, включая LCP значения, построенные в пределах 32-битное адресное пространство и 8-битных символов.) Этот фактор зависит от свойств и может достигать 2 с использованием 4-байтовыми широких символов ( необходимо содержать любой символ в некоторых UNIX-подобных системах, см. wchar_t ) в 32-битных системах. Исследователи продолжали находить более мелкие структуры индексации.

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

Были предложены различные параллельные алгоритмы для ускорения построения дерева суффиксов. Недавно был разработан практический параллельный алгоритм построения суффиксного дерева с работой (последовательное время) и промежутком. Алгоритм обеспечивает хорошую параллельную масштабируемость на многоядерных машинах с общей памятью и может индексировать геном человека - примерно 3 ГБ - менее чем за 3 минуты с использованием 40-ядерной машины. ${\ Displaystyle О (п)}$ $На)$ ${\ Displaystyle О (\ журнал ^ {2} п)}$ $О (\ журнал ^ {2} п)$

Внешняя конструкция

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

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

С другой стороны, были проведены практические работы по построению суффиксных деревьев на основе дисков, которые масштабируются до (нескольких) ГБ / час. Самыми современными методами являются TDD, TRELLIS, DiGeST и B ² ST.

TDD и TRELLIS масштабируются до всего генома человека, в результате получается суффиксное дерево на диске размером в десятки гигабайт. Однако эти методы не могут эффективно обрабатывать наборы последовательностей, превышающие 3 ГБ. DiGeST работает значительно лучше и может обрабатывать наборы последовательностей размером порядка 6 ГБ примерно за 6 часов.. Все эти методы позволяют эффективно строить суффиксные деревья для случая, когда дерево не помещается в основной памяти, но входные данные помещаются. Самый последний метод, B ² ST, масштабируется для обработки входных данных, которые не помещаются в основную память. ERA - это недавний метод построения параллельного дерева суффиксов, который стал значительно быстрее. ERA может проиндексировать весь геном человека за 19 минут на 8-ядерном настольном компьютере с 16 ГБ оперативной памяти. В простом кластере Linux с 16 узлами (4 ГБ ОЗУ на узел) ERA может проиндексировать весь геном человека менее чем за 9 минут.

Смотрите также

Заметки

Рекомендации

Ахо, Альфред В. ; Хопкрофт, Джон Э. ; Ульман, Джеффри Д. (1974), Дизайн и анализ компьютерных алгоритмов, чтение / MA: Addison-Wesley, ISBN 0-201-00029-6.
Апостолико, А.; Iliopoulos, C.; Ландау, GM; Schieber, B.; Вишкин, У. (1988), "Параллельное построение суффиксного дерева с приложениями", Algorithmica, 3 (1–4): 347–365, doi : 10.1007 / bf01762122.
Баеза-Йейтс, Рикардо А. ; Гонен, Гастон H. (1996), "Быстрый поиск текста для регулярных выражений или автомат поиска по попыткам", Журнал ACM, 43 (6): 915-936, DOI : 10,1145 / 235809,235810, S2CID 1420298.
Барский, Марина; Стеге, Ульрике; Томо, Алекс; Аптон, Крис (2008), «Новый метод индексации геномов с использованием суффиксных деревьев на диске», CIKM '08: Материалы 17-й конференции ACM по управлению информацией и знаниями, Нью-Йорк, Нью-Йорк, США: ACM, стр. 649 –658.
Барский, Марина; Стеге, Ульрике; Томо, Алекс; Аптон, Крис (2009), «Суффикс-деревья для очень больших геномных последовательностей», CIKM '09: Материалы 18-й конференции ACM по управлению информацией и знаниями, Нью-Йорк, Нью-Йорк, США: ACM.
Фарач, Мартин (1997), «Оптимальное построение суффиксного дерева с большими алфавитами» (PDF), 38-й симпозиум IEEE по основам информатики (FOCS '97), стр. 137–143.
Фарах, Мартин ; Мутукришнан, С. (1996), "Построение рандомизированного суффиксного дерева с оптимальным логарифмическим временем", Международный коллоквиум по языкам автоматов и программированию.
Фарач-Колтон, Мартин ; Феррагина, Паоло; Мутукришнан, С. (2000), "О сортировочной сложности построения суффиксного дерева"., Журнал ACM, 47 (6): 987-1011, DOI : 10,1145 / 355541,355547, S2CID 8164822.
Giegerich, R.; Курц, S. (1997), "От Ukkonen к McCreight и Вайнер: объединяющим Вид Линейно-Time суффикса дерева Строительство" (PDF), Algorithmica, 19 (3): 331-353, DOI : 10.1007 / PL00009177, архивируются из оригинал (PDF) на 2016-03-03, извлекаться 2012-07-13.
Гусфилд, Дэн (1999), Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология, Cambridge University Press, ISBN 0-521-58519-8.
Харихаран, Рамеш (1994), "Оптимальное параллельное построение суффиксного дерева", Симпозиум ACM по теории вычислений.
Илиопулос, Костас; Риттер, Войцех (2004), «О параллельных преобразованиях суффиксных массивов в суффиксные деревья», 15-й Австралийский семинар по комбинаторным алгоритмам.
Мансур, Эссам; Аллам, Амин; Скиадопулос, Спирос; Калнис, Панос (2011), «ERA: Эффективное последовательное и параллельное построение суффиксного дерева для очень длинных строк» (PDF), Proceedings of the VLDB Endowment, 5 (1): 49–60, arXiv : 1109.6884, Bibcode : 2011arXiv1109.6884M, DOI : 10,14778 / 2047485,2047490.
McCreight, Эдвард М. (1976), "A Space-экономический Суффикс конструкция дерева Алгоритм", Журнал ACM, 23 (2): 262-272, CiteSeerX 10.1.1.130.8022, DOI : 10,1145 / 321941,321946.
Фофакди, Бенджарат; Заки, Мохаммед Дж. (2007), «Индексация суффиксного дерева на основе диска в масштабе генома», SIGMOD '07: Материалы Международной конференции ACM SIGMOD по управлению данными, Нью-Йорк, Нью-Йорк, США: ACM, стр. 833– 844.
Сахиналп, Дженк; Вишкин, Узи (1994), "Нарушение симметрии для построения суффиксного дерева", Симпозиум ACM по теории вычислений
Смит, Уильям (2003), Вычислительные шаблоны в строках, Аддисон-Уэсли.
Шун, Джулиан; Blelloch, Guy E. (2014), "Простой параллельный декартово дерево Алгоритм и его применение параллельных суффиксов дерева Строительство", ACM Сделки по параллельным вычислениям, 1 : 1-20, DOI : 10,1145 / 2661653, S2CID 1912378.
Тата, Сандип; Хэнкинс, Ричард А.; Патель, Джигнеш М. (2003), «Практическое построение суффиксного дерева», VLDB '03: Материалы 30-й Международной конференции по очень большим базам данных, Морган Кауфманн, стр. 36–47.
Укконен, Е. (1995), "О-линии построение деревьев суффиксов" (PDF), Algorithmica, 14 (3): 249-260, DOI : 10.1007 / BF01206331.
Вайнер, П. (1973), «Линейные алгоритмы сопоставления с образцом» (PDF), 14-й ежегодный симпозиум IEEE по теории коммутации и автоматов, стр. 1–11, doi : 10.1109 / SWAT.1973.13.
Замир, Орен; Etzioni, Oren (1998), "Кластеризация веб-документов: демонстрация осуществимости", SIGIR '98: Материалы 21-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска, Нью-Йорк, Нью-Йорк, США: ACM, стр. 46 –54.

Внешние ссылки

Суффикс Деревья на Сартедж Сани
Словарь алгоритмов и структур данных NIST: суффиксное дерево
Универсальное сжатие данных на основе преобразования Барроуза-Уиллера: теория и практика, применение суффиксных деревьев в BWT
Теория и практика лаконичных структур данных, реализация сжатого суффиксного дерева на C ++
Реализация суффиксного дерева Укконена в C Часть 1 Часть 2 Часть 3 Часть 4 Часть 5 Часть 6
Онлайн-демонстрация: Визуализация суффиксного дерева Укконена