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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Хранение в памяти)
(Хранение в памяти)
Строка 73: Строка 73:
 
|-
 
|-
 
|}
 
|}
Если не хранить массив переходов по символам для вершин, где такой переход единственный, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].
+
Можно заметить, что количество разветвлений будет равно количеству суффиксов. Количество суффиксов <tex>n</tex>. Тогда количество строк, в которых больше одного перехода будет <tex>O(n)</tex>. Поэтому, если не хранить массив переходов для вершин, где такой переход единственный, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Словарные структуры данных]]
 
[[Категория:Словарные структуры данных]]

Версия 16:36, 17 апреля 2012

Суффиксный бор для строки [math]abbc[/math]

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

По определению, в суффиксном боре для строки [math]s[/math] (где [math]\lvert s\rvert=n[/math]) содержатся все строки [math]s[1..n], ..., s[n..n][/math]. Сделаем следующее наблюдение: если в суффиксном боре находится строка [math]s[i..n][/math], то все ее префиксы [math]s[i..j], i \le j \le n[/math] уже содержатся в нашем боре. Значит, суффиксный бор можно использовать для поиска всех подстрок строки [math]s[/math] (чтобы бор формально содержал все подстроки [math]s[/math], нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке [math]\varepsilon[/math]).

Свойства

Суффиксный бор для строки [math]s[/math]:

  • Можно использовать для поиска образца [math]p[/math] в строке [math]s[/math] за время [math]O(\lvert p\rvert)[/math].
  • Можно построить за время [math]O(n^2)[/math], последовательно добавив все суффиксы [math]s[/math].
  • Имеет порядка [math]n^2[/math] вершин.

Реализация

  [math]int [/math] [math][length ^ 2][alphabet] [/math] [math] table[/math] 
  [math]int [/math] [math] number = 1 [/math]

[math]\text{Add}(int [/math] [math] i, j)[/math]

   [math] int [/math] [math] current = 0 [/math]
   [math]for[/math] ([math]char [/math] [math] c \in s[i, j])[/math]
       [math] if (table[current][c] \neq -1) [/math] //проверка есть ли ребро с текущим символом
       [math] table[current][c] = number [/math]
       [math] number++; [/math]
    [math] current = table[current][c][/math]

[math]\text{Build}[/math] [math](String [/math] [math] s)[/math]

  добавляем все суффиксы.

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

Пусть [math]s \in \Sigma^*[/math], [math]\lvert s\rvert = n[/math]. Из третьего свойства следует, что для хранения суффиксного бора в худшем случае потребуется [math]O(n^2 |\Sigma|)[/math] памяти. При этом таблица для приведенной выше реализации выглядит так:

a b c
0 1 5 9
1 -1 2 -1
2 -1 3 -1
3 -1 -1 4
4 -1 -1 -1
5 -1 6 8
6 -1 -1 7
7 -1 -1 -1

Можно заметить, что количество разветвлений будет равно количеству суффиксов. Количество суффиксов [math]n[/math]. Тогда количество строк, в которых больше одного перехода будет [math]O(n)[/math]. Поэтому, если не хранить массив переходов для вершин, где такой переход единственный, то можно получить оценку [math]O(n^2 + n|\Sigma|)[/math]. Улучшением суффиксного бора, расходующим всего [math]O( n|\Sigma|)[/math] памяти, является сжатое суффиксное дерево.