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

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

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

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

Определение [ править ]

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

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

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

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

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

История [ править ]

Эта концепция была впервые введена Вайнером (1973) . Вместо того , чтобы суффикс S [ я .. п ], Веинер хранится в его синтаксическом дереве ^[2] префикс идентификатор для каждой позиции, то есть, самую короткая строка , начиная с I и происходящей только один раз в S . Его алгоритм D берет несжатое ^[3] дерево для 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, наконец, использует сжатые попытки для достижения линейного общего размера хранилища и времени выполнения. ^[4]Дональд Кнут впоследствии охарактеризовал последний как «алгоритм 1973 года». ^{[ необходимая цитата ]} В учебнике Aho, Hopcroft & Ullman (1974 , Sect.9.5) результаты Вайнера воспроизводятся в упрощенной и более элегантной форме, вводя термин « дерево позиций» .

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

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

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

Функциональность [ править ]

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

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

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

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

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

Приложения [ править ]

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

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

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

Реализация [ править ]

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

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

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

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

${\displaystyle {\begin{array}{r|lll}&{\text{Lookup}}&{\text{Insertion}}&{\text{Traversal}}\\\hline {\text{Sibling lists / unsorted arrays}}&O(\sigma )&\Theta (1)&\Theta (1)\\{\text{Bitwise sibling trees}}&O(\log \sigma )&\Theta (1)&\Theta (1)\\{\text{Hash maps}}&\Theta (1)&\Theta (1)&O(\sigma )\\{\text{Balanced search tree}}&O(\log \sigma )&O(\log \sigma )&O(1)\\{\text{Sorted arrays}}&O(\log \sigma )&O(\sigma )&O(1)\\{\text{Hash maps + sibling lists}}&O(1)&O(1)&O(1)\end{array}}}$

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

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

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

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

Внешнее строительство [ править ]

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

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

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

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

См. Также [ править ]

Викискладе есть медиафайлы по теме суффиксного дерева .

• Массив суффиксов
• Суффикс-автомат
• Обобщенное суффиксное дерево
• Trie

Примечания [ править ]

Ссылки [ править ]

• Ахо, Альфред В .; Хопкрофт, Джон Э .; Ульман, Джеффри Д. (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.
• Барский, Марина; Стеге, Ульрике; Томо, Алекс; Аптон, Крис (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.
• 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.
• Тата, Сандип; Хэнкинс, Ричард А .; Патель, Джигнеш М. (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
• Онлайн-демонстрация: Визуализация суффиксного дерева Укконена