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

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

Определение

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

Суффиксное дерево (сжатое суффиксное дерево) [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] листами, у которой два ребенка — листья. Рассмотрим возможные случаи: 1) У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с [math]n[/math] листьями, причем в нем количество внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее [math]n[/math] внутренних вершин, а, значит, и для исходного дерева лемма верна. 2) У нее ровно два ребенка. Отрежем их, получим дерево с [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][i][j][/math] ячейка содержит информацию о том, в какую вершину ведет ребро из [math]i[/math]-ой вершины по [math]j[/math]-ому символу и индексы [math]l, r[/math] начала и конца подстроки, записанной на данном переходе. Итак, дерево занимает [math]O(n|\Sigma|)[/math] памяти.

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

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

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

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

insert(l, 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] [math] \neq [/math] 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

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

Этот алгоритм работает за время [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].

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

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

• Количество различных подстрок данной строки
• Наибольшую общую подстроку двух строк
• Суффиксный массив и массив [math]lcp[/math] (longest common prefix) исходной строки
• Строку максимальной длины, ветвящуюся влево и вправо за [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]a[/math], соответствующая пути к вершине [math]v[/math], является ветвящейся вправо и влево тогда и только тогда, когда вершина [math]v[/math] различна влево и счётчик вершины [math]\gt 1[/math].

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

[math]\triangleright[/math]

[math]\Leftarrow[/math] Предположим, что [math]v[/math] различна влево. Значит, что существуют подстроки [math]cs[/math] и [math]ds[/math]. Пусть за первой подстрокой следует символ [math]p[/math]. Если за второй подстрокой следует символ, [math]\ne p[/math], то [math]s[/math] — строка, ветвящаяся вправо и влево. Так как у [math]v[/math] есть два различных ребёнка, которые начинаются с различных символов [math]p,q \ne \$[/math], строка является ветвящейся вправо. [math]\Rightarrow[/math] Пусть строка [math]s[/math] является ветвящейся вправо и влево. Тогда существуют подстроки [math]csa[/math] и [math]dsb[/math]. В суффиксном дереве существует вершина [math]v[/math] соответствующая строке [math]s[/math] (так как есть как минимум два суффикса, начинающиеся со строки [math]s[/math]). У вершины [math]v[/math], есть как минимум два ребёнка, которые начинаются с символов [math]a[/math] и [math]b[/math] [math]\Rightarrow[/math] счётчик вершины [math]\gt 2[/math]. Так же у вершины [math]v[/math], есть как минимум два ребёнка, у которых левый символ [math]c[/math] и [math]d[/math], значит вершина [math]v[/math] различна влево по определению.

[math]\triangleleft[/math]

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

Чтобы найти вершины различные влево будем хранить левый символ для каждой вершины, пусть он будет [math]\$[/math], если вершина различна влево. Чтобы промаркировать всё дерево, нужно записать левые символы для листов, а затем подниматься вверх по дереву. Для каждой вершины [math]v[/math] будем запускать проверку:

• Если среди левых символов детей [math]v[/math] есть хотя бы один [math]\$[/math], то запишем в [math]v[/math] [math]\$[/math] и закончим проверку.
• Если среди левых символов детей [math]v[/math] нет ни одного [math]\$[/math], то проверим на совпадение левые символы детей:
  • Если все левые символ детей [math]v[/math] одинаковы и эквивалентны [math]x[/math], то запишем в [math]v[/math] [math]x[/math].
  • Если не все левые символы детей [math]v[/math], то запишем в [math]v[/math] [math]\$[/math] — вершина различна влево.

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

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

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

См. также

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

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

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