Редактирование: Суффиксный бор

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Суффиксный бор''' (англ. ''suffix trie'') [[бор]], содержащий все суффиксы данной строки.
+
[[Файл:Suffix_trie.png|thumb|right|Суффиксный бор для строки <tex>abbc</tex>]]
 +
'''Суффиксный бор''' (англ. ''suffix trie'') {{---}} [[бор]], содержащий все суффиксы данной строки.
  
По определению, в суффиксном боре для строки <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>\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</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>).  
[[Файл:Syffix_trie_1.png|500px|thumb|center|Суффиксный бор для строки <tex>abbc</tex>]]
+
Для поиска подстроки p в суффиксном боре нужно искать совпадения для символов из p вдоль единственного пути в боре до тех пор, пока либо p не исчерпается, либо дальнейшее совпадение будет невозможным. Если p исчерпалось, то подстрока найдена за <tex>O(p)</tex>, если дальнейшее совпадение невозможно, то p нет в суффиксном дереве.
 
+
==Свойства==
=== Свойства ===
 
[[Файл: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(\lvert p\rvert)</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>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>
 
  
=== Реализация ===
+
== Реализация ==
Зададим бор его корнем:
+
  '''struct Trie'''
<code style="display: inline-block">
+
     int [length^2][alphabet] trie
  '''struct''' Trie:
+
    number <tex> \leftarrow 1</tex>
    '''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>
 
  
=== Оценки использования памяти ===
+
'''Add'''(i, j)
Пусть мы построили суффиксный бор для строки <tex>s \in \Sigma^*</tex> (<tex>|s| = n</tex>). Из третьего свойства следует, что если хранить переходы суффиксного бора  из каждой вершины как массив размера <tex>|\Sigma|</tex> (по каждому символу — переход), то потребуется <tex>O(n^2 |\Sigma|)</tex> памяти.
+
  current <tex>\leftarrow</tex> 0
Однако, заметим, что число ветвлений в не превышает числа листьев, что, в свою очередь, не превышает количества суффиксов. Количество суффиксов  — <tex>n</tex>, а значит число вершин, из которых ведет больше одного перехода, <tex>O(n)</tex>. Поэтому, если в неветвящихся вершинах хранить только символ перехода и ребенка, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].
+
  '''for''' (char c <tex>\in</tex> s[i, j])
 +
    if (trie[current][c] <tex>\neq  </tex> -1)
 +
      trie[current][c] <tex> \leftarrow</tex> number
 +
      number++;
 +
    current <tex>\leftarrow</tex> trie[current][c]
  
==См. также==
+
'''Build'''(String  s)
* [[Сжатое суффиксное дерево]]
+
  '''for'''(int i = 0, i < n, i++)
 +
    Add(i, n)
  
== Источники информации ==
+
==Хранение в памяти==
*''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
+
Пусть <tex>s \in \Sigma^*</tex>, <tex>\lvert s\rvert = n</tex>. Из третьего свойства следует, что для хранения суффиксного бора в худшем случае потребуется <tex>O(n^2 |\Sigma|)</tex> памяти. Например, если строка состоит из всех символов алфавита.  
 +
Количество разветвлений будет равно количеству суффиксов, так как каждый лист соответствует единственному суффиксу. Количество суффиксов <tex>n</tex>. Тогда количество вершин, в которых больше одного перехода будет <tex>O(n)</tex>. Поэтому, если вместо массива переходов для вершин хранить map<char, integer>, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Словарные структуры данных]]
 
[[Категория:Словарные структуры данных]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)