120
правок
Изменения
Добавлена историческая справка
{{В разработке}}
'''Алгоритм МакКрейта''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. Отличается от [[Алгоритм Укконена| алгоритма Укконена]] тем, что добавляет суффиксы в порядке убывания длины.
==Историческая справка==
Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году предложил [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf свой алгоритм], в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf свою версию алгоритма], которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
== Теоретическое обоснование ==
Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше. {{Определение|id=def_head. |definition=Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j..\left\vert s \right\vert]</tex> и <tex>s[i..\left\vert s \right\vert])</tex> среди всех <tex>j < i</tex>.}}
Пусть мы знаем <tex>head_i</tex> и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать <tex>head_i</tex> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
{{Лемма
Для удобства реализации вместе с корнем <tex>root</tex> создадим вспомогательную вершину <tex>superRoot</tex>, обладающую свойствами:
* <tex>root.suf = superRoot</tex>
* Для любого символа <tex>c</tex> из вершины <tex>superRoot</tex> есть ребро в корень<tex>root</tex>.
Будем поддерживать инвариант:
|statement=Инвариант алгоритма сохраняется
|proof=Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для <tex>head_{i-1}</tex>, но мы продолжили бы сканирование по ребру дальше и получили две вершины <tex>head_{i-1}.suf, head_i</tex> с неопределенными суффиксными ссылками.
Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j..\left\vert s \right\vert], j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1..\left\vert s \right\vert]</tex>. Тогда и <tex>s[i..\left\vert s \right\vert]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
}}
== Сравнение с другими алгоритмами ==
* Преимущества: мы строим суффиксное дерево в явной форме, что может облегчить понимание алгоритма.
* Недостатки: является offline алгоритмом, то есть требует для начала работы всю строку целиком.
== Источники ==
* [[wikipedia:en:Suffix_tree| Suffix tree - Wikipedia]]* [http://ruwww.wikipediaacademia.orgedu/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 /wiki/%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE Суффиксное дерево 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]
== См. также ==
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]
[[Категория: Дискретная математика и алгоритмы]]
