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

Разделы:

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метки рёбер должны представлять собой указатели на положение в строке, чтобы суффиксное дерево расходовало память размером O(n). Метка (p, q) ребра означает подстроку tp…tq{displaystyle t_{p}ldots t_{q}} $t_{p}ldots t_{q}$ или пустую строку, если p > q.

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм mсс начинает работу с пустого дерева и добавляет суффиксы начиная с самого длинного. Алгоритм mcc не является on-line алгоритмом, то есть для его работы необходима вся строка целиком. Для корректной работы требуется, чтобы строка завершалась специальным символом, отличным от других, так, чтобы ни один суффикс не являлся префиксом другого суффикса. Каждому суффиксу в дереве будет соответствовать лист.Для алгоритма мы определим sufi{displaystyle suf_{i}} $suf_{i}$ — текущий суффикс (на шаге i{displaystyle i} $i$ ), headi{displaystyle head_{i}} $head_{i}$ (голова) — наибольший префикс суффикса sufi{displaystyle suf_{i}} $suf_{i}$ , который является также префиксом другого суффикса sufj{displaystyle suf_{j}} $suf_{j}$ , где j<i{displaystyle j<i} $j<i$ . taili{displaystyle tail_{i}} $tail_{i}$ (хвост) определим как sufi−headi{displaystyle suf_{i}-head_{i}} $suf_{i}-head_{i}$ .

Ключевой идеей алгоритма mcc является соотношение между headi{displaystyle head_{i}} $head_{i}$ и headi−1{displaystyle head_{i-1}} $head_{{i-1}}$ .

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

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

Мы знаем местоположение headi−1=aw{displaystyle head_{i-1}=aw} $head_{{i-1}}=aw$ , и если мы будем иметь суффиксное звено, то можем быстро перейти к местоположению w{displaystyle w} $w$ — префикса головы headi{displaystyle head_{i}} $head_{i}$ без необходимости находить путь от корня дерева. Но местоположение w¯{displaystyle {overline {w}}} $overline {w}$ могло бы не являться явным (если местоположение headi−1¯{displaystyle {overline {head_{i-1}}}} $overline {head_{{i-1}}}$ не было явным на предыдущем шаге) и суффиксное звено могло бы быть ещё не установлено для узла headi−1¯{displaystyle {overline {head_{i-1}}}} $overline {head_{{i-1}}}$ .Решение, данное МакКреем, находит узел headi¯{displaystyle {overline {head_{i}}}} $overline {head_{i}}$ за два шага: «повторное сканирование» («rescanning») и «сканирование» («scanning»). Мы проходим дерево наверх от узла headi−1¯{displaystyle {overline {head_{i-1}}}} $overline {head_{{i-1}}}$ пока не найдем суффиксное звено, следуем по нему и затем применяем повторное сканирование пути до местоположения w{displaystyle w} $w$ (которое является простым, потому что мы знаем длину w{displaystyle w} $w$ и это местоположение существует, так что мы не должны читать полные метки ребер, двигаясь вниз по дереву, мы можем просто проверять только начальные буквы и длину слов).

Рисунок демонстрирует эту идею. Вместо попытки найти путь от корня до узла f{displaystyle f} $f$ , алгоритм переходит до a{displaystyle a} $a$ , следует суффиксному звену до d{displaystyle d} $d$ , проводит повторное сканирование пути до (возможно неявного) местоположения e{displaystyle e} $e$ и остается найти путь до f{displaystyle f} $f$ , проходя посимвольно.

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

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

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

3. Наконец алгоритм устанавливает суффиксное звено для headi−1{displaystyle head_{i-1}} $head_{{i-1}}$ , сканирует оставшуюся часть headi{displaystyle head_{i}} $head_{i}$ (названную γ{displaystyle gamma } $gamma$ ) и добавляет новый лист для taili{displaystyle tail_{i}} $tail_{i}$ .

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

Алгоритм 1 (mcc, McCreight)Вход: строка t 1: T: = пустое дерево; 2: head0 := ϵ{displaystyle epsilon } $epsilon$ ; 3: n:= length(t); 4: for i:= 1 to n do 5: найти χ{displaystyle chi } $chi$ , α{displaystyle alpha } $alpha$ , β{displaystyle beta } $beta$ такие, что a. headi-1 = χαβ{displaystyle chi alpha beta } $chi alpha beta$ , b. если предок узла headi-1 не корень (root), обозначим его χα¯{displaystyle {overline {chi alpha }}} $overline {chi alpha }$ , в противном случае |α|=0{displaystyle |alpha |=0} $|alpha |=0$ c. |χ|≤1{displaystyle |chi |leq 1} $|chi |leq 1$ и (|χ|=0⇔{displaystyle |chi |=0Leftrightarrow } $|chi |=0Leftrightarrow$ |headi-1| = 0) 6: if (|α|{displaystyle |alpha |} $|alpha |$ >0) then 7: следовать по суффиксному звену от узла χα¯{displaystyle {overline {chi alpha }}} $overline {chi alpha }$ до α¯{displaystyle {overline {alpha }}} $overline {alpha }$ ; 8: end if 9: αβ¯{displaystyle {overline {alpha beta }}} $overline {alpha beta }$ := Rescan(α¯,β{displaystyle {overline {alpha }},beta } $overline {alpha },beta$ );10: установить суффиксное звено от headi−1¯{displaystyle {overline {head_{i-1}}}} $overline {head_{{i-1}}}$ до αβ¯{displaystyle {overline {alpha beta }}} $overline {alpha beta }$ 11: (headi¯{displaystyle {overline {head_{i}}}} $overline {head_{{i}}}$ ,taili) := Scan(αβ¯{displaystyle {overline {alpha beta }}} $overline {alpha beta }$ ,sufi-αβ{displaystyle alpha beta } $alpha beta$ );12: добавить лист, соответствующий taili;13: end for

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

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

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

Процедура 1 Rescan(n,β{displaystyle beta } $beta$ )Вход: узел n, строка β{displaystyle beta } $beta$ 1: i:=1; 2: while i≤{displaystyle leq } $leq$ |β{displaystyle beta } $beta$ |do 3: найти ребро e=n⟶w{displaystyle {stackrel {w}{longrightarrow }}} ${{stackrel {w}{longrightarrow }}}$ n’,w1 = β{displaystyle beta } $beta$ 1; 4: if i+|w|>|β{displaystyle beta } $beta$ |+1 then 5: k:=|β{displaystyle beta } $beta$ |-i+1; 6: расщепить ребро e с новым узлом m и ребрами n⟶w1…wk{displaystyle {stackrel {w_{1}ldots w_{k}}{longrightarrow }}} ${{stackrel {w_{1}ldots w_{k}}{longrightarrow }}}$ m и m⟶wk+1…w|w|{displaystyle {stackrel {w_{k+1}ldots w_{|w|}}{longrightarrow }}} ${{stackrel {w_{{k+1}}ldots w_{{|w|}}}{longrightarrow }}}$ n’; 7: return m; 8: end if 9: i:=i+|w|;10: n:=n’;11: end while12: return n’;

Процедура 2 Scan(n,γ{displaystyle gamma } $gamma$ )Вход: узел n, строка γ{displaystyle gamma } $gamma$ 1: i:=1; 2: while существует ребро e=n⟶w{displaystyle {stackrel {w}{longrightarrow }}} ${{stackrel {w}{longrightarrow }}}$ n’, w1 = γ{displaystyle gamma } $gamma$ i do 3: k:=1; 4: while wk = γ{displaystyle gamma } $gamma$ i и k≤{displaystyle leq } $leq$ |w| do 5: k:=k+1; 6: i:=i+1; 7: end while 8: if k>|w| then 9: n:=n’;10: else11: расщепить ребро e с новым узлом m и ребрами n⟶w1…wk−1{displaystyle {stackrel {w_{1}ldots w_{k-1}}{longrightarrow }}} ${{stackrel {w_{1}ldots w_{{k-1}}}{longrightarrow }}}$ m и m⟶wk…w|w|{displaystyle {stackrel {w_{k}ldots w_{|w|}}{longrightarrow }}} ${{stackrel {w_{{k}}ldots w_{{|w|}}}{longrightarrow }}}$ n’;12: return (m,γ{displaystyle gamma } $gamma$ i,…,γ|γ|{displaystyle gamma _{|gamma |}} $gamma _{{|gamma |}}$ );13: end if14: end while15: return (n,γ{displaystyle gamma } $gamma$ i,…,γ|γ|{displaystyle gamma _{|gamma |}} $gamma _{{|gamma |}}$ );

Построение дерева за линейное время. Алгоритм ukk. (Ukkonens’s Algorithm)

Алгоритм, который изобрел Эско Укконен для построения суффиксного дереваза линейное время, вероятно, самый простой из таких алгоритмов.Простота происходит оттого, что алгоритм можно представить сначала как простой,но не эффективный метод, который с помощью нескольких приемов реализации науровне «здравого смысла» достигает уровня лучших алгоритмов по времени счетав наихудших условиях. В PDF with figures сделано примерно тоже самое. Про алгоритм Укконена на английском языке можно прочестьв английской вики.

Для алгоритма Укконена нам потребуются

1) Неявные суффиксные деревья 2) Общее описание алгоритма3) Оптимизация алгоритма

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

Файл:CуффиксноеДерево.jpg Суффиксное дерево для строки xabxa$Файл:НеявноеCуффиксноеДерево.jpg Неявное суффиксное дерево для строки xabxa$

Алгоритм Укконена строит последовательность неявных суффиксных деревьев,последнее из которых преобразуется в настоящее суффиксное дерево строки S.

Неявное суффиксное дерево строки S — это дерево,полученное из суффиксного дерева S$ удалением всех вхождений терминального символа $ из меток дуг дерева, удалением после этого дуг без меток иудалением затем вершин, имеющих меньше двух детей. Неявное суффиксное дерево префикса S[l..i] строки S аналогично получается из суффиксного дерева для S[l..i]$ удалением символов $, дуг и вершин, как описано выше.

Неявное суффиксное дерево для любой строки S будет иметь меньше листьев,чем суффиксное дерево для строки S$, в том и только том случае, если хотя бы одиниз суффиксов S является префиксом другого суффикса. Терминальный символ $ былдобавлен к концу S как раз во избежание этой ситуации. В определении настоящего суффиксного дерево это очень важный момент.Однако если S заканчивается символом, который больше нигде в S не появляется, то неявное суффиксное дереводля S будет иметь лист для каждого суффикса и, следовательно, будет настоящимсуффиксным деревом.

Хотя неявное суффиксное дерево может иметь листья не для всех суффиксов,в нем закодированы все суффиксы S — каждый произносится символами какого-либопути от корня этого неявного суффиксного дерева. Однако если этот путь некончается листом, то не будет маркера, обозначающего конец пути. Таким образом, неявные суффиксные деревья сами по себе несколько менее информативны, чемнастоящие. Мы будем использовать их только как вспомогательное средство в алгоритмеУкконена, чтобы получить настоящее суффиксное дерево для S.

Общее описание алгоритма.

Построить дерево T. for i from 1 to m — 1 do begin {фаза i + 1} for j from 1 to i + 1 begin {продолжение j} найти в текущем дереве конец пути из корня с меткой S[j..i]. Если нужно, продолжить путь, добавив символ S(i + 1), обеспечив появление строки S[j..i + 1] в дереве, end; end;

Алгоритм Укконена строит неявное суффиксное дерево Ti для каждого префиксаS[l..i] строки S, начиная с T1 и увеличивая i на единицу, пока не будет построеноTm. Настоящее суффиксное дерево для S получается из Tm, и вся работа требуетвремени О(m). Мы объясним алгоритм Укконена, представив сначала метод, с помощьюкоторого все деревья строятся за времяO(m³),а затем оптимизируемреализацию этого метода так, что будет достигнута заявленная скорость.

Три правила продолжения суффикса.

Чтобы превратить это общее описание в алгоритм, мы должны точно указать, каквыполнять продолжение суффикса. Пусть S[j..i] = β — суффикс S[1..i]. В продолжении j, когда алгоритм находит конец β в текущем дереве, он продолжает β, чтобыобеспечить присутствие суффикса βS(i + 1) в дереве. Алгоритм действует по одномуиз следующих трех правил.

Правило 1. В текущем дереве путь β кончается в листе. Это значит, что путь откорня с меткой β доходит до конца некоторой «листовой» дуги (дуги, входящейв лист). При изменении дерева нужно добавить к концу метки этой листовой дугисимвол S(i + 1).

Правило 2. Ни один путь из конца строки β не начинается символом S(i + 1), но поКрайней мере один начинающийся оттуда путь имеется.В этом случае должна быть создана новая листовая дуга, начинающаяся в конце β помеченная символом S(i + 1). При этом, если β кончается внутри дуги, должнабыть создана новая вершина. Листу в конце новой листовой дуги сопоставляетсяномер j. Таким образом в правиле 2 возможно два случая.

Правило 3. Некоторый путь из конца строки β начинается символом S(i + 1). В этомслучае строка βS(i + 1) уже имеется в текущем дереве, так что ничего не надо делать(в неявном суффиксном дереве конец суффикса не нужно помечать явно).

Литература

Дэн Гасфилд. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер. с англ. И. В. Романовского. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.