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

Суффиксный бор — удобная структура данных для поиска подстроки в строке, но она занимает много места в памяти. Рассмотрим в боре все пути от [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]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]l, r[/math] ее начала и конца в исходной строке, а не хранят саму строку. Представим теперь дерево как массив [math][|V|*|\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] памяти.

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

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

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 с: ил.