Суффиксный бор

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

По определению, в суффиксном боре для строки $s$ (где $|s| = n$) содержатся все строки $s[1 \ldots n], \dotsc, s[n \ldots n]$. Заметим, что если в суффиксном боре находится строка $s[i \ldots n]$, то все её префиксы $s[i \ldots j]$ ($i \leqslant j \leqslant n$) уже содержатся в боре.

Применение

Суффиксный бор можно использовать для поиска подстроки в строке $s$ тем же образом, что и для поиска строки в боре. Чтобы бор формально содержал все подстроки $s$, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке $\varepsilon$.

Суффиксный бор для строки $abbc$

Свойства

Суффиксный бор для строки «aaabbb»

Суффиксный бор для строки $s$:

• можно использовать для поиска образца $p$ в строке $s$ за время $O(|p|)$,
• можно построить за время $O(n^2)$, последовательно добавив все суффиксы $s$,
• имеет порядка $n^2$ вершин в худшем случае. Например, для строки $a^n b^n$ суффиксный бор будет содержать:

$1$ корневую вершину,

$n$ вершин для суффикса $b^n$,

$n$ вершин для подстроки $a^n$, у каждой по $n$ вершин для соответствующего суффикса $b^n$.

• итого $1 + 2n + n^2 = (n+1)^2 = \theta(n^2)$ вершин.

Реализация

Зададим бор его корнем:

struct Trie:
   Node root

По каждому символу будем хранить переход в соответствующую вершину:

struct Node:
   map<char, Node> children

При добавлении узла будем идти вниз по сыновьям и добавлять их, если необходимо:

function add(s : string):
   Node current = root
   for c in s
      if current.children[c] == [math]\varnothing[/math]
         current.children[c] = Node()
      current = current.children[c]

Чтобы построить суффиксный бор для некоторой строки, последовательно добавим в пустой бор все её суффиксы:

function build(s : string):
   root = Node()
   int n = s.size
   for i = 0 to n - 1
      add(s[i..n])

Оценки использования памяти

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

См. также

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

Источники информации

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