Изменения

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

Сжатое суффиксное дерево

1119 байт убрано, 13:11, 22 мая 2015
Поиск строки максимальной длины, ветвящейся влево и вправо 1.3.1
}}
[[Файл:RightMergingSS.png|thumb|400px|center|Суффиксное дерево для строки <tex>aabcabd</tex>]]
Построим cуффиксное дерево при помощи [[Алгоритм Укконена|Алгоритма алгоритма Укконена]]. В полученном дереве не листовой вершине <tex>v</tex> будет соответствовать подстрока <tex>s</tex>, которая ветвится вправо, при условии, что количество "хороших" детей вершины <tex>v > 2</tex> ("хорошие" дети {{---}} листы, метка которых <tex>\ne\$</tex>). В примере для строки <tex>aabcabd</tex> это <tex>b</tex>, <tex>a</tex> и <tex>ab</tex>. Далее введём термины ''левый символ'' и ''вершина различная влево'', чтобы найти строки, ветвящиеся влево.
{{Определение
|definition=
'''Вершина <tex>v</tex> различна влево''', если как минимум два листа в поддереве <tex>v</tex> имеют различные ''левые символы''. По определению лист не может быть различным влево.
}}
{{Теорема
|about=
о строке, ветвящейся вправо и влево
|statement=
Строка <tex>a</tex>, соответствующая пути к вершине <tex>v</tex>, является ветвящейся вправо и влево тогда и только тогда, когда вершина <tex>v</tex> ''различна влево'' и счётчик вершины <tex>> 1</tex>.
|proof=
<tex>\Leftarrow</tex>
ПредположимДопустим, что <tex>v</tex> различна строка ветвится влево. Значит, что Тогда существуют подстроки <tex>cssa</tex> и <tex>dssb</tex>. Пусть за первой подстрокой следует символ В суффиксном дереве существует вершина <tex>pv</tex>. Если за второй подстрокой следует символ, соответствующая строке <tex>\ne ps</tex>(так как есть как минимум два суффикса, то начинающиеся со строки <tex>s</tex> {{---}} строка, ветвящаяся вправо и влево). Так как же у вершины <tex>v</tex> , есть как минимум два различных ребёнка, которые начинаются с различных символов у которых ''левый символ'' <tex>pc</tex> и <tex>d</tex>,q \ne \$значит вершина <tex>v</tex>, строка является ветвящейся вправо''различна влево'' по определению.
Чтобы найти строки, ветвящиеся влево, нужно проверить все вершины суффиксного дерева на различность влево. Если какая-то вершина <tex>\Rightarrowv</tex>будет различна влево и удволетворять свойству ветвимости право, то строка, соответствующая вершине <tex>v</tex> будет ветвится вправо и влево.
Пусть строка <tex>s</tex> является ветвящейся вправо и влево. Тогда существуют подстроки <tex>csa</tex> и <tex>dsb</tex>. В суффиксном дереве существует вершина <tex>v</tex> соответствующая строке <tex>s</tex> (так как есть как минимум два суффикса, начинающиеся со строки <tex>s</tex>). У вершины <tex>v</tex>, есть как минимум два ребёнка, которые начинаются с символов <tex>a</tex> и <tex>b</tex> <tex>\Rightarrow</tex> счётчик вершины <tex>> 2</tex>. Так же у вершины <tex>v</tex>, есть как минимум два ребёнка, у которых ''левый символ'' <tex>c</tex> и <tex>d</tex>, значит вершина <tex>v</tex> ''различна влево'' по определению.}} Чтобы найти строки, ветвящиеся влево, нужно проверить все вершины суффиксного дерева на различность влево. Если какая-то вершина <tex>v</tex> будет различна влево и удволетворять свойству ветвимости право, то строка, соответствующая вершине <tex>v</tex> будет ветвится вправо и влево по теореме. Чтобы найти вершины различные влево будем хранить левый символ для каждой вершины, пусть он будет <tex>\$#</tex>, если вершина различна влево. Чтобы промаркировать всё дерево, нужно записать левые символы для листов, а затем подниматься вверх по дереву. Для каждой вершины <tex>v</tex> будем запускать проверку:*Если среди левых символов детей <tex>v</tex> есть хотя бы один <tex>\$#</tex>, то запишем в <tex>v</tex> <tex>\$#</tex> и закончим проверку(в суффиксном дереве свойство различности влево наследуется вверх {{---}} строка соответствующая вершине <tex>v</tex> и строка соответствующая ребёнку <tex>v</tex> начинаются с одного и того же символа).*Если среди левых символов детей <tex>v</tex> нет ни одного <tex>\$#</tex>, то проверим на совпадение левые символы детей:
**Если все левые символ детей <tex>v</tex> одинаковы и эквивалентны <tex>x</tex>, то запишем в <tex>v</tex> <tex>x</tex>.
**Если не все левые символы детей <tex>v</tex>, то запишем в <tex>v</tex> <tex>\$#</tex> {{---}} вершина различна влево.
Так как время проверки <tex>v</tex> пропорционально числу детей, время работы всего алгоритма {{---}} <tex>O(n)</tex>.
Анонимный участник

Навигация