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

Эту статью следует викифицировать. Пожалуйста, оформите её согласно общим правилам и указаниям.

Суффиксное дерево — способ организации данных (строк), позволяющий выяснять, входит ли строка w в строку t, за время O(|w|), где w — длина строки w.

Основные определения и описание структуры

$\Sigma$ — непустое конечное множество символов, называемое алфавитом. Последовательность символов (возможно, пустая) из алфавита обозначается буквами r, s и t. $t^{-1}$ представляет собой перевёрнутую строку. Отдельные символы обозначаются буквами x, y или z. $\varepsilon$ — пустая строка. Символами из алфавита являются буквы a, b, .... Пока размер алфавита принимается постоянным. |t| обозначает длину строки t. $\Sigma^m$ — все строки длины m, $\Sigma^*=\bigcup\limits_{i=0}^{\infty}\Sigma^i$ и $\Sigma^+=\Sigma^*\backslash \{\varepsilon\}$.

Префикс w строки t — строка такая, что wv = t для некоторой (возможно, пустой) строки v. Префикс называется собственным, если |v| $\ne$ 0.

Суффикс w строки t — строка такая, что vw = t для некоторой (возможно, пустой) строки v. Суффикс называется собственным, если |v| $\ne$ 0. Например, для строки «substring» подстрока «sub» является собственным префиксом, «ring» — собственным суффиксом.

Подстрока w строки t называется правым ветвлением, если t может быть представлена как uwxv и $u'wyv'$ для некоторых строк $u, v, u'$ и $v'$, а также букв x $\ne$ y. Левое ветвление определяется аналогично. Например, для «eabceeabcd» подстрока «abc» является правым ветвлением, т.к. в обоих её вхождениях в t справа от неё стоят различные символы, зато та же подстрока не является левым ветвлением, потому что слева от неё в обоих вхождениях стоит одинаковый символ «e».

$\Sigma^+$-дерево T — корневое дерево с рёбрами, помеченными последовательностями из $\Sigma^+$. Для каждого символа a из алфавита каждый узел в дереве T имеет не более одного ребра, метка которого начинается c символа a. Ребро от t до s с меткой v мы будем обозначать $t \longrightarrow_v s$.

350px

Пусть k — узел $\Sigma^+$-дерева T, тогда path(k) — строка, которая представляет собой конкатенацию всех меток рёбер от корня до k. Мы назовем $\overline{w}$ местоположением w, для которого path($\overline{w}$) = w.

Т.к. каждая ветвь уникальна, если path(t) = w, мы можем обозначить узел t за $\overline{w}$. Поддерево узла $\overline{w}$ обозначается $T_{\overline{w}}$.

Слова, которые представлены в $\Sigma^+$-дереве T, задаются множеством, которое обозначается words(T). Слово w входит во множество words(T) тогда и только тогда, когда существует строка v (возможно, пустая) такая, что $\overline{wv}$ — узел дерева T.

Если строка w входит в words(T), w = uv, $\overline{u}$ — узел дерева T, пару $(\overline{u}, v)$ будем называть ссылочной парой w по отношению к дереву T. Если u — наидлиннейший префикс такой, что $(\overline{u}, v)$ — ссылочная пара, мы будем называть $(\overline{u}, v)$ канонической ссылочной парой. Тогда мы будем писать $\widehat{w} = (\overline{u},v)$. Местоположение $\widehat{w} = (\overline{u},v)$ называется явным, если |v| = 0, и неявным в противном случае.

$\Sigma^+$-дерево T, в котором каждое ребро помечено одиночным символом, называется атомарным (для него каждое местоположение является явным). $\Sigma^+$-дерево T, в котором каждый узел является либо корнем, либо листом или узлом ветвления, называется компактным.

300px

300px

Атомарное $\Sigma^+$-дерево также называют $trie$ (луч). Атомарное и компактное $\Sigma^+$-дерево однозначно определены словами, которые они содержат.

Суффиксное дерево для строки t — это $\Sigma^+$-дерево такое, что words(T) = {w| w — подслово t}. Для строки t атомарное суффиксное дерево обозначается ast(t), компактное суффиксное дерево обозначается cst(t).

Обратное префиксное дерево строки t — это суффиксное дерево для строки $t^{-1}$.

Вложенный суффикс — суффикс, который входит в строку t где-нибудь ещё, наидлиннейший вложенный суффикс называется активным суффиксом строки t.

Свойства суффиксных деревьев

Лемма. Местоположение w явно в компактном суффиксном дереве тогда и только тогда, когда w не является вложенным суффиксом t или w — правое ветвление.

Доказательство. $\Rightarrow$. Если $\overline{w}$ явно, то это может быть либо лист, либо вершина ветвления или корень (в этом случае $w = \varepsilon$ и w — вложенный суффикс t).

Если $\overline{w}$ — лист, тогда также является и суффиксом t. Значит, это должен быть не вложенный суффикс, т.к. иначе он появился бы где-нибудь ещё в строке t: $\exists$ v — суффикс t такой, что w — префикс v. Этот узел не может быть листом.

Если $\overline{w}$ — узел ветвления, тогда должны существовать, по меньшей мере, два выходящих ребра из $\overline{w}$ с различными метками. Это означает, что существуют два различных суффикса u, v, что w — префикс u и w — префикс v, где v = wxs, u = $wx's'$, x $\ne x'$. Следовательно, w — правое ветвление.

$\Leftarrow$. Если w не является вложенным суффиксом t, это должен быть лист. Если w — правое ветвление, то имеются два суффикса u и v, u = wxs, v = $wx's'$, x $\ne x'$, тогда w является узлом ветвления. Лемма доказана.

Теперь легко видеть, почему ответ на вопрос, входит ли слово w в строку t, может быть найден за время O(|w|): нужно только проверить, является ли w местоположением (явным или неявным) в cst(t).

Метки рёбер должны представлять собой указатели на положение в строке, чтобы суффиксное дерево расходовало память размером O(n). Метка (p,q) ребра означает подстроку $t_p\ldots t_q$ или пустую строку, если p > q.

Укконен вводит название открытые рёбра для рёбер, заканчивающихся в листьях. Пометки открытых рёбер записывают как (p, $\infty$) вместо (p, |t|), где $\infty$ — длина, всегда большая, чем |t|.

Пусть T — $\Sigma^+$-дерево. Пусть $\overline{aw}$ — узел T, v — наидлиннейший суффикс w такой, что $\overline{v}$ — также узел T. Непомеченное ребро от $\overline{aw}$ до $\overline{v}$ называется суффиксным звеном. Если v = w, оно называется атомарным.

Утверждение. В ast(t) и cst(t$), где $ $\notin$ t, все суффиксные звенья являются атомарными.

Доказательство. Символ $ называется символом-стражем. Первая часть (для ast(t)) следует из определения, т.к. местоположения являются явными. Для доказательства второй (случай cst(t)) части мы должны показать, что для каждого узла $\overline{aw}$ $\overline{w}$ также является узлом cst(t). Если $\overline{aw}$ — узел cst(t), то является либо листом, либо узлом ветвления. Если является листом, тогда w — не вложенный суффикс t. Благодаря символу-стражу, из леммы следует, что все суффиксы (включая корень, пустой суффикс) являются явными, т.к. только корень — вложенный суффикс. Поэтому w является листом или корнем. Если $\overline{aw}$ — узел ветвления, тогда aw — правое ветвление, как и w. Следовательно, местоположение $\overline{w}$ явно по лемме. Утверждение доказано.

Как следует из этого доказательства, символ-страж гарантирует существование листьев для всех суффиксов. С таким символом не может быть вложенных суффиксов, кроме пустого. Если мы опустим символ-страж, некоторые суффиксы могут стать вложенными, и их местоположения станут неявными.

Требования суффиксного дерева к памяти

Утверждение. Компактное суффиксное дерево может быть представлено в виде, требующем O(n) памяти.

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

Для представления строк, являющихся метками рёбер, мы используем индексацию в исходной строке, как описано выше. Каждый узел имеет не более одного предка и, таким образом, общее число ребер не превышает 2n.

Аналогично, каждый узел имеет не более одного суффиксного звена, тогда общее число суффиксных звеньев также ограничено числом 2n. Утверждение доказано.

Как пример суффиксного дерева с 2n-1 вершинами можно рассмотреть дерево для слова $a^n$$. Размер атомарного суффиксного дерева для строки t составляет O($n^2$).

Построение дерева за линейное время. Алгоритм «MCC». («McCreight's Algorithm»)

Алгоритм «mсс» начинает работу с пустого дерева и добавляет суффиксы начиная с самого длинного. Алгоритм «mcc» не является алгоритмом «реального времени», т.е. для его работы необходима вся строка целиком. Для корректной работы требуется, чтобы строка завершалась специальным символом, отличным от других, так, чтобы ни один суффикс не являлся префиксом другого суффикса. Каждому суффиксу в дереве будет соответствовать лист. Для алгоритма мы определим $суф_i$ — текущий суффикс (на шаге $i$), $голова_i$ — наибольший префикс суффикса $суф_i$, который является также префиксом другого суффикса $суф_j$, где $j < i$. $хвост_i$ определим как $суф_i-голова_i$.

Ключевой идеей алгоритма «mcc» является соотношение между $голова_i$ и $голова_{i-1}$.

Лемма. Если $голова_{i-1} = aw$ где $a$ — буква алфавита, $w$ — строка (может быть пустая), тогда $w$ — префикс $голова_i$.

Доказательство. Пусть $голова_{i-1} = aw$. Тогда существует $j$, $j < i$, такой, что $aw$ является как префиксом $суф_{i-1}$, так и префиксом $суф_{j-1}$. Тогда $w$ — префикс $суф_j$ и $суф_j$, следовательно, $w$ является префиксом головы $голова_i$. Лемма доказана.

Мы знаем местоположение $голова_{i-1} = aw$, и если мы будем иметь суффиксное звено,то можем быстро перейти к местоположению $w$ — префикса головы $голова_i$ без необходимости находить путь от корня дерева. Но местоположение $\overline{w}$ могло бы не являться явным (если местоположение $\overline{голова_{i-1}}$ не было явным на предыдущем шаге) и суффиксное звено могло бы быть ещё не установлено для узла $\overline{голова_{i-1}}$. Решение, данное МакКреем, находит узел $\overline{голова_i}$ за два шага: «повторное сканирование» и «сканирование». Мы проходим дерево наверх от узла $\overline{голова_{i-1}}$ пока не найдем суффиксное звено, следуем по нему и затем применяем повторное сканирование пути до местоположения $w$ (которое является простым, потому что мы знаем длину $w$ и это местоположение существует, так что мы не должны читать полные метки ребер, двигаясь вниз по дереву, мы можем просто проверять только начальные буквы и длину слов). Рисунок демонстрирует эту идею. Вместо попытки найти путь от корня до узла $f$, алгоритм переходит до $a$, следует суффиксному звену до $d$, проводит повторное сканирование пути до (возможно неявного) местоположения $e$ и остается найти путь до $f$, проходя посимвольно.

Алгоритм состоит из трех частей.

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

2. Затем он повторно сканирует часть предыдущей головы, для которой длина является известной (эта часть названа $\beta$).

3. Наконец алгоритм устанавливает суффиксное звено для $голова_{i-1}$, сканирует оставшуюся часть $голова_i$ (названную $\gamma$) и добавляет новый лист для $хвост_i$.

Узел ветвления создается во второй фазе повторного сканирования, если не существует местоположения $w$. В этом случае сканирование не является необходимым, потому что если $голова_i$ была бы длиннее чем $\alpha\beta$, тогда $\alpha\beta\gamma$ являлось бы правым ветвлением, но по лемме $\alpha\beta$ является также правым ветвлением, так узел $\overline{\alpha\beta}$ уже должен существовать. Узел создается в третьей фазе, если местоположение $\overline{голова_i}$ ещё не явно.

Алгоритм 1

Вход: строка t

1: T: = пустое дерево;

2: голова0 := $\epsilon$;

3: n:= ДЛИНА(t);

4: ОТ i:= 1 ДО n ВЫП

5: найти $\chi$, $\alpha$, $\beta$ такие, что

а. головаi-1 = $\chi\alpha\beta$,

б. если предок узла головаi-1 не корень, обозначим его $\overline{\chi\alpha}$, в противном случае $|\alpha|=0$

в. $|\chi|\le0$ и ($|\chi| = 0 \Leftrightarrow$ |головаi-1| = 0)

6: ЕСЛИ ($|\alpha|$ >0) ТО

7: следовать по суффиксному звену от узла $\overline{\chi\alpha}$ до $\overline{\alpha}$;

8: КОН;

9: $\overline{\chi\alpha}$ := Перескан($\overline{\alpha},\beta$);

10: установить суффиксное звено от $\overline{голова_{i-1}}$ до $\overline{\alpha\beta}$

11: ($\overline{голова_{i-1}}$,хвостi) := Скан($\overline{\alpha\beta}$,суфi-$\alpha\beta$);

12: добавить лист, соответствующий хвостi

13: КОН

Обратите внимание, что если $|\alpha| = 0$ тогда $\overline{\alpha} = корень$ и узнается одинаково быстро, как следуя суффиксному звену согласно строке 7 алгоритма.

Процедура Перескан ищет местоположение $\alpha\beta$. Если местоположение $\overline{\alpha\beta}$ еще не явно, добавляется новый узел. Этот случай имеет место, когда голова просмотрена целиком: если голова длиннее (и узел уже определен), $\alpha\beta$ должно являться префиксом более чем двух суффиксов и также является левым ветвлением $t$. Местоположение $\overline{\alpha\beta}$ может являться только явным, если этот узел уже является узлом ветвления, и если $\alpha\beta$ не было левым ветвлением тогда $голова_{i-1}$, должно быть, был длиннее, потому что встретился более длинный префикс.

Процедура Скан производит поиск в глубину дерева и возвращает позицию.

Процедура 1 Перескан(n,$\beta$)

Вход: узел n', строка $\beta$

1: i:=1;

2: ПОКА i$\le$ |$\beta$|ВЫП

3: найти ребро e=n${\stackrel{w}{\longrightarrow}}$n',w1 = $\beta$1;

4: ЕСЛИ i+|w|>|$\beta$|+1 ТО

5: k:=|$\beta$|-i+1;

6: расщепить ребро e с новым узлом m и ребрами n${\stackrel{w_1\ldots w_k}{\longrightarrow}}$m и m${\stackrel{w_{k+1}\ldots w_{|w|}}{\longrightarrow}}$n';

7: ВОЗВРАТ m

8: КОН;

9: i:=i+|w|;

10: n:=n'

11: КОН;

12: ВОЗВРАТ n'

Процедура 2 Скан(n,$\gamma$)

Вход: узел n', строка $\gamma$

1: i:=1;

2: ПОКА существует ребро e=n${\stackrel{w}{\longrightarrow}}$n', w1 = $\gamma$i ВЫП

3: k:=1;

4: ПОКА wk = $\gamma$i и k$\le$|w| ВЫП

5: k:=k+1;

6: i:=i+1;

7: КОН

8: ЕСЛИ k>|w| ТО

9: n:=n';

10: ИНАЧЕ

11: расщепить ребро e с новым узлом m и ребрами n${\stackrel{w_1\ldots w_{k-1}}{\longrightarrow}}$m и m${\stackrel{w_{k}\ldots w_{|w|}}{\longrightarrow}}$n';

12: ВОЗВРАТ (m,$\gamma$i,...,$\gamma_{|\gamma|}$)

13: КОН

14: КОН

15: ВОЗВРАТ (n,$\gamma$i,...,$\gamma_{|\gamma|}$)

Внешние ссылки

• Moritz Maaß Suffix Trees and their Applications.
• Суффиксные деревья на сайте algolist.manual.ru
• Suffix Trees in Python — на Pythonе