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

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

Определение

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

Суффиксное дерево (сжатое суффиксное дерево) [math]T[/math] для строки [math]s[/math] (где [math]|s| = n[/math]) — дерево с [math]n[/math] листьями, обладающее следующими свойствами:

• каждая внутренняя вершина дерева имеет не меньше двух детей;
• каждое ребро помечено непустой подстрокой строки [math]s[/math];
• никакие два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа;
• дерево должно содержать все суффиксы строки [math]s[/math], причем каждый суффикс заканчивается точно в листе и нигде кроме него.

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

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

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

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

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

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

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

go[0] = Vertex() // 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)         // если мы не можем пойти из вершины по символу [math] l [/math]
            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

Node Vertex():
    top = new Node
    return top

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

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

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

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

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

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

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

В вершинах дерева [math]Node[/math] мы будем хранить предка [math]parent[/math], стек детей в лексикографическом порядке ребер [math]children[/math], глубину вершины в символах от корня [math]depth[/math]. Соответственно, конструктор вершины имеет вид 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

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

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

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

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

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

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

1. Количество различных подстрок данной строки.
2. Наибольшую общую подстроку двух строк.
3. Суффиксный массив и массив [math]lcp[/math] (longest common prefix) исходной строки.
4. Строку максимальной длины, ветвящуюся влево и вправо за [math]ST + O(n)[/math].

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

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

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

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

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)

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

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

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

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

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

Суффиксное дерево для строки [math]aabcabd[/math]

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

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

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

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

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

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

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

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

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

Случай 1. Если среди левых детей [math]v[/math] есть хотя бы один, удовлетворяющий свойству различности влево, то обозначаем [math]v[/math] как различную влево вершину (в суффиксном дереве свойство различности влево передаётся от детей к родителю — строка соответствующая вершине [math]v[/math] и строка соответствующая ребёнку [math]v[/math] начинаются с одного и того же символа).

Случай 2. Если среди левых символов детей [math]v[/math] нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей.

Случай 2.1. Если все левые символ детей [math]v[/math] одинаковы и эквивалентны [math]x[/math], то записываем в [math]v[/math] этот символ [math]x[/math].

Случай 2.2. Если не все левые символы детей [math]v[/math] эквивалентны, то записываем в [math]v[/math], что она различна влево.

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

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

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

См. также

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

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

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