120
правок
Изменения
Новая страница: «{{В разработке}} '''Алгоритм МакКрейта''' — алгоритм построения [[Сжатое суффиксное дерево|...»
{{В разработке}}
'''Алгоритм МакКрейта''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. Отличается от [[Алгоритм Укконена| алгоритма Укконена]] тем, что добавляет суффиксы в порядке убывания длины.
== Теоретическое обоснование ==
Заметим, что если два суффикса имеют <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> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
{{Лемма
|id=lemma_head
|statement=Пусть <tex>head_i = s[i..i+h]</tex>, тогда <tex>s[i+1..i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.
|proof=
* При <tex>h=0</tex>, очевидно, пустая строка является префиксом любой другой.
* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j..\left\vert s \right\vert]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i..\left\vert s \right\vert]</tex>. Тогда <tex>s[j+1..\left\vert s \right\vert]</tex> будет иметь с <tex>s[i+1..\left\vert s \right\vert]</tex> общий префикс длины <tex>h-1</tex>. Поскольку любой общий префикс будет по определению также являться и префиксом <tex>head_{i+1}</tex>, получаем искомое утверждение.
}}
Если нам известны суффиксные ссылки <tex>u.suf</tex> для каждой вершины <tex>u</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>head_i</tex>, известны суффиксные ссылки.
# Суффиксная ссылка всегда ведет в вершину, а не в середину ребра.
При добавлении каждого следующего суффикса будем выполнять следующие шаги:
* Если суффиксная ссылка <tex>head_{i-1}</tex> не определена:
*# Поднимемся вверх к ее предку;
*# Пройдем по суффиксной ссылке;
*# Спустимся вниз на столько символов, сколько мы прошли вверх к предку (''fast scanning'').
*# Если мы оказались посередине ребра, разрежем его и добавим вершину.
*# Установим суффиксную ссылку для <tex>head_{i-1}</tex>
* Иначе просто пройдем по суффиксной ссылке.
* Будем идти по дереву вниз, пока либо не будет перехода по символу, либо очередной символ на ребре не совпадет с символом нового суффикса (''slow scanning'')
* Добавим ребро/разрежем существующее, запомним новую позицию <tex>head_i</tex> и добавим оставшуюся часть суффикса в качестве листа.
{{Утверждение
|id=proposal_invariant
|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>.
}}
== Асимптотическая оценка ==
В приведенном алгоритме используется константное число операций на добавление одного суффикса, не считая ''slow scanning'' и ''fast scanning''.
''Slow scanning'' делает <tex>\left\vert head_i \right\vert - \left\vert head_{i-1} \right\vert + 1</tex> операций, что суммарно дает <tex>\left\vert head_n \right\vert - \left\vert head_0 \right\vert + n = O(n)</tex> операций.
''Fast scanning'' работает с целыми ребрами, поэтому будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. Из структуры [[Сжатое суффиксное дерево| суффиксного дерева]] мы знаем, что суффиксная ссылка может уменьшить глубину вершины не более, чем на <tex>1</tex>, так что мы на каждой итерации поднимаемся не более, чем на <tex>2</tex> {{---}} один раз к предку, а потом по суффиксной ссылке, что составляет <tex>O(n)</tex> за весь алгоритм. Соответственно, спустимся мы тоже суммарно <tex>O(n)</tex> раз, так как и максимальная глубина составляет <tex>O(n)</tex>.
Итоговая асимптотика алгоритма {{---}} <tex>O(n)</tex>.
== Сравнение с другими алгоритмами ==
Является первым асимптотически оптимальным алгоритмом. В сравнении с [[Алгоритм Укконена| алгоритмом Укконена]]:
* Преимущества: мы строим суффиксное дерево в явной форме, что может облегчить понимание алгоритма.
* Недостатки: является offline алгоритмом, то есть требует для начала работы всю строку целиком.
== Источники ==
* [http://ru.wikipedia.org/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 Суффиксное дерево - Википедия]
* [http://users-cs.au.dk/cstorm/courses/StrAlg_f12/slides/suffix-tree-construction.pdf ''C. N. Storm'', McCreight's suffix tree construction algorithm]
== См. также ==
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]
'''Алгоритм МакКрейта''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. Отличается от [[Алгоритм Укконена| алгоритма Укконена]] тем, что добавляет суффиксы в порядке убывания длины.
== Теоретическое обоснование ==
Заметим, что если два суффикса имеют <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> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
{{Лемма
|id=lemma_head
|statement=Пусть <tex>head_i = s[i..i+h]</tex>, тогда <tex>s[i+1..i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.
|proof=
* При <tex>h=0</tex>, очевидно, пустая строка является префиксом любой другой.
* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j..\left\vert s \right\vert]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i..\left\vert s \right\vert]</tex>. Тогда <tex>s[j+1..\left\vert s \right\vert]</tex> будет иметь с <tex>s[i+1..\left\vert s \right\vert]</tex> общий префикс длины <tex>h-1</tex>. Поскольку любой общий префикс будет по определению также являться и префиксом <tex>head_{i+1}</tex>, получаем искомое утверждение.
}}
Если нам известны суффиксные ссылки <tex>u.suf</tex> для каждой вершины <tex>u</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>head_i</tex>, известны суффиксные ссылки.
# Суффиксная ссылка всегда ведет в вершину, а не в середину ребра.
При добавлении каждого следующего суффикса будем выполнять следующие шаги:
* Если суффиксная ссылка <tex>head_{i-1}</tex> не определена:
*# Поднимемся вверх к ее предку;
*# Пройдем по суффиксной ссылке;
*# Спустимся вниз на столько символов, сколько мы прошли вверх к предку (''fast scanning'').
*# Если мы оказались посередине ребра, разрежем его и добавим вершину.
*# Установим суффиксную ссылку для <tex>head_{i-1}</tex>
* Иначе просто пройдем по суффиксной ссылке.
* Будем идти по дереву вниз, пока либо не будет перехода по символу, либо очередной символ на ребре не совпадет с символом нового суффикса (''slow scanning'')
* Добавим ребро/разрежем существующее, запомним новую позицию <tex>head_i</tex> и добавим оставшуюся часть суффикса в качестве листа.
{{Утверждение
|id=proposal_invariant
|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>.
}}
== Асимптотическая оценка ==
В приведенном алгоритме используется константное число операций на добавление одного суффикса, не считая ''slow scanning'' и ''fast scanning''.
''Slow scanning'' делает <tex>\left\vert head_i \right\vert - \left\vert head_{i-1} \right\vert + 1</tex> операций, что суммарно дает <tex>\left\vert head_n \right\vert - \left\vert head_0 \right\vert + n = O(n)</tex> операций.
''Fast scanning'' работает с целыми ребрами, поэтому будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. Из структуры [[Сжатое суффиксное дерево| суффиксного дерева]] мы знаем, что суффиксная ссылка может уменьшить глубину вершины не более, чем на <tex>1</tex>, так что мы на каждой итерации поднимаемся не более, чем на <tex>2</tex> {{---}} один раз к предку, а потом по суффиксной ссылке, что составляет <tex>O(n)</tex> за весь алгоритм. Соответственно, спустимся мы тоже суммарно <tex>O(n)</tex> раз, так как и максимальная глубина составляет <tex>O(n)</tex>.
Итоговая асимптотика алгоритма {{---}} <tex>O(n)</tex>.
== Сравнение с другими алгоритмами ==
Является первым асимптотически оптимальным алгоритмом. В сравнении с [[Алгоритм Укконена| алгоритмом Укконена]]:
* Преимущества: мы строим суффиксное дерево в явной форме, что может облегчить понимание алгоритма.
* Недостатки: является offline алгоритмом, то есть требует для начала работы всю строку целиком.
== Источники ==
* [http://ru.wikipedia.org/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 Суффиксное дерево - Википедия]
* [http://users-cs.au.dk/cstorm/courses/StrAlg_f12/slides/suffix-tree-construction.pdf ''C. N. Storm'', McCreight's suffix tree construction algorithm]
== См. также ==
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]
