Сжатое суффиксное дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Количество внутренних вершин)
Строка 12: Строка 12:
  
 
==Количество внутренних вершин==
 
==Количество внутренних вершин==
 +
{{Лемма
 +
|statement=
 +
Количество внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества листьев
 +
|proof=
 +
Докажем лемму индукцией по количеству листьев <tex>n</tex>.
 +
 +
''База''
 +
 +
При <tex>n = 2</tex> в дереве одна внутренняя вершина - верно.
 +
 +
''Переход'' <tex>n \rightarrow n + 1</tex>
 +
 +
Рассмотрим все вершины, у которых хотя бы один из детей - лист.
 +
 +
Если среди них есть вершина, у которой более двух детей, отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, удовлетворяющее условию леммы, в котором количество внутренних вершин равно количеству внутренних вершин в исходном дереве. Тогда, по индукционному предположению, у полученного дерева менее <tex>n</tex> внутренних вершин, значит в исходном дереве количество внутренних вершин меньше количества листьев.
 +
 +
Иначе среди этих вершин есть вершина, у которой оба ребенка - листья. Отрежем оба этих листа, получим дерево с <tex>n</tex> листьями, удовлетворяющее условию леммы, количество внутренних вершин которого на <tex>1</tex> меньше количества внутренних вершин в исходном дереве. Тогда, по индукционному предположению, у полученного дерева менее <tex>n</tex> внутренних вершин, значит в исходном дереве количество внутренних вершин меньше <tex>n + 1</tex>.
 +
}}
 +
 +
 +
Так как суффиксное дерево удовлетворяет условиям леммы, то количество внутренних вершин в нем меньше количества листьев, то есть меньше длины строки.
  
 
==Хранение в памяти==
 
==Хранение в памяти==

Версия 04:22, 17 мая 2011

Определение:
Пусть дана строка [math]s[/math], [math]|s| = n[/math]. Суффиксное дерево (сжатое суффиксное дерево) [math]T[/math] для строки [math]s[/math] - ориентированное дерево с корнем, имеющее ровно [math]n[/math] листьев, занумерованных от [math]1[/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]xabxa[/math] с защитным символом

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

Связь с суффиксным бором

Пусть [math]P[/math] - суффиксный бор строки [math]s[/math]. Тогда сжатое суффиксное дерево [math]T[/math] может быть получено из [math]P[/math] слиянием каждого пути из неветвящихся вершин в одну дугу.

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

Лемма:
Количество внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества листьев
Доказательство:
[math]\triangleright[/math]

Докажем лемму индукцией по количеству листьев [math]n[/math].

База

При [math]n = 2[/math] в дереве одна внутренняя вершина - верно.

Переход [math]n \rightarrow 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(n|\Sigma|)[/math] памяти.

Использование

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

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

Источники

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