Викиконспекты - Вклад участника [ru]

Суффиксный бор

2012-06-04T15:55:23Z

109.188.204.171: Отмена правки 23680 участника 109.188.204.171 (обсуждение)

[[Файл:Syffix_trie_1.png|400px|thumb|right|Суффиксный бор для строки <tex>abbc</tex>]]
'''Суффиксный бор''' (англ. ''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>).
Для поиска подстроки p в суффиксном боре нужно искать совпадения для символов из p вдоль единственного пути в боре до тех пор, пока либо p не исчерпается, либо дальнейшее совпадение будет невозможным. Если p исчерпалось, то подстрока найдена за <tex>O(|p|)</tex>, если дальнейшее совпадение невозможно, то p нет в суффиксном дереве.

==Свойства==
Суффиксный бор для строки <tex>s</tex>:
* Можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(\lvert p\rvert)</tex>.
* Можно построить за время <tex>O(n^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>.
* Имеет порядка <tex>n^2</tex> вершин.

== Реализация ==
'''struct Trie'''
map<char, integer>[length^2] trie
number <tex> \leftarrow 1</tex>

'''Add'''(i, j)
current <tex>\leftarrow</tex> 0
'''for''' (char c <tex>\in</tex> s[i, j])
if (trie[current] constainKey(c))
trie[current].add(c, number)
number++;
current <tex>\leftarrow</tex> trie[current][c]

'''Build'''(String s)
'''for'''(int i = 0, i < n, i++)
Add(i, n)

==Оценки использования памяти==
Пусть мы построили суффиксный бор для строки <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> памяти, является [[сжатое суффиксное дерево]].

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Словарные структуры данных]]

Суффиксный бор

2012-06-04T12:29:50Z

109.188.204.171: /* Реализация */

[[Файл:Syffix_trie_1.png|400px|thumb|right|Суффиксный бор для строки <tex>abbc</tex>]]
'''Суффиксный бор''' (англ. ''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>).
Для поиска подстроки p в суффиксном боре нужно искать совпадения для символов из p вдоль единственного пути в боре до тех пор, пока либо p не исчерпается, либо дальнейшее совпадение будет невозможным. Если p исчерпалось, то подстрока найдена за <tex>O(|p|)</tex>, если дальнейшее совпадение невозможно, то p нет в суффиксном дереве.

==Свойства==
Суффиксный бор для строки <tex>s</tex>:
* Можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(\lvert p\rvert)</tex>.
* Можно построить за время <tex>O(n^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>.
* Имеет порядка <tex>n^2</tex> вершин.

== Реализация ==
'''struct Vert'''
char symbol
count number
char[] array
integer count

'''struct Trie'''
Vert[length^2] trie
number <tex> \leftarrow 1</tex>

'''Add'''(i, j)
current <tex>\leftarrow</tex> 0
'''for''' (char c <tex>\in</tex> s[i, j])
if (trie[current] constainKey(c))
if(trie[current].count > 1)
inicialize array
array[c] = number
else
symbol = c
number = number
number++;
current <tex>\leftarrow</tex> trie[current][c]

'''Build'''(String s)
'''for'''(int i = 0, i < n, i++)
Add(i, n)

==Оценки использования памяти==
Пусть мы построили суффиксный бор для строки <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> памяти, является [[сжатое суффиксное дерево]].

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Словарные структуры данных]]