Дерево суффиксов
-
Определение и структура дерева суффиксов
- Дерево суффиксов содержит все суффиксы строки в качестве ключей и позиции в строке в качестве значений.
- Построение дерева занимает линейное время и пространство по длине строки.
- Дерево позволяет быстро выполнять операции с подстроками и регулярными выражениями.
-
История и развитие
- Концепция дерева суффиксов предложена Вайнером в 1973 году.
- Вайнер использовал префиксные идентификаторы вместо суффиксов.
- Маккрайт и Укконен упростили конструкцию, используя суффиксные ссылки.
- Фарах предложил алгоритм, оптимальный для всех алфавитов.
-
Функциональность и алгоритмы
- Дерево суффиксов позволяет проверять подстроки, находить шаблоны и регулярные выражения.
- Алгоритмы включают поиск подстрок, шаблонов, регулярных выражений и статистических данных.
- Дерево также используется для поиска наибольшего общего предка и других структур данных.
-
Обобщенное суффиксное дерево
- Обобщенное суффиксное дерево представляет все суффиксы набора строк.
- Каждая строка должна заканчиваться другим символом завершения.
-
Затраты и ограничения
- Построение дерева требует линейного времени для алфавитов постоянного размера.
- Для больших алфавитов основное время уходит на предварительную сортировку.
- Дерево требует больше места для хранения, чем сама строка.
-
Применение деревьев суффиксов
- Деревья суффиксов используются для решения задач редактирования текста, поиска свободного текста, вычислительной биологии и других прикладных областях.
- Основные приложения включают поиск по строке, поиск самой длинной повторяющейся подстроки, поиск самой длинной общей подстроки и поиск самого длинного палиндрома.
- Деревья суффиксов также используются в биоинформатике для поиска закономерностей в ДНК и белковых последовательностях.
- Они также применяются в сжатии данных и кластеризации данных.
-
Реализация деревьев суффиксов
- Деревья суффиксов могут быть представлены в Θ(n) пространстве, если каждый узел и ребро могут быть представлены в Θ(1) пространстве.
- Общая длина всех строк на всех ребрах дерева равна O(n^2), но каждое ребро может быть сохранено как положение и длина подстроки S, что дает общее использование пространства Θ(n) компьютерные слова.
- Наихудшее использование пробелов в суффиксном дереве наблюдается при использовании слова Фибоначчи, дающего полный 2n узлов.
- Важным выбором при создании реализации дерева суффиксов являются родительско-дочерние отношения между узлами.
- Наиболее распространенным является использование связанных списков, называемых родственными списками.
- Другие реализации используют хэш-карты, отсортированные или несортированные массивы или сбалансированные деревья поиска.
-
Параллельное построение деревьев суффиксов
- Были предложены различные параллельные алгоритмы для ускорения построения дерева суффиксов.
- Недавно был разработан практический параллельный алгоритм построения дерева суффиксов с O(n) работой (последовательное время) и O(log^2 n) временем выполнения.
- Алгоритм обеспечивает хорошую параллельную масштабируемость на многоядерных компьютерах и может индексировать геном человека объемом около 3 ГБ менее чем за 3 минуты на 40-ядерном компьютере.
-
Внешняя конструкция деревьев суффиксов
- Несмотря на линейность, использование памяти деревом суффиксов значительно выше фактического размера коллекции последовательностей.
- Для большого текста могут потребоваться подходы к использованию внешней памяти.
- Получены теоретические результаты по построению суффиксных деревьев во внешних память.
- Алгоритм Фарача-Колтона, Феррагины и Мутукришнана (2000) теоретически является оптимальным, но его общая сложность до сих пор препятствовала его практической реализации.
- Практические работы по созданию деревьев суффиксов на основе дисков включают TDD, TRELLIS, DiGeST и B2ST.
- TDD и TRELLIS масштабируются до всего генома человека, но не могут эффективно обрабатывать коллекции последовательностей объемом более 3 ГБ.
- DiGeST работает значительно лучше и способен обрабатывать наборы последовательностей объемом порядка 6 ГБ примерно за 6 часов.
- B2ST масштабируется для обработки входных данных, которые не помещаются в основную память.
- ERA — это недавний метод построения параллельного дерева суффиксов, который значительно быстрее и может проиндексировать весь геном человека за 19 минут на 8-ядерном настольном компьютере с 16 ГБ оперативной памяти.