Дерево суффиксов

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

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

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

Построение такого дерева для строки занимает время и пространство линейно по длине . После построения можно быстро выполнить несколько операций, например, найти подстроку в , найти подстроку, если допускается определенное количество ошибок, и найти совпадения для шаблона регулярного выражения . Суффиксные деревья также предоставили одно из первых линейно-временных решений для самой длинной распространенной проблемы подстроки . ^[2] Эти ускорения обходятся дорого: хранение суффиксного дерева строки обычно требует значительно больше места, чем хранение самой строки. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

История

Эта концепция была впервые введена Вайнером (1973). Вместо суффикса Вайнером ^{[3] был сохранен} идентификатор префикса для каждой позиции, то есть самая короткая строка, начинающаяся с и встречающаяся только один раз в . Его алгоритм D берет несжатый ^[4] trie для и расширяет его до trie для . Таким образом, начиная с тривиального trie для , trie для может быть построен путем последовательных вызовов алгоритма D; однако общее время выполнения равно . Алгоритм Вайнера B поддерживает несколько вспомогательных структур данных для достижения общего времени выполнения, линейного по размеру построенного trie. Последние по-прежнему могут быть узлами, например, для Алгоритм Вайнера C , наконец, использует сжатые попытки для достижения линейного общего размера хранилища и времени выполнения. ^[5] Дональд Кнут впоследствии охарактеризовал последний как «Алгоритм года 1973» по словам его ученика Воана Пратта . ^{[ оригинальное исследование? ] [6]} Учебник Ахо, Хопкрофта и Ульмана (1974, раздел 9.5) воспроизвел результаты Вайнера в упрощенной и более элегантной форме, введя термин « дерево позиций» . ${\displaystyle S[i..n]}$ ${\displaystyle i}$ ${\displaystyle S}$ ${\displaystyle S[k+1..n]}$ ${\displaystyle S[k..n]}$ ${\displaystyle S[n..n]}$ ${\displaystyle S[1..n]}$ ${\displaystyle n-1}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{2})}$ ${\displaystyle S=a^{n}b^{n}a^{n}b^{n}\$.}$

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

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

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

Определение

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

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

Если суффикс также является префиксом другого суффикса, то такого дерева для строки не существует. Например, в строке abcbc суффикс bc также является префиксом суффикса bcbc . В таком случае путь, прописывающий bc , не будет заканчиваться листом, что нарушает пятое правило. Чтобы исправить эту проблему, дополняется терминальным символом, которого нет в строке (обычно обозначается ). Это гарантирует, что ни один суффикс не является префиксом другого, и что будут листовые узлы, по одному для каждого из суффиксов . ^[8] Поскольку все внутренние некорневые узлы являются ветвящимися, таких узлов может быть не более, а всего узлов ( листья, внутренние некорневые узлы, 1 корень). ${\displaystyle S}$ ${\displaystyle S}$$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle n-1}$ ${\displaystyle n+(n-1)+1=2n}$ ${\displaystyle n}$ ${\displaystyle n-1}$

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

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

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

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

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

• Поиск строк:
  • Проверьте, является ли строка длины подстрокой во времени. ^[10] ${\displaystyle P}$ ${\displaystyle m}$ ${\displaystyle O(m)}$
  • Найдите первое вхождение шаблонов общей длины в виде подстрок во времени. ${\displaystyle P_{1},\dots ,P_{q}}$ ${\displaystyle m}$ ${\displaystyle O(m)}$
  • Найти все вхождения шаблонов общей длины как подстрок во времени. ^[11] ${\displaystyle z}$ ${\displaystyle P_{1},\dots ,P_{q}}$ ${\displaystyle m}$ ${\displaystyle O(m+z)}$
  • Поиск регулярного выражения P по времени, ожидаемо сублинейного по . ^[12] ${\displaystyle n}$
  • Найдите для каждого суффикса шаблона длину самого длинного совпадения между префиксом и подстрокой за время . ^[13] Это называется статистикой совпадений для . ${\displaystyle P}$ ${\displaystyle P[i\dots m]}$ ${\displaystyle D}$ ${\displaystyle \Theta (m)}$ ${\displaystyle P}$
• Найдите свойства строк:
  • Найдите самые длинные общие подстроки строки и за время. ^[14] ${\displaystyle S_{i}}$ ${\displaystyle S_{j}}$ ${\displaystyle \Theta (n_{i}+n_{j})}$
  • Найти все максимальные пары , максимальные повторы или сверхмаксимальные повторы во времени. ^[15] ${\displaystyle \Theta (n+z)}$
  • Найдите разложение Лемпеля–Зива по времени. ^[16] ${\displaystyle \Theta (n)}$
  • Найдите самые длинные повторяющиеся подстроки за время. ${\displaystyle \Theta (n)}$
  • Найдите наиболее часто встречающиеся подстроки минимальной длины во времени. ${\displaystyle \Theta (n)}$
  • Найдите самые короткие строки из , которые не встречаются за , во времени, если такие строки есть . ${\displaystyle \Sigma }$ ${\displaystyle D}$ ${\displaystyle O(n+z)}$ ${\displaystyle z}$
  • Найдите самые короткие подстроки, встречающиеся только один раз . ${\displaystyle \Theta (n)}$
  • Найдите для каждого кратчайшие подстроки, не встречающиеся больше нигде во времени . ${\displaystyle i}$ ${\displaystyle S_{i}}$ ${\displaystyle D}$ ${\displaystyle \Theta (n)}$

Дерево суффиксов может быть подготовлено для постоянного поиска наименьшего общего предка между узлами во времени. ^[17] Затем можно также: ${\displaystyle \Theta (n)}$

• Найдите самый длинный общий префикс между суффиксами и в . ^[18] ${\displaystyle S_{i}[p..n_{i}]}$ ${\displaystyle S_{j}[q..n_{j}]}$ ${\displaystyle \Theta (1)}$
• Поиск шаблона P длиной m с не более чем k несовпадениями во времени, где z — количество совпадений. ^[19] ${\displaystyle O(kn+z)}$
• Найдите все максимальные палиндромы за , ^[20] или время, если допускаются пробелы длины или если допускаются несовпадения. ^[21] ${\displaystyle z}$ ${\displaystyle \Theta (n)}$ ${\displaystyle \Theta (gn)}$ ${\displaystyle g}$ ${\displaystyle \Theta (kn)}$ ${\displaystyle k}$
• Найти все тандемные повторы в и k -несовпадающие тандемные повторы в . ^[22] ${\displaystyle z}$ ${\displaystyle O(n\log n+z)}$ ${\displaystyle O(kn\log(n/k)+z)}$
• Найдите самые длинные общие подстроки для по крайней мере строк за время . ^[23] ${\displaystyle k}$ ${\displaystyle D}$ ${\displaystyle k=2,\dots ,K}$ ${\displaystyle \Theta (n)}$
• Найти самую длинную палиндромную подстроку заданной строки (используя обобщенное суффиксное дерево строки и его обратную версию) за линейное время. ^[24]

Приложения

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

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

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

Выполнение

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

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

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

Пусть σ будет размером алфавита. Тогда у вас будут следующие затраты: ^{[ необходима цитата ]}

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

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

Параллельная конструкция

Были предложены различные параллельные алгоритмы для ускорения построения суффиксного дерева. ^{[27] [28] [29] [30] [31]} Недавно был разработан практический параллельный алгоритм для построения суффиксного дерева с работой (последовательное время) и диапазоном . Алгоритм достигает хорошей параллельной масштабируемости на многоядерных машинах с общей памятью и может индексировать человеческий геном — примерно 3 ГБ — менее чем за 3 минуты, используя 40-ядерную машину. ^[32] ${\displaystyle O(n)}$ ${\displaystyle O(\log ^{2}n)}$

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

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

Существуют теоретические результаты для построения деревьев суффиксов во внешней памяти. Алгоритм Farach-Colton, Ferragina & Muthukrishnan (2000) теоретически оптимален, со сложностью ввода-вывода, равной сложности сортировки. Однако общая сложность этого алгоритма до сих пор не позволяла реализовать его на практике. ^[33]

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

TDD и TRELLIS масштабируются до всего генома человека, что приводит к созданию дерева суффиксов на диске размером в десятки гигабайт. ^{[34] [35]} Однако эти методы не могут эффективно обрабатывать коллекции последовательностей, превышающие 3 ГБ. ^[36] DiGeST работает значительно лучше и способен обрабатывать коллекции последовательностей размером порядка 6 ГБ примерно за 6 часов. ^[36]

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

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

• Суффиксный автомат

Примечания

1. Дональд Э. Кнут; Джеймс Х. Моррис; Воган Р. Пратт (июнь 1977 г.). «Быстрое сопоставление шаблонов в строках» (PDF) . Журнал SIAM по вычислениям . 6 (2): 323–350. doi :10.1137/0206024.Здесь: стр.339 внизу.
2. Кнут предположил, что эта задача не может быть решена за линейное время. ^[1] В 1973 году это было опровергнуто алгоритмом суффиксного дерева Вайнера (1973).
3. Этот термин используется здесь для того, чтобы отличить предшествующие структуры данных Вайнера от настоящих суффиксных деревьев, определенных выше и не рассматривавшихся до МакКрейта (1976).
4. т.е. каждая ветвь помечена одним символом
5. Смотрите Файл:WeinerB aaaabbbbaaaabbbb.gif и Файл:WeinerC aaaabbbbaaaabbbb.gif для несжатого примера дерева и его сжатого соответствия.
6. Гигерих и Курц (1997).
7. Гасфилд (1999) , стр.90.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
8. Гасфилд (1999) , стр.90-91.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
9. Фарах (1997).
10. Гасфилд (1999) , стр.92.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
11. Гасфилд (1999) , стр.123.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
12. Баеза-Йейтс и Гоннет (1996).
13. Гасфилд (1999) , стр.132.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
14. Гасфилд (1999) , стр.125.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
15. Гасфилд (1999) , стр.144.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
16. Гасфилд (1999) , стр.166.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
17. Гасфилд (1999) , Глава 8.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
18. Гасфилд (1999) , стр.196.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
19. Гасфилд (1999) , стр.200.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
20. Гасфилд (1999) , стр.198.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
21. Гасфилд (1999) , стр.201.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
22. Гасфилд (1999) , стр.204.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
23. Гасфилд (1999) , стр.205.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
24. Гасфилд (1999) , стр.197–199.ошибка harvtxt: нет цели: CITEREFGusfield1999 ( помощь )
25. Allison, L. "Suffix Trees". Архивировано из оригинала 2008-10-13 . Получено 2008-10-14 .
26. Впервые представлено Замиром и Эциони (1998).
27. Апостолико и др. (1988).
28. Харихаран (1994).
29. Сахиналп и Вишкин (1994).
30. Фарах и Мутукришнан (1996).
31. Илиопулос и Риттер (2004).
32. Шун и Блеллок (2014).
33. Смит (2003).
34. Tata, Hankins & Patel (2003).
35. Пхупакди и Заки (2007).
36. Барски и др. (2008).
37. Барски и др. (2009).
38. Мансур и др. (2011).

Ссылки

• Ахо, Альфред В.; Хопкрофт , Джон Э .; Ульман, Джеффри Д. (1974), Проектирование и анализ компьютерных алгоритмов , Reading/MA: Addison-Wesley, ISBN 0-201-00029-6.
• Апостолико, А.; Илиопулос, К.; Ландау, Г. М.; Шибер, Б.; Вишкин, У. (1988), «Параллельное построение дерева суффиксов с приложениями», Algorithmica , 3 (1–4): 347–365, doi :10.1007/bf01762122, S2CID  5024136.
• Баеза-Йетс, Рикардо А.; Гонне , Гастон Х. (1996), «Быстрый поиск текста с помощью регулярных выражений или автоматический поиск по попыткам», Журнал ACM , 43 (6): 915–936, doi : 10.1145/235809.235810 , S2CID  1420298.
• Барски, Марина; Стеге, Ульрике; Томо, Алекс; Аптон, Крис (2008), «Новый метод индексации геномов с использованием суффиксных деревьев на диске», CIKM '08: Труды 17-й конференции ACM по управлению информацией и знаниями (PDF) , Нью-Йорк, США: ACM, стр. 649–658.
• Барски, Марина; Стеге, Ульрике; Томо, Алекс; Аптон, Крис (2009), «Суффиксные деревья для очень больших геномных последовательностей», CIKM '09: Труды 18-й конференции ACM по управлению информацией и знаниями (PDF) , Нью-Йорк, США: ACM.
• Фарах, Мартин (1997), «Оптимальное построение дерева суффиксов с большими алфавитами» (PDF) , 38-й симпозиум IEEE по основам компьютерной науки (FOCS '97) , стр. 137–143.
• Фарах, Мартин ; Мутукришнан, С. (1996), «Оптимальное логарифмическое время рандомизированного построения суффиксного дерева», Международный коллоквиум по языкам автоматов и программированию (PDF).
• Фарах-Колтон, Мартин ; Феррагина, Паоло; Мутукришнан, С. (2000), «О сложности сортировки построения суффиксного дерева», Журнал ACM , 47 (6): 987–1011, doi : 10.1145/355541.355547 , S2CID  8164822.
• Giegerich, R.; Kurtz, S. (1997), "От Укконена до МакКрейта и Вайнера: унифицированный взгляд на построение линейного дерева суффиксов" (PDF) , Algorithmica , 19 (3): 331–353, doi :10.1007/PL00009177, S2CID  18039097, архивировано из оригинала (PDF) 2016-03-03 , извлечено 2012-07-13.
• Гасфилд, Дэн (1997), Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология , Cambridge University Press, ISBN 0-521-58519-8.
• Харихаран, Рамеш (1994), «Оптимальное построение параллельного суффиксного дерева», Симпозиум ACM по теории вычислений (PDF).
• Илиопулос, Костас; Риттер, Войцех (2004), «О параллельных преобразованиях массивов суффиксов в деревья суффиксов», 15-й Австралазийский семинар по комбинаторным алгоритмам , CiteSeerX  10.1.1.62.6715.
• Мансур, Эссам; Аллам, Амин; Скиадопулос, Спирос; Калнис, Панос (2011), «ERA: эффективное последовательное и параллельное построение дерева суффиксов для очень длинных строк» ​​(PDF) , Труды VLDB Endowment , 5 (1): 49–60, arXiv : 1109.6884 , Bibcode : 2011arXiv1109.6884M, doi : 10.14778/2047485.2047490, S2CID  7582116.
• МакКрейт, Эдвард М. (1976), «Алгоритм построения дерева суффиксов с экономным использованием пространства», Журнал ACM , 23 (2): 262–272, CiteSeerX  10.1.1.130.8022 , doi :10.1145/321941.321946, S2CID  9250303.
• Phoophakdee, Benjarath; Zaki, Mohammed J. (2007), «Индексирование дерева суффиксов на основе диска в масштабе генома», SIGMOD '07: Труды Международной конференции ACM SIGMOD по управлению данными , Нью-Йорк, США: ACM, стр. 833–844, CiteSeerX  10.1.1.81.6031.
• Сахиналп, Дженк; Вишкин, Узи (1994), «Нарушение симметрии для построения суффиксного дерева», Симпозиум ACM по теории вычислений , стр. 300–309, doi : 10.1145/195058.195164 , ISBN 0-89791-663-8, S2CID  5985171
• Смит, Уильям (2003), Вычисление шаблонов в строках , Эддисон-Уэсли.
• Шун, Джулиан; Блеллох, Гай Э. (2014), «Простой параллельный алгоритм декартового дерева и его применение для построения параллельного суффиксного дерева», ACM Transactions on Parallel Computing , 1 : 1–20, doi : 10.1145/2661653, S2CID  1912378.
• Тата, Сандип; Хэнкинс, Ричард А.; Патель, Джигнеш М. (2003), «Практическое построение суффиксного дерева», VLDB '03: Труды 30-й Международной конференции по сверхбольшим базам данных (PDF) , Морган Кауфманн, стр. 36–47.
• Укконен, Э. (1995), «Онлайн-конструирование суффиксных деревьев» (PDF) , Algorithmica , 14 (3): 249–260, doi :10.1007/BF01206331, S2CID  6027556.
• Weiner, P. (1973), "Linear pattern matching algorithms" (PDF) , 14th Annual IEEE Symposium on Switching and Automata Theory , стр. 1–11, doi :10.1109/SWAT.1973.13, заархивировано из оригинала (PDF) 2016-03-03 , извлечено 2015-04-16.
• Замир, Орен; Этциони, Орен (1998), «Кластеризация веб-документов: демонстрация возможности», SIGIR '98: Труды 21-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска , Нью-Йорк, США: ACM, стр. 46–54, CiteSeerX  10.1.1.36.4719.

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

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