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

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

Количество вершин

В сжатом суффиксном дереве содержится [math]n[/math] листьев, т.к. каждый суффикс строки [math]s[/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]O(|V||\Sigma|)[/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 с: ил.