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

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

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

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

История

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

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

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

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

Определение

Суффиксное дерево для строки $S$ длины $n$ определяется как дерево такое, что:

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

Реализация

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

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

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

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

	Искать	Вставка	Обход
Родственные списки/несортированные массивы	О ( п )	Я(1)	Я(1)
Побитовые родственные деревья	О ( logσ )	Я(1)	Я(1)
Хэш-карты	Я(1)	Я(1)	О ( п )
Сбалансированное дерево поиска	О ( logσ )	О ( logσ )	О (1)
Сортированные массивы	О ( logσ )	О ( п )	О (1)
Хэш-карты + списки братьев и сестер	О (1)	О (1)	О (1)

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

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

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

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

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

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

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

С другой стороны, были проведены практические работы по построениюдисковые суффиксные деревьякоторые масштабируются до (несколько) ГБ/часов.Современные методы: TDD, ТРЕЛЛИС, ДиГеСТ, иБ ² СТ.

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

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

См. также

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

Ссылки

• Ахо, Альфред В .; Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1974), Проектирование и анализ компьютерных алгоритмов , Ридинг / Массачусетс: Аддисон-Уэсли, ISBN  0-201-00029-6 .
• Апостолико, А.; Илиопулос, К.; Ландау, генеральный директор; Шибер, Б.; Вишкин, Ю. (1988), «Параллельное построение суффиксного дерева с приложениями» , Algorithmica , 3 (1–4): 347–365, doi : 10.1007/bf01762122 , S2CID   5024136 .
• Баеза-Йейтс, Рикардо А .; Гонне, Гастон Х. (1996), «Быстрый поиск текста по регулярным выражениям или автоматический поиск при попытках», Journal of the 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 .
• Гигерих, Р.; Курц, С. (1997), «От Укконена до МакКрайта и Вайнера: унифицированный взгляд на построение суффиксного дерева в линейном времени» (PDF) , Algorithmica , 19 (3): 331–353, doi : 10.1007/PL00009177 , S2CID   18039097 , заархивировано из оригинала (PDF) 3 марта 2016 г. , получено 13 июля 2012 г.
• Гасфилд, Дэн (1997), Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология , Cambridge University Press, ISBN  0-521-58519-8 .
• Харихаран, Рамеш (1994), «Построение оптимального параллельного суффиксного дерева», Симпозиум ACM по теории вычислений (PDF) .
• Илиопулос, Костас; Риттер, Войцех (2004), «О параллельных преобразованиях суффиксных массивов в суффиксные деревья», 15-й австралийский семинар по комбинаторным алгоритмам , CiteSeerX   10.1.1.62.6715 .
• Мансур, Эссам; Аллам, Амин; Скиадопулос, Спирос; Калнис, Панос (2011), «ERA: Эффективное построение последовательного и параллельного суффиксного дерева для очень длинных строк» ​​(PDF) , Proceedings of 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 .
• Пхупакди, Бенджарат; Заки, Мохаммед Дж. (2007), «Индексация суффиксного дерева на основе диска в масштабе генома», SIGMOD '07: Материалы Международной конференции ACM SIGMOD по управлению данными , Нью-Йорк, Нью-Йорк, США: ACM, стр. 833– 844, CiteSeerX   10.1.1.81.6031 .
• Сахинальп, Дженк; Вишкин, Узи (1994), «Нарушение симметрии для построения суффиксного дерева», Симпозиум ACM по теории вычислений , doi : 10.1145/195058.195164 , S2CID   5985171
• Смит, Уильям (2003), Вычисление шаблонов в строках , Аддисон-Уэсли .
• Шун, Джулиан; Блеллок, Гай Э. (2014), «Простой алгоритм параллельного декартова дерева и его применение к построению параллельного суффиксного дерева», Транзакции ACM на параллельных вычислениях , 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 .
• Вайнер, П. (1973), «Алгоритмы сопоставления с линейным образцом» (PDF) , 14-й ежегодный симпозиум IEEE по теории коммутации и автоматов , стр. 1–11, doi : 10.1109/SWAT.1973.13 , заархивировано из оригинала (PDF) на 3 марта 2016 г. , получено 16 апреля 2015 г.
• Замир, Орен; Эциони, Орен (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
• Онлайн-демо: визуализация суффиксного дерева Укконена