Chtochto

  • 17 дек. 2012 г.
  • 2961 Слова
Построение суффиксного дерева за линейное время Лекция № 1 курса Алгоритмы для Интернета
Юрий Лифшиц∗ 28 сентября 2006 г.

Содержание
1. Введение в суффиксные деревья 1.1. Определение суффиксного дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Два применения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Наивныйкубический алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Квадратичный алгоритм 3. Линейный алгоритм Итоги Источники 1 1 2 4 6 9 10 10

1.
1.1.

Введение в суффиксные деревья
Определение суффиксного дерева

Будем называть текстом T строку из n символов t1 . . . tn , а каждое окончание текста ti . . . tn его суффиксом. Суффиксное дерево (ST) это способпредставления текста. Неформально говоря, чтобы построить ST для текста T = t1 . . . tn , нужно приписать специальный символ $ в конец текста, взять все n + 1 суффиксов, подвесить их за начала и склеить все ветки, идущие по одинаковым буквам. В каждом листе записывается номер суффикса, заканчивающегося в этом листе. Номером суффикса является индекс его начала в тексте T . Заметим, что ни одинсуффикс в ST не может полностью лежать в другом суффиксе, поскольку они заканчиваются специальным символом $. Таким образом, листьев в ST всегда будет n + 1 для строки t1 . . . tn , то есть столько же, сколько суффиксов. Но общее число вершин в суффиксном дереве квадратично. Разберемся теперь, как хранить суффиксное дерево, используя линейную память. Для этого оставим в ST только вершины разветвления, тоесть имеющие не менее двух детей. Вместо строки для ребра будем хранить ссылку на сегмент текста T [i..j]. В таком виде суффиксное дерево называется сжатым.
∗ Законспектировал

Иван Лагунов.

1

Рис. 1. Пример сжатого суффиксного дерева для строки xabxa$ Заметим, что, так как теперь каждая из внутренних вершин является вершиной разветвления, то она добавляет к своему поддереву как минимум одинлист. Листьев же в ST всего n + 1 для строки t1 . . . tn , поэтому внутренних вершин может быть в диапазоне 1 . . . n.

Рис. 2. Крайние случаи для числа внутренних вершин в сжатом суффиксном дереве: одна внутренняя вершина для строки abc$, три для строки aaa$ Таким образом, всего вершин и ребер в сжатом суффиксном дереве будет линейное число, значит оно будет занимать линейную память.

1.2.

Дваприменения

Поиск подстрок Дан текст T = t1 . . . tn . Нужно так его подготовить за время O(n), чтобы поиск любого шаблона P занимал время O(|P |). Шаблоном называем строку, которую хотим найти в тексте T . Приведем решение с помощью суффиксного дерева. Сначала построим суффиксное дерево для текста T . Будем читать шаблон вдоль дерева от корня. Если в какой-то момент не сможем прочитать следующуюбукву шаблона, значит шаблон ни разу не встречался в тексте T . Допустим, что он встречался, тогда, прочитав его, приходим в вершину v или останавливаемся на ребре. В случае остановки на ребре пройдем дальше от корня ST до первой вершины v. Далее прочитаем числа, записанные в листьях-потомках вершины v. Эти числа номера суффиксов, начинающихся с шаблона P , а значит индексы вхождений P в текст T. Сложность этого алгоритма O(|P | + |Output|), где |Output| число листов в поддереве вершины v. Заметим, что первое вхождение шаблона можно найти за время O(|P |), для этого нужно предварительно для каждой вершины разветвления запомнить номер первого листа в ее поддереве. Это можно

2

Рис. 3. Пример для задачи поиска шаблона P в тексте T сделать на этапе подготовки, например, обходом вглубину. Это очень важно, поскольку часто возникают задачи с очень большим текстом и короткими шаблонами для поиска. В качестве примера можно привести трехтомный роман Л. Н. Толстого Война и мир . Очевидно в данном случае, что невыгодно для каждого шаблона искать его вхождения в текст за время порядка длины текста. Поэтому построим суффиксное дерево для всего романа, найдем в нем для...
tracking img