Суффиксное дерево, Алгоритм Укконена.

Будем называть текстом T строку из n символов t1... tn, а каждое окончание текста ti

... tn — его суффиксом.

Суффиксное дерево (ST) — это способ представления текста. Неформально говоря, чтобы построить

ST для текста T = t1... tn, нужно приписать специальный символ $ в конец текста, взять все n + 1

суффиксов, подвесить их за начала и склеить все ветки, идущие по одинаковым буквам. В каждом листе записывается номер суффикса, заканчивающегося в этом листе. Номером суффикса является индекс его начала в тексте T. По сути суффиксное дерево – бор для суффиксов

Заметим, что ни один суффикс в ST не может полностью лежать в другом суффиксе, поскольку они

заканчиваются специальным символом $. Таким образом, листьев в ST всегда будет n + 1 для строки

t1... tn, то есть столько же, сколько суффиксов. Но общее число вершин в суффиксном дереве квадратично. Разберемся теперь, как хранить суффиксное дерево, используя линейную память. Для этого оставим в ST только вершины разветвления, то есть имеющие не менее двух детей. Вместо строки для ребра будем хранить ссылку на сегмент текста T[i..j]. В таком виде суффиксное дерево называется сжатым.

 

Заметим, что, так как теперь каждая из внутренних вершин является вершиной разветвления, то она

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

Таким образом, всего вершин и ребер в сжатом суффиксном дереве будет линейное число, значит онобудет занимать линейную память

Наивный кубический алгоритм

On-line подход

Этот подход основан на том, что данные на вход алгоритму подаются частями, будь то текст или

какие-то запросы. Алгоритм, использующий on-line подход, читает последовательно поступающие данные

и получает готовое решение на каждом шаге.

Рассмотрим теперь on-line подход для задачи построения суффиксного дерева. Для каждого суффикса

его дополнение до исходного текста T = t1... tn будем называть префиксом, то есть префикс — любое начало текста t1... ti. Будем строить ST не только для всего текста, но последовательно для всех егопрефиксов:

0. Строим суффиксное дерево для t1.

1. Расширяем его до дерева для t1t2.

...

n − 1. Расширяем дерево для t1... tn−1 до дерева для t1... tn.

n. Расширяем дерево для t1... tn до дерева для t1... tn$.

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

 

 

 

Вернемся к примеру с «Войной и миром». Представим, что нам не будет дан сразу весь роман, а будут

даваться по очереди первый, второй и третий тома. Тогда можно построить суффиксное дерево сначала

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

Неявные суффиксные деревья

Неявное суффиксное дерево (IST) — это суффиксное дерево для текста без $ на конце. Некоторые

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

На рисунке 6 видно, что в явном суффиксном дереве добавилось несколько веток. Это объясняется тем,

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

суффикса происходит либо ответвление с возникновением новой ветки, либо продление символом $.

Фаза = последовательность продлений

Рассмотрим фазу i. В ней мы перестраиваем IST для t1... ti в IST для t1... titi+1. Для каждого j

от 1 до i находим в суффиксном дереве конец суффикса tj... ti

. Далее продляем его буквой ti+1, если

необходимо.

Например, рассмотрим фазу на рисунке 7. Надо найти концы суффиксов строки axabx, для этого про-

сто по очереди будем читать их от корня суффиксного дерева. Читаем первый суффикс axabx, приходим

в лист 1, продляем его, дальше читаем суффикс xabx, приходим в лист 2, продляем, и так далее для всех

суффиксов. Но ситуации могут отличаться, как, например, для суффикса x, когда, прочитав его, остаемся

на ребре. В этом случае создаем новую ветку и лист 5.

Всего может быть три типа продлений. Рассмотрим возможные варианты.

1. Продление листа.

Эта ситуация возникает, когда, прочитав суффикс tj... ti

, мы пришли в лист суффиксного дерева.

Тогда «удлиняем» ребро, ведущее в лист, добавляя к строке, соответствующей ребру, новую букву

ti+1.

2. Ответвление буквы.

Прочитав суффикс tj... ti

, мы могли остановиться не в листе, а во внутренней вершине или даже

на каком-то ребре.

(a) В случае, когда остановились во внутренней вершине v и из нее нет исходящего ребра по букве

ti+1, добавляем новое ребро из v в новый лист и записывает на ребре букву ti+1.

(b) Но мы могли остановиться на ребре, потому что ребру соответствует сегмент текста T[k..m] =

= tk... tm, а не одна буква. Этот случай изображен на рисунке 9.

Допустим, мы прочитали на ребре только часть текста tk... ts, которая совпадает с подсуффик-

сом нашего суффикса tj... ti

, где ts = ti. Тогда если ts+1 =6 ti+1, разобьем новой внутренней

вершиной v это ребро на два, соответствующие строкам T[k..s] и T[s + 1..m]. Затем создадим

новое ребро с буквой ti+1 из вершины v в новый лист, как в случае 2(a).

 

3. Пустое правило.

Если, прочитав суффикс tj... ti, мы остановились во внутренней вершине или на ребре (как в случае 2), но дальше уже есть буква ti+1, не создаем ничего нового.