Изменения

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

Алгоритм МакКрейта

379 байт убрано, 20:53, 6 мая 2014
Изменен псевдокод
В вершинах дерева <tex>Node</tex> будем хранить следующую информацию:
* <tex>parent</tex> {{---}} предок
* <tex>s[start,\ end]</tex> {{---}} позиции строки, соответствующие ребру до метка подстроки на ребре от предка <tex>s[start, end]</tex>* <tex>length= end - start + 1</tex> {{---}} длина ребра до предка
* <tex>depth</tex> {{---}} глубина вершины в символах
* <tex>suf</tex> {{---}} суффиксная ссылка
Node addSuffix(Node head, '''int''' start):
newHead = slowScan(fastScan(head), start)
newLeaf = Node(добавим новый лист к newHead, start + newHead.depth, n, n - start + 1) newHead.children[s[start + newHead.depth]] = newLeaf
'''return''' newHead
Node fastScan(Node head):
'''if''' если head.depth == 0{{---}} корень:
'''return''' head
'''if''' если не существует суффиксной ссылки head.suf == '''null''':
skipped = head.length
curPos = head.start
'''if''' skipped > 0 '''and''' если head.parent.depth == 0совпадает с корнем:
skipped--
curPos++
curNode = head.parent.suf
'''while''' curNode.children[s[curPos]].length <tex>\leqslant</tex> skippedпока непройденная длина больше длины ребра:
curNode = curNode.children[s[curPos]]
skipped -= curNode.length
curPos += curNode.length
'''if''' skipped > 0если остались непройденные символы: newNode = split(curNode, разделим ребро и запишем новую вершину в curNode.children[s[curPos]], skipped) head.suf = newNodecurNode
'''return''' head.suf
 
Node split(Node parent, Node child, '''int''' edgeLength):
inserted = Node(parent, child.start, child.start + edgeLenth - 1, parent.depth + edgeLength)
parent.children[s[child.start]] = inserted
child.start += edgeLength
child.length -= edgeLength
inserted.children[s[child.start]] = child
child.parent = inserted
'''return''' inserted
Node slowScan(Node node, '''int''' start):
curNode = node
curPos = start + node.depth
'''while''' curNode.children[s[пока существует ребро по символу curPos]] != null:
child = curNode.children[s[curPos]]
edgePos = 0
'''while''' child.start + edgePos <tex>\leqslant</tex> child.end '''and''' s[child.start + edgePos] == s[curPos]пока символы на ребре совпадают с суффиксом:
curPos++
edgePos++
'''if''' child.start + edgePos > child.endесли ребро пройдено до конца:
curNode = child
'''else'''иначе: разделим ребро в месте несовпадения, запишем в curNode = split(curNode, child, edgePos) '''break''' и выйдем из цикла
'''return''' curNode
</code>
* [http://www.academia.edu/3146231/Algorithms_on_strings_trees_and_sequences_computer_science_and_computational_biology ''Gusfield, Dan'' , Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology // Cambridge University Press, {{---}} 1999. {{---}} ISBN: 0-521-58519-8]
* [http://users-cs.au.dk/cstorm/courses/StrAlg_f12/slides/suffix-tree-construction.pdf ''C. N. Storm'', McCreight's suffix tree construction algorithm]
* [http://pastie.org/9146207 Реализация на языке Java]
== См. также ==
Genyaz
120
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/36767»

Навигация