Просмотр исходного текста страницы Суффиксный бор

'''Суффиксный бор''' (англ. ''suffix trie'') — [[бор]], содержащий все суффиксы данной строки.

По определению, в суффиксном боре для строки <tex>s</tex> (где <tex>|s| = n</tex>) содержатся все строки <tex>s[1 \mathinner{\ldotp\ldotp} n], \dotsc, s[n \mathinner{\ldotp\ldotp} n]</tex>. Заметим, что если в суффиксном боре находится строка <tex>s[i \mathinner{\ldotp\ldotp} n]</tex>, то все её префиксы <tex>s[i \mathinner{\ldotp\ldotp} j]</tex> (<tex>i \leqslant j \leqslant n</tex>) уже содержатся в боре. 
==Применение==
Суффиксный бор можно использовать для поиска подстроки в строке <tex>s</tex> тем же образом, что и для [[Бор#Поиск строки в бору|поиска строки в боре]]. Чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>.
[[Файл:Syffix_trie_1.png|500px|thumb|center|Суффиксный бор для строки <tex>abbc</tex>]]

=== Свойства ===
[[Файл:aaabbb-suftrie.png|мини|400px|Суффиксный бор для строки «aaabbb»]]
Суффиксный бор для строки <tex>s</tex>:
* можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(|p|)</tex>,
* можно построить за время <tex>O(n^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>,
* имеет порядка <tex>n^2</tex> вершин в худшем случае. Например, для строки <tex>a^n b^n</tex> суффиксный бор будет содержать:
: <tex>1</tex> корневую вершину,
: <tex>n</tex> вершин для суффикса <tex>b^n</tex>,
: <tex>n</tex> вершин для подстроки <tex>a^n</tex>, у каждой по <tex>n</tex> вершин для соответствующего суффикса <tex>b^n</tex>.
<ul style="list-style: none;"><li>итого <tex>1 + 2n + n^2 = (n+1)^2 = \theta(n^2)</tex> вершин.</ul>

=== Реализация ===
Зададим бор его корнем:
<code style="display: inline-block">
 '''struct''' Trie:
    '''Node''' root
</code>
По каждому символу будем хранить переход в соответствующую вершину:
<code style="display: inline-block">
 '''struct''' Node:
    '''map<char, Node>''' children
</code>
При добавлении узла будем идти вниз по сыновьям и добавлять их, если необходимо:
<code style="display: inline-block">
 '''function''' add(s : '''string'''):
    '''Node''' current = root
    '''for''' c '''in''' s
       '''if''' current.children[c] == <tex>\varnothing</tex>
          current.children[c] = Node()
       current = current.children[c]
</code>
Чтобы построить суффиксный бор для некоторой строки, последовательно добавим в пустой бор все её суффиксы:
<code style="display: inline-block">
 '''function''' build(s : '''string'''):
    root = Node()
    '''int''' n = s.size
    '''for''' i = 0 '''to''' n - 1
       add(s[i..n])
</code>

=== Оценки использования памяти ===
Пусть мы построили суффиксный бор для строки <tex>s \in \Sigma^*</tex> (<tex>|s| = n</tex>). Из третьего свойства следует, что если хранить переходы суффиксного бора  из каждой вершины как массив размера <tex>|\Sigma|</tex> (по каждому символу — переход), то потребуется <tex>O(n^2 |\Sigma|)</tex> памяти.
Однако, заметим, что число ветвлений в не превышает числа листьев, что, в свою очередь, не превышает количества суффиксов. Количество суффиксов  — <tex>n</tex>, а значит число вершин, из которых ведет больше одного перехода, <tex>O(n)</tex>. Поэтому, если в неветвящихся вершинах хранить только символ перехода и ребенка, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].

==См. также==
* [[Сжатое суффиксное дерево]]

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

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