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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства: более удачный пример для O(n^2) вершин; элементы списка со строчной буквы)
м
 
(не показано 7 промежуточных версий 3 участников)
Строка 1: Строка 1:
'''Суффиксный бор''' (англ. ''suffix trie'') {{---}} [[бор]], содержащий все суффиксы данной строки.
+
'''Суффиксный бор''' (англ. ''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| = n</tex>) содержатся все строки <tex>s[1 \ldots n], \dotsc, s[n \ldots n]</tex>. Заметим, что если в суффиксном боре находится строка <tex>s[i \ldots n]</tex>, то все её префиксы <tex>s[i \ldots 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>]]
 
[[Файл:Syffix_trie_1.png|500px|thumb|center|Суффиксный бор для строки <tex>abbc</tex>]]
Суффиксный бор можно использовать для поиска подстроки в строке <tex>s</tex> тем же образом, что и для [[Бор#Поиск строки в бору|поиска строки в боре]]. Чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>.
 
  
==Свойства==
+
=== Свойства ===
[[Файл:aaabbb-suftrie.png|мини|500px|Суффиксный бор для строки «aaabbb»]]
+
[[Файл:aaabbb-suftrie.png|мини|400px|Суффиксный бор для строки «aaabbb»]]
 
Суффиксный бор для строки <tex>s</tex>:
 
Суффиксный бор для строки <tex>s</tex>:
 
* можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(|p|)</tex>,
 
* можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(|p|)</tex>,
 
* можно построить за время <tex>O(n^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>,
 
* можно построить за время <tex>O(n^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>,
* имеет порядка <tex>n^2</tex> вершин в худшем случае. Например, для строки <tex>a^n b^n</tex> суффиксный бор будет содержать:<!--
+
* имеет порядка <tex>n^2</tex> вершин в худшем случае. Например, для строки <tex>a^n b^n</tex> суффиксный бор будет содержать:
--><ul><li>1 корневую вершину,<!--
+
: <tex>1</tex> корневую вершину,
--><li> n вершин для суффикса <tex>b^n</tex>,<!--
+
: <tex>n</tex> вершин для суффикса <tex>b^n</tex>,
--><li> n вершин для подстроки <tex>a^n</tex>, у каждой по n вершин для соответствующего суффикса <tex>b^n</tex>.</ul><!-- Вики-разметка не может в продолжение элемента списка после вложенного списка — очень жаль.
+
: <tex>n</tex> вершин для подстроки <tex>a^n</tex>, у каждой по <tex>n</tex> вершин для соответствующего суффикса <tex>b^n</tex>.
-->итого <tex>1 + 2n + n^2 = (n+1)^2 = O(n^2)</tex> вершин.
+
<ul style="list-style: none;"><li>итого <tex>1 + 2n + n^2 = (n+1)^2 = \theta(n^2)</tex> вершин.</ul>
 
 
== Реализация ==
 
'''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] == <tex>\varnothing</tex>
 
      current.children[c] = Node()
 
    current = current.children[c]
 
  
  '''function''' build(s : '''string''')
+
=== Реализация ===
  root = Node()
+
Зададим бор его корнем:
  '''int''' n = s.size
+
<code style="display: inline-block">
  '''for''' i = 1 '''to''' n
+
'''struct''' Trie:
    add(s[i..n])
+
    '''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>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> памяти, является [[сжатое суффиксное дерево]].
 
Однако, заметим, что число ветвлений в не превышает числа листьев, что, в свою очередь, не превышает количества суффиксов. Количество суффиксов  — <tex>n</tex>, а значит число вершин, из которых ведет больше одного перехода, <tex>O(n)</tex>. Поэтому, если в неветвящихся вершинах хранить только символ перехода и ребенка, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].

Текущая версия на 20:41, 22 марта 2017

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

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

Применение[править]

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

Суффиксный бор для строки [math]abbc[/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] суффиксный бор будет содержать:
[math]1[/math] корневую вершину,
[math]n[/math] вершин для суффикса [math]b^n[/math],
[math]n[/math] вершин для подстроки [math]a^n[/math], у каждой по [math]n[/math] вершин для соответствующего суффикса [math]b^n[/math].
  • итого [math]1 + 2n + n^2 = (n+1)^2 = \theta(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 = 0 to n - 1
      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 с: ил.