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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
Строка 2: Строка 2:
 
'''Суффиксный бор''' (англ. ''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>\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>).
 +
Для поиска подстроки p в суффиксном боре нужно искать совпадения для символов из p вдоль единственного пути в боре до тех пор, пока либо p не исчерпается, либо дальнейшее совпадение будет невозможным. Если p исчерпалось, то подстрока найдена за <tex>O(p)</tex>, если дальнейшее совпадение невозможно, то p нет в суффиксном дереве.
 
==Свойства==
 
==Свойства==
 
Суффиксный бор для строки <tex>s</tex>:
 
Суффиксный бор для строки <tex>s</tex>:

Версия 00:04, 27 апреля 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]). Для поиска подстроки p в суффиксном боре нужно искать совпадения для символов из p вдоль единственного пути в боре до тех пор, пока либо p не исчерпается, либо дальнейшее совпадение будет невозможным. Если p исчерпалось, то подстрока найдена за [math]O(p)[/math], если дальнейшее совпадение невозможно, то p нет в суффиксном дереве.

Свойства

Суффиксный бор для строки [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] вершин.

Реализация

struct Trie
   int [length^2][alphabet] trie 
   number [math] \leftarrow 1[/math]
Add(i, j)
  current [math]\leftarrow[/math] 0 
  for (char c [math]\in[/math] s[i, j])
    if (trie[current][c] [math]\neq  [/math]  -1)
      trie[current][c] [math] \leftarrow[/math] number 
      number++; 
    current [math]\leftarrow[/math] trie[current][c]
Build(String  s)
  for(int i = 0, i < n, i++)
    Add(i, n)

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

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