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

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

Определение

Определение:

Суффиксное дерево (сжатое суффиксное дерево) $T$ для строки $s$ (где $|s| = n$) — дерево с $n$ листьями, обладающее следующими свойствами: Каждая внутренняя вершина дерева имеет не меньше двух детей; Каждое ребро помечено непустой подстрокой строки $s$; Никакие два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа; Дерево должно содержать все суффиксы строки $s$, причем каждый суффикс заканчивается точно в листе и нигде кроме него.

Суффиксное дерево для строки $xabxa$ с защитным символом

Данное определение порождает следующую проблему:
Рассмотрим дерево для строки $xabxa$: суффикс $xa$ является префиксом суффикса $xabxa$, а, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки $s$ добавляют символ, не входящий в исходный алфавит: защитный символ. Обозначим его как $\$$. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т. к. в такой строке не существует двух различных подстрок одинаковой длины, заканчивающихся на $\$$.

Далее $n$ — длина строки $s$ с защитным символом.

Количество вершин

По определению, в суффиксном дереве содержится $n$ листьев. Оценим количество внутренних вершин такого дерева.

Лемма:

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

Доказательство:

$\triangleright$

Докажем лемму индукцией по количеству листьев $n$. База При $n = 2$ в дереве одна внутренняя вершина, следовательно утверждение верно. Переход $n \rightarrow n + 1$ Возьмем вершину в дереве с $n + 1$ листами, у которой два ребенка — листья. Рассмотрим возможные случаи: У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с $n$ листьями, причем в нем количество внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее $n$ внутренних вершин, а, значит, и для исходного дерева лемма верна. У нее ровно два ребенка. Отрежем их, получим дерево с $n - 1$ листьями, количество внутренних вершин которого на $1$ меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее $n - 1$ внутренних вершин, значит, в исходном дереве их меньше $n$.

$\triangleleft$

Занимаемая память

Представим дерево как двумерный массив размера $|V| \times |\Sigma|$, где $|V|$ — количество вершин в дереве, $|\Sigma|$ — мощность алфавита. Для любого суффиксного дерева верна предыдущая лемма (у каждой вершины, по определению, не менее двух детей), значит, $|V| = O(2 n)$. Каждая $[i][j]$ ячейка содержит информацию о том, в какую вершину ведет ребро из $i$-ой вершины по $j$-ому символу и индексы $l, r$ начала и конца подстроки, записанной на данном переходе. Итак, дерево занимает $O(n|\Sigma|)$ памяти.

Построение суффиксного дерева

Наивный алгоритм

Рассмотрим наивный алгоритм построения суффиксного дерева строки $s$:

go[0] = Vertex() // корень
count = 0        // номер последней вершины, созданной в дереве (глобальная переменная)
for i = 0 to n   // для каждого символа строки
    insert(i, n) // добавляем суффикс, начинающийся с него

void insert(int l, int r):
    cur = 0 
    while (l < r)
        if (go[cur][s[l]].v = -1)         // если мы не можем пойти из вершины по символу $l$
            createVertex(cur, l, r)       // создаем новую вершину 
        else
            start = go[cur][s[l]].l
            finish = go[cur][s[l]].r
            hasCut = false
            for j = start to finish       // для каждого символа на ребре из текущей вершины
                if (s[l+j-start] != s[j]) // если нашли не совпадающий символ
                    // создаем вершину на ребре
                    old = go[cur][s[l]]
                    createVertex(cur, l, j - 1)
                    go[count][s[j]].v = old
                    go[count][s[j]].r = j
                    go[count][s[j]].l = finish
                    createVertex(count, l + j - start, r)
                    hasCut = true
                    break
            if (!hasCut)
                cur = go[cur][s[l]].v  // переходим по ребру
                l = l + finish - start // двигаемся по суффиксу на длину подстроки, записанной на ребре
            else
                break

void createVertex(int cur, int l, int r):
    go[++count] = Vertex()
    go[cur][s[l]].v = count
    go[cur][s[l]].l = l
    go[cur][s[l]].r = r

Этот алгоритм работает за время $O(n^2)$, однако алгоритм Укконена позволяет построить сжатое суффиксное дерево за $O(n)$.

Построение из суффиксного массива

Пусть нам известен суффиксный массив $suf$ строки $s$, его можно получить алгоритмом Карккайнена-Сандерса за линейное время. Для преобразования нам также понадобится массив $lcp$ (longest common prefix), который можно получить алгоритмом Касаи.

В этом преобразовании используется тот же инвариант, что и в других суффиксных структурах:

1. Строка $s$ заканчивается специальным символом, который больше не встречается в строке.
2. Следствие: $lcp[i] \lt len[i - 1]$, где $len[i - 1]$ — длина суффикса, соответствующего $suf[i - 1]$.

Будем строить дерево, добавляя суффиксы в лексикографическом порядке. Чтобы ускорить добавление, будем использовать то, что $i$-ый суффикс имеет с предыдущим $lcp[i]$ общих символов. Тогда добавление из корня не отличается от того, что мы поднимемся вверх из предыдущего суффикса до глубины $lcp[i]$ и продолжим построение оттуда. Инвариант позволяет нам утверждать, что ни один лист мы не сможем продолжить, и нам всегда нужно будет хоть раз подняться из него вверх. Поскольку суффиксы отсортированы лексикографически, мы не будем спускаться по ребру после того, как уже поднялись из него из-за несовпадения символа. Все это позволяет сформулировать алгоритм добавления суффикса по известной вершине предыдущего суффикса:

1. Подняться из вершины вверх до глубины $lcp$
2. Если эта глубина находится на ребре, разрезать ребро по ней.
3. Вставить новую вершину как сына вершины с глубиной $lcp$

В вершинах дерева $Node$ мы будем хранить предка $parent$, стек детей в лексикографическом порядке ребер $children$, глубину вершины в символах от корня $depth$. Соответственно, конструктор вершины имеет вид Node(Node parent, int depth).

Node addNextSuffix(Node previous, int length, int lcp):
   if (previous.depth == 0 or previous.depth == lcp)           // Добавляем к сыновьям текущей вершины 
      added = Node(previous, length)
      previous.children.push(added)
      return added
   else
      if previous.parent.depth < lcp:                          // Нужно разрезать ребро 
         inserted = Node(prevous.parent, lcp)
         previous.parent.children.pop()
         previous.parent.children.push(inserted)
         inserted.children.push(previous)
         previous.parent = inserted
      return addNextSuffix(previous.parent, length, lcp)      
      
Node buildSuffixTree(int[] suf, int[] lcp, int length):
   root = Node(null, 0)
   previous = root
   for i = 1 to length
      previous = addNextSuffix(previous, length - suf[i], lcp[i])
   return root

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

Тогда ребро $s[start, end]$ определяется так:

function calculatePositions(Node parent, Node child, int stringLength):
   start = stringLength - child.maxDepth + parent.depth
   end = start + child.depth - parent.depth - 1

Для асимптотического анализа будем использовать в качестве потенциала глубину в вершинах. При добавлении суффикса мы спускаемся один раз, подняться выше корня мы не можем, значит, и подниматься мы будем суммарно $O(n)$ раз. Обход в глубину также выполняется за $O(n)$, итоговая асимптотика $O(n)$.

Использование сжатого суффиксного дерева

Суффиксное дерево позволяет за линейное время найти:

• Количество различных подстрок данной строки
• Наибольшую общую подстроку двух строк
• Суффиксный массив и массив $lcp$ (longest common prefix) исходной строки
• Строку максимальной длины, ветвящуюся влево и вправо за $ST + O(n)$

Построение суффиксного массива и массива lcp из суффиксного дерева

Пусть к строке дописан специальный символ для сохранения инварианта. Рассмотрим лексикографический по ребрам порядок обхода сжатого суффиксного дерева. Пусть два суффикса имеют общее начало, но различаются в $i$-ом символе. Первым будет рассмотрено поддерево по ребру с меньшим символом, значит и лист, соответствующий этому суффиксу, будет посещен первым.

Тогда суффиксный массив строится из суффиксного дерева обходом в глубину в указанном порядке. Пусть длина строки $length$, глубина листа в символах $depth$, тогда номер суффикса $i = length - depth$.

Для заполнения массива $lcp$ нам понадобится вершина $minNode$, которая будет означать вершину с минимальной глубиной, в которую мы поднимались при переходе между суффиксами. Поскольку мы точно поднимались туда, но не поднимались выше, это будет наименьший общий предок этих узлов. Из этого следует, что у рассматриваемых суффиксов совпадает ровно $lcp = minNode.depth$ символов.

int curPos = 0
Node minNode = root
// Для заполнения нужно вызвать dfs(root) 
function dfs(Node n):
   if n.children.size == 0
      suf[curPos] = length - n.depth
      lcp[curPos] = minNode.depth
      curPos++
      minNode = n
   else
      foreach child in n.children
         if n.depth < minNode.depth:
            minNode = n
         dfs(child)

Асимптотика алгоритма совпадает с асимптотикой обхода в глубину и составляет $O(n)$.

Таким образом, мы умеем за $O(n)$ строить суффиксное дерево, суффиксный массив и преобразовывать одно в другое.

Поиск строки максимальной длины, ветвящейся влево и вправо

Определение:

Строка $s$ называется ветвящейся вправо в $t$ (англ. right branching string), если существуют символы $c$ и $d$, такие что $c$ $\ne$ $d$ : $sc$ и $sd$ — подстроки $t$. Аналогично, ветвящаяся влево (англ. left branching), если $cs$ и $ds$ — подстроки $t$.

Суффиксное дерево для строки $aabcabd$

Построим cуффиксное дерево при помощи алгоритма Укконена. В полученном дереве не листовой вершине $v$ будет соответствовать подстрока $s$, которая ветвится вправо, при условии, что количество "хороших" детей вершины $v \gt 2$ ("хорошие" дети — листы, метка которых $\ne\$$). В примере для строки $aabcabd$ это $b$, $a$ и $ab$. Далее введём термины левый символ и вершина различная влево, чтобы найти строки, ветвящиеся влево.

Определение:

Левый символ для позиции $i$ строки $S$ — это символ $S(i-1)$. Левым символом листа $L$ называется левый символ начала суффикса, ведущего в этот лист.

Определение:

Вершина $v$ различна влево, если как минимум два листа в поддереве $v$ имеют различные левые символы. По определению лист не может быть различным влево.

Левые вершины и символы для суффиксного дерева над строкой $aabcabd$ (символом $\#$ помечены различные влево вершины)

Допустим, что строка ветвится влево. Пусть существуют подстроки $cs$ и $ds$, тогда есть два суффикса, начинающиеся с $s$, которым соответствуют различные листовые вершины с различными левыми символами ($c$ и $d$). Также в дереве существует внутренняя вершина $v$, соответствующая строке $s$. Из определения следует, что $v$ различна влево.

Чтобы найти строки, ветвящиеся влево, нужно проверить все внутренние вершины суффиксного дерева на различность влево. Если какая-то вершина $v$ будет различна влево и удовлетворять свойству ветвимости право, то строка, соответствующая вершине $v$ будет ветвится вправо и влево.

Чтобы найти вершины различные влево, нужно хранить левый символ для каждой вершины или информацию о том, что она различна влево. Для поиска строки, ветвящейся влево, нужно промаркировать всё дерево. Сделать это можно при помощи обхода в глубину. Начиная с корня, спускаясь вниз, для листов левый символ уже известен — при добавление нового суффикса в дерево записываем левый символ для него в лист, для вершины $v$ запустим проверку:

• если среди левых детей $v$ есть хотя бы один, удовлетворяющий свойству различности влево, то обозначаем $v$ как различную влево вершину (в суффиксном дереве свойство различности влево передаётся от детей к родителю — строка соответствующая вершине $v$ и строка соответствующая ребёнку $v$ начинаются с одного и того же символа),
• если среди левых символов детей $v$ нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей:
  • если все левые символ детей $v$ одинаковы и эквивалентны $x$, то записываем в $v$ этот символ $x$,
  • если не все левые символы детей $v$ эквивалентны, то записываем в $v$, что она различна влево.

Так как время проверки $v$ пропорционально числу детей, время работы всего алгоритма — $O(n)$.

Теперь несложно среди всех найденных строк найти строку максимальной длины (также этот алгоритм можно использовать для нахождения количества строк, ветвящихся влево и вправо).

Таким образом можно найти строку максимальной длины, ветвящуюся влево и вправо, за время $ST+O(n)$, где $ST$ — время построения суффиксного дерева.

См. также

• Суффиксный бор
• Суффиксный массив
• Алгоритм Укконена

Источники информации

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