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

Определение:

Пусть дана строка [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]i[/math] конкатенация меток дуг на пути от корня к листу [math]i[/math] в точности составляет суффикс строки [math]s[/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]O(n|\Sigma|)[/math] памяти.

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

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

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

Источники

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