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

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

Определение

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

Суффиксное дерево (сжатое суффиксное дерево) [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] = new 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  then //если мы не можем пойти из вершины по символу [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] then //если нашли не совпадающий символ
                    //создаем вершину на ребре
                    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 then
                cur = go[cur][s[l]].v //переходим по ребру
                l = l + finish - start //двигаемся по суффиксу на длину подстроки, записанной на ребре
            else
                break

createVertex(cur, l, 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]lcp[/math] (longest common prefix) исходной строки

Источники

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

См. также

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