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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Применение: переместил картинку вправо для пущей компактности)
(Вернул картинку обратно в середину)
Строка 3: Строка 3:
 
По определению, в суффиксном боре для строки <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| = 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>) уже содержатся в боре.  
 
==Применение==
 
==Применение==
[[Файл:Syffix_trie_1.png|500px|thumb|Суффиксный бор для строки <tex>abbc</tex>]]
+
[[Файл:Syffix_trie_1.png|500px|thumb|center|Суффиксный бор для строки <tex>abbc</tex>]]
 
Суффиксный бор можно использовать для поиска подстроки в строке <tex>s</tex> тем же образом, что и для [[Бор#Поиск строки в бору|поиска строки в боре]]. Чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>.
 
Суффиксный бор можно использовать для поиска подстроки в строке <tex>s</tex> тем же образом, что и для [[Бор#Поиск строки в бору|поиска строки в боре]]. Чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>.
<br clear="all">
 
  
 
==Свойства==
 
==Свойства==

Версия 15:44, 9 июня 2015

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

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

Применение

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

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

Свойства

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

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

  • можно использовать для поиска образца [math]p[/math] в строке [math]s[/math] за время [math]O(|p|)[/math],
  • можно построить за время [math]O(n^2)[/math], последовательно добавив все суффиксы [math]s[/math],
  • имеет порядка [math]n^2[/math] вершин в худшем случае. Например, для строки [math]a^n b^n[/math] суффиксный бор будет содержать:
    • 1 корневую вершину,
    • n вершин для суффикса [math]b^n[/math],
    • n вершин для подстроки [math]a^n[/math], у каждой по n вершин для соответствующего суффикса [math]b^n[/math].
    итого [math]1 + 2n + n^2 = (n+1)^2 = O(n^2)[/math] вершин.


Реализация

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 = 1 to n
    add(s[i..n])

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

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

См. также

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

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