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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Хранение в памяти)
м
(не показано 38 промежуточных версий 9 участников)
Строка 1: Строка 1:
[[Файл:Suffix_trie.png|thumb|right|Суффиксный бор для строки <tex>abbc</tex>]]
+
'''Суффиксный бор''' (англ. ''suffix trie'') [[бор]], содержащий все суффиксы данной строки.
'''Суффиксный бор''' (англ. ''suffix trie'') {{---}} [[бор]], содержащий все суффиксы данной строки.
 
  
По определению, в суффиксном боре для строки <tex>s</tex> (где <tex>\lvert s\rvert=n</tex>) содержатся все строки <tex>s[1..n], ..., s[n..n]</tex>. Сделаем следующее наблюдение: если в суффиксном боре находится строка <tex>s[i..n]</tex>, то все ее префиксы <tex>s[i..j], i \le j \le n</tex> уже содержатся в нашем боре. Значит, суффиксный бор можно использовать для поиска всех подстрок строки <tex>s</tex> (чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</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>]]
  
==Свойства==
+
=== Свойства ===
 +
[[Файл:aaabbb-suftrie.png|мини|400px|Суффиксный бор для строки «aaabbb»]]
 
Суффиксный бор для строки <tex>s</tex>:
 
Суффиксный бор для строки <tex>s</tex>:
* Можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(\lvert p\rvert)</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>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>
  
== Реализация ==
+
=== Реализация ===
  <tex>int </tex> <tex>[length ^ 2][alphabet] </tex> <tex> table</tex>  
+
Зададим бор его корнем:
  <tex>int </tex> <tex> number = 1 </tex>
+
<code style="display: inline-block">
'''<tex>\text{Add}(int </tex> <tex> i, j)</tex>'''
+
'''struct''' Trie:
     <tex> int </tex> <tex> current = 0 </tex>
+
    '''Node''' root
     <tex>for</tex> (<tex>char </tex> <tex> c \in s[i, j])</tex>
+
</code>
        <tex> if (table[current][c] \neq -1) </tex> //проверка есть ли ребро с текущим символом
+
По каждому символу будем хранить переход в соответствующую вершину:
        <tex> table[current][c] = number </tex>
+
<code style="display: inline-block">
        <tex> number++; </tex>
+
'''struct''' Node:
    <tex> current = table[current][c]</tex>
+
    '''map<char, Node>''' children
'''<tex>\text{Build}</tex> <tex>(String  </tex> <tex> s)</tex>
+
</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>\lvert s\rvert = n</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> памяти, является [[сжатое суффиксное дерево]].
{| border="1" cellpadding="3" cellspacing="0" style="text-align:center" width=20%
+
 
!style="background:#f2f2f2"|№
+
==См. также==
!style="background:#f2f2f2"|a
+
* [[Сжатое суффиксное дерево]]
!style="background:#f2f2f2"|b
+
 
!style="background:#f2f2f2"|c
+
== Источники информации ==
|-
+
*''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
|style="background:#f9f9f9"|0
 
|style="background:#f9f9f9"|1
 
|style="background:#f9f9f9"|5
 
|style="background:#f9f9f9"|9
 
|-
 
|style="background:#f9f9f9"|1
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|2
 
|style="background:#f9f9f9"|-1
 
|-
 
|style="background:#f9f9f9"|2
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|3
 
|style="background:#f9f9f9"|-1
 
|-
 
|style="background:#f9f9f9"|3
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|4
 
|-
 
|style="background:#f9f9f9"|4
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|-1
 
|-
 
|style="background:#f9f9f9"|5
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|6
 
|style="background:#f9f9f9"|8
 
|-
 
|style="background:#f9f9f9"|6
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|7
 
|-
 
|style="background:#f9f9f9"|7
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|-1
 
|style="background:#f9f9f9"|-1
 
|-
 
|}
 
Если не хранить массив переходов по символам для вершин, где такой переход единственный, то можно получить оценку <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 с: ил.