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

2012-06-01T11:33:57Z

178.178.22.166: /* Определение */ small fixup

[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она занимает много места в памяти. Рассмотрим в боре все пути от <tex>u</tex> до <tex>v</tex>, в которых у каждой вершины только один сын. Такой путь можно сжать до ребра <tex>u v</tex>, записав на нем все встречающиеся на пути символы, которые являются подстрокой исходной строки. Для хранения ее на ребре обычно используют индексы <tex>l, r</tex> начала и конца. Получилось '''сжатое суффиксное дерево'''.

==Определение==
{{Определение
|definition =
'''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где <tex>|s| = n</tex>) {{---}} дерево с <tex>n</tex> листьями, каждая внутренняя вершина которого имеет не меньше двух детей, а каждое ребро помечено непустой подстрокой строки <tex>s</tex>. Два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа.
}}

Сжатое суффиксное дерево, как и бор, содержит все суффиксы строки <tex>s</tex>, причем каждый суффикс заканчивается точно в листе и нигде кроме него. [[Файл:Suffix_tree_3.png|thumb|right|Суффиксное дерево для строки <tex>xabxa</tex> с защитным символом]]
Рассмотрим дерево для строки <tex>xabxa</tex>. У него суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки <tex>s</tex> добавляют символ, не входящий в исходный алфавит: '''''защитный''''' символ. Как правило, это <tex>\$</tex>. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе.

Далее <tex>n</tex> - длина строки <tex>s</tex> с защитным символом.

==Количество вершин==
По определению, в суффиксном дереве содержится <tex>n</tex> листьев. Рассмотрим количество внутренних вершин такого дерева.

{{Лемма
|statement=
Количество внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества листьев.
|proof=
Докажем лемму индукцией по количеству листьев <tex>n</tex>.

'''База'''

При <tex>n = 2</tex> в дереве одна внутренняя вершина - верно.

'''Переход''' <tex>n \rightarrow n + 1</tex>

Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка - листья. Рассмотрим возможные случаи:

1) У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем количество внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, значит, для исходного дерева лемма верна.

2) У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n</tex> листьями, количество внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее <tex>n</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n + 1</tex>.
}}

==Занимаемая память==
Представим дерево как массив <tex>[|V|*|\Sigma|]</tex>, где <tex>|V|</tex> {{---}} количество вершин в дереве, <tex>|\Sigma|</tex> - мощность алфавита. Для любого суффиксного дерева верна предыдущая лемма (у каждой вершины по определению не менее двух детей), значит, <tex>|V| = O(2*n)</tex>. Каждая <tex>[i][j]</tex> ячейка содержит информацию о том, в какую вершину ведет <tex>i-</tex>ое ребро по <tex>j-</tex>ому символу и индексы <tex>l, r</tex>. Итак, дерево занимает <tex>O(n*|\Sigma|)</tex> памяти.

==Построение суффиксного дерева==
Рассмотрим наивный алгоритм построения суффиксного дерева:
'''for''' <tex> i \leftarrow 0 </tex> '''to''' <tex> n </tex> '''do''' //для каждого символа строки
insert(<tex>i, n</tex>) //добавляем суффикс, начинающийся с него

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

Этот алгоритм работает за время <tex>O(n^2)</tex>, однако [[Алгоритм Укконена| алгоритм Укконена]] позволяет построить сжатое суффиксное дерево за <tex>O(n)</tex>.

==Использование сжатого суффиксного дерева==
Суффиксное дерево позволяет за линейное время найти:
* Количество различных подстрок данной строки
* Наибольшую общую подстроку двух строк
* [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (longest common prefix) исходной строки

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

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Словарные структуры данных ]]

Викиконспекты - Вклад участника [ru]

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