Изменения

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

Алгоритм Укконена

2304 байта убрано, 21:02, 29 апреля 2015
Нет описания правки
Алгоритм состоит из <tex>n</tex> итераций так как в исходном тексте <tex>O(n)</tex> суффиксов. На каждой фазе происходит продление всех суффиксов по порядку, что требует <tex>O(n^2)</tex> времени. Следовательно, общая асимптотика алгоритма <tex>O(n^3)</tex>.
=== Псевдокод алгоритма за O(n<sup>3</sup>) ===<code style = "display: inline-block;"> '''for''' i = 1 .. n '''for''' j = 1 .. i treeExtend(s[1..j]) <font color=green>// добавление текущего суффикса работает за линейное время</font></code>
'''Замечание:''' на первый взгляд, более логичным подходом кажется добавление всех суффиксов строки в дерево по очереди, получив сразу алгоритм со временем работы <tex>O(n^2)</tex>. Однако улучшение данного алгоритма до линейного времени работы будет намного сложней осуществить, хотя именно в этом и заключается суть [[Алгоритм МакКрейта | алгоритма МакКрейта]].
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.png|300px]]
|}
 
== Реализация алгоритма за O(n<sup>3</sup>) ==
for i = 1 .. n
for j = 1 .. i
спускаемся от корня до конца текущего <tex>j</tex>-го суффикса
совершаем продление символом <tex>s_{i}</tex> по одному из правил
==Суффиксные ссылки==
# На сегодняшний день существуют кэш-эффективные алгоритмы, которые превосходят алгоритм Укконена на современных процессорах<ref>[https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&ved=0CFMQFjAF&url=http%3A%2F%2Fwww.researchgate.net%2Fprofile%2FYuanyuan_Tian%2Fpublication%2F30848628_Practical_methods_for_constructing_suffix_trees%2Flinks%2F0046352b38e5dc849e000000.pdf&ei=Bh4sVZL8EIausAHujoDoBg&usg=AFQjCNEAr63t7zZnWZPKYIZLjQQInbelSg&sig2=jAPs1IULJvJZt8xwx5PYtA&bvm=bv.90491159,d.bGg&cad=rja Yuanyuan Tian, Sandeep Tata, Richard A. Hankins, Jignesh M. Patel {{---}} Practical methods for constructing suffix trees.]</ref>.
# Так же алгоритм предполагает, что дерево полностью должно быть загружено в оперативную память, а при больших размерах входных данных это может быть затруднительно, поэтому хотелось бы, чтобы дерево было загружено "частично"<ref>[http://arxiv.org/pdf/1012.4074.pdf Woong-Kee Loh, Yang-Sae Moon, Wookey Lee {{---}} A fast divide-and-conquer algorithm for indexing human genome sequences.]</ref>.
 
== Реализация алгоритма за O(n) ==
'''struct Node'''
'''int''' begin
'''int''' end
'''Node''' parent
'''Node[]''' children
'''Node''' suffixLink
'''function''' buildSuffixTree(s):
'''int''' n = s.length()
'''Node''' root = new Node(0, 0, null)
'''Node''' node = root <font color=green>// вершина, в которой мы остановились на предыдущем шаге</font>
'''int''' tail = 0 <font color=green>// длина в символах до конца текущего суффикса по метке, которой помечено ребро, ведущее из node по символу s[i - tail]</font>
'''for''' i = 0..n
'''Node''' last = null <font color=green>// последняя созданная на текущей итерации внутренняя вершина</font>
'''while''' tail <tex>\geqslant</tex> 0
'''Node''' ch = node.children[s[i - tail]]
'''while''' ch <tex>\ne</tex> null && tail <tex>\geqslant</tex> ch.end - ch.begin
tail -= ch.end - ch.begin
node = ch
ch = ch.children[s[i - tail]]
'''if''' ch == null
создаем новую вершину по правилу продления 2.а с ребром, помеченным s[i]
'''if''' last <tex>\ne</tex> null
last.suffixLink = node
last = null
'''else'''
t = s[ch.begin + tail]
'''if''' t == s[i]
ничего не делаем по правилу продления 3
'''if''' last <tex>\ne</tex> null
last.suffixLink = node
'''break'''
'''else'''
используем правило продления 2.б :
разделяем ребро, ведущее в текущую вершину, новой вершиной splitNode
и создаем новый лист с ребром, помеченным s[i]
'''if''' last <tex>\ne</tex> null
last.suffixLink = splitNode
last = splitNode
'''if''' node == root
--tail
'''else'''
node = node.suffixLink
tail++
'''return''' root
== См. также==
KK
275
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/45883»

Навигация