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

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

Определение

Суффиксное дерево (сжатое суффиксное дерево) [math]T[/math] для строки [math]s[/math] (где [math]|s| = n[/math]) — дерево с [math]n[/math] листьями, каждая внутренняя вершина которого имеет не меньше двух детей, а каждое ребро помечено непустой подстрокой строки [math]s[/math] и символом ее начала. Два ребра, выходящие из одной вершины, не могут иметь одинаковых символьных меток. Такое дерево, как и суффиксный бор, содержит все суффиксы строки [math]s[/math], причем каждый суффикс заканчивается точно в листе и нигде кроме него.

Защитный символ

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

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

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

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

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

[math]\triangleleft[/math]

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

Так как любое суффиксное дерево удовлетворяет условиям леммы (у каждой вершины не менее двух детей), то количество внутренних вершин в нем меньше количества листьев, равного [math]n[/math]. Значит, для его хранения требуется [math]O(n|\Sigma|)[/math] памяти.

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

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

for [math] i \leftarrow 0 [/math] to [math] n [/math] do //для каждого символа строки
    insert([math]i, n[/math]) //добавляем суффикс, начинающийся с него

insert(l,r)
    [math] cur \leftarrow root [/math] //инициализируем текущую вершину корнем
    while ([math] i \lt  r [/math])
         if [math] go[cur][s[i]].v = 0 [/math] //если мы не можем пойти из вершины по символу [math] i [/math]
              create_vertex([math]cur, new V, i, r, s[i][/math]) //создаем новую вершину
         else
              [math]start \leftarrow go[cur][s[i]].l [/math]
              [math]finish \leftarrow go[cur][s[i]].r [/math]
              for [math] j = start [/math] to [math] finish [/math] //для каждого символа на ребре из текущей вершины
                   if [math]s[i+j-start] \lt \gt s[j] [/math] //если нашли не совпадающий символ
                        разбить ребро
                        break
              if ребро не разбивали
                   [math]cur \leftarrow go[cur][s[i]].v [/math] //переходим по ребру
                   [math]i \leftarrow i + finish - start [/math] //двигаемся по суффиксу на длину подстроки, записанной на ребре

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

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

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

• Количество различных подстрок данной строки
• Наибольшую общую подстроку двух строк
• Суффиксный массив и массив [math]lcp[/math] (longest common prefix) исходной строки

Источники

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