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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

struct Vertex:  // Структура, содержащая информацию о вершине 
    int l // индекс начала подстроки 
    int r // индекс конца подстроки 
    int v // индекс текущей позиции 
   
go[0] = new Vertex // массив из пустых Vertex (можно все поля положить -1), размер массива -- количество символов в алфавите 
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 and l + j - start < n      // для каждого символа на ребре из текущей вершины
                if (s[l + j - start] != s[j]) // если нашли не совпадающий символ
                    // создаем вершину на ребре
                    old = go[cur][s[l]]
                    createVertex(cur, l, j)
                    go[count][s[j]].v = old
                    go[count][s[j]].l = j
                    go[count][s[j]].r = 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] = new 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]\mathtt {parent}[/math], стек детей в лексикографическом порядке ребер [math]\mathtt{children}[/math], глубину вершины в символах от корня [math]\mathtt{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]\mathtt{maxDepth}[/math].

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

void 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]\mathtt{length}[/math], глубина листа в символах [math]\mathtt{depth}[/math], тогда номер суффикса [math]\mathtt{i = length - depth}[/math].

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

int curPos = 0
Node minNode = root
// Для заполнения нужно вызвать dfs(root) 
void 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] на