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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition= Пусть дана строка <tex>S</tex>, <tex>|S| = m</tex>. Суффиксное дерево <tex>T</tex> для стр…»)
 
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть дана строка <tex>S</tex>, <tex>|S| = m</tex>. Суффиксное дерево <tex>T</tex> для строки <tex>S</tex> - ориентированное дерево с корнем, имеющее ровно <tex>m</tex> листьев, занумерованных от <tex>1</tex> до <tex>m</tex>. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки <tex>S</tex>. Никакие две дуги не могут иметь пометок, начинающихся с одного и того же символа.
+
Пусть дана строка <tex>s</tex>, <tex>|s| = m</tex>. Суффиксное дерево <tex>T</tex> для строки <tex>s</tex> - ориентированное дерево с корнем, имеющее ровно <tex>m</tex> листьев, занумерованных от <tex>1</tex> до <tex>m</tex>. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки <tex>s</tex>. Никакие две дуги не могут иметь пометок, начинающихся с одного и того же символа.
 
}}
 
}}
Главная особенность суффиксного дерева заключается в том, что для каждого листа <tex>i</tex> конкатенация меток дуг на пути от корня к листу <tex>i</tex> в точности составляет суффикс строки <tex>S</tex>, который начинается в позиции <tex>i</tex>, то есть <tex>S[i..m]</tex>.
+
Главная особенность суффиксного дерева заключается в том, что для каждого листа <tex>i</tex> конкатенация меток дуг на пути от корня к листу <tex>i</tex> в точности составляет суффикс строки <tex>s</tex>, который начинается в позиции <tex>i</tex>, то есть <tex>s[i..m]</tex>.
 
+
==Существование сжатого суффиксного дерева==
Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки <tex>S</tex>. Если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки <tex>xabxa</tex> суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>. Во избежание этого в конце строки <tex>S</tex> добавляется символ, не входящий в исходный алфавит. Такой символ называется '''''защитным'''''. Как правило в качестве защитного символа используется <tex>\$</tex>.
+
[[Файл:Suffix_tree.jpg|thumb|right|Суффиксный бор для строки <tex>xabxa</tex> с защитным символом]]
 +
Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки <tex>s</tex>. Если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки <tex>xabxa</tex> суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>. Во избежание этого в конце строки <tex>s</tex> добавляется символ, не входящий в исходный алфавит. Такой символ называется '''''защитным'''''. Как правило в качестве защитного символа используется <tex>\$</tex>.
 +
==Связь с суффиксным бором==
 +
Пусть <tex>P</tex> - [[Суффиксный бор|суффиксный бор]] строки <tex>s</tex>. Тогда сжатое суффиксное дерево <tex>T</tex> может быть получено из <tex>P</tex> слиянием каждого пути из неветвящихся вершин в одну дугу.
 +
==Хранение в памяти==

Версия 05:55, 22 марта 2011

Определение:
Пусть дана строка [math]s[/math], [math]|s| = m[/math]. Суффиксное дерево [math]T[/math] для строки [math]s[/math] - ориентированное дерево с корнем, имеющее ровно [math]m[/math] листьев, занумерованных от [math]1[/math] до [math]m[/math]. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки [math]s[/math]. Никакие две дуги не могут иметь пометок, начинающихся с одного и того же символа.

Главная особенность суффиксного дерева заключается в том, что для каждого листа [math]i[/math] конкатенация меток дуг на пути от корня к листу [math]i[/math] в точности составляет суффикс строки [math]s[/math], который начинается в позиции [math]i[/math], то есть [math]s[i..m][/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] слиянием каждого пути из неветвящихся вершин в одну дугу.

Хранение в памяти