Алгоритм МакКрейта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
м (rollbackEdits.php mass rollback)
 
(не показано 19 промежуточных версий 6 участников)
Строка 1: Строка 1:
{{В разработке}}
+
'''Алгоритм МакКрейта''' (англ. ''McCreight's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. Отличается от [[Алгоритм Укконена| алгоритма Укконена]] тем, что добавляет суффиксы в порядке убывания длины.
'''Алгоритм МакКрейта''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <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 алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
+
Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году предложил свой алоритм<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf Edward M. McCreight {{---}} A Space-Economical Suffix Tree Construction Algorithm]</ref>, в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил свою версию алгоритма<ref>[http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf Esko Ukkonen {{---}} On-line construction of suffix trees]</ref>, которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.
  
 
== Теоретическое обоснование ==
 
== Теоретическое обоснование ==
 
Рассмотрим строку <tex>s</tex> длины <tex>n</tex>, которая заканчивается специальным символом, не встречающимся больше в строке.
 
Рассмотрим строку <tex>s</tex> длины <tex>n</tex>, которая заканчивается специальным символом, не встречающимся больше в строке.
Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше. Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j..n]</tex> и <tex>s[i..n]</tex> среди всех <tex>j < i</tex>.  
+
Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше. Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j \ldots n]</tex> и <tex>s[i \ldots n]</tex> среди всех <tex>j < i</tex>.  
  
 
Пусть мы знаем <tex>head_i</tex> и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать <tex>head_i</tex> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
 
Пусть мы знаем <tex>head_i</tex> и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать <tex>head_i</tex> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
Строка 13: Строка 12:
 
{{Лемма
 
{{Лемма
 
|id=lemma_head
 
|id=lemma_head
|statement=Пусть <tex>head_i = s[i..i+h]</tex>, тогда <tex>s[i+1..i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.
+
|statement=Пусть <tex>head_i = s[i \ldots i+h]</tex>, тогда <tex>s[i+1 \ldots i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.
 
|proof=
 
|proof=
 
* При <tex>h=0</tex>, очевидно, пустая строка является префиксом любой другой.
 
* При <tex>h=0</tex>, очевидно, пустая строка является префиксом любой другой.
* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j..n]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i..n]</tex>. Тогда <tex>s[j+1..n]</tex> будет иметь с <tex>s[i+1..n]</tex> общий префикс длины <tex>h-1</tex>. Поскольку любой общий префикс будет по определению также являться и префиксом <tex>head_{i+1}</tex>, получаем искомое утверждение.
+
* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j \ldots n]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i \ldots n]</tex>. Тогда <tex>s[j+1 \ldots n]</tex> будет иметь с <tex>s[i+1 \ldots n]</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>u.suf</tex> для каждой вершины <tex>u</tex>, мы можем быстро перейти от позиции <tex>head_i</tex> к её суффиксу и продолжить сравнение символов оттуда. Если бы новая позиция <tex>head_i</tex> всегда оказывалась существующей вершиной построенного дерева, этот алгоритм бы уже работал, но в реальности можно оказаться на середине ребра, для которой суффиксная ссылка неизвестна. Для нахождения её суффиксной ссылки на следующей итерации мы сначала перейдем к предку, пройдем по суффиксной ссылке, а уже затем будем продолжать сравнение.
  
 
== Алгоритм ==
 
== Алгоритм ==
Строка 32: Строка 31:
 
При добавлении каждого следующего суффикса будем выполнять следующие шаги:
 
При добавлении каждого следующего суффикса будем выполнять следующие шаги:
 
* Если суффиксная ссылка <tex>head_{i-1}</tex> не определена:
 
* Если суффиксная ссылка <tex>head_{i-1}</tex> не определена:
*# Поднимемся вверх к ее предку;
+
*# Поднимемся вверх к её предку;
 
*# Пройдем по суффиксной ссылке;
 
*# Пройдем по суффиксной ссылке;
 
*# Спустимся вниз на столько символов, сколько мы прошли вверх к предку (''fast scanning'').
 
*# Спустимся вниз на столько символов, сколько мы прошли вверх к предку (''fast scanning'').
Строка 45: Строка 44:
 
|statement=Инвариант алгоритма сохраняется
 
|statement=Инвариант алгоритма сохраняется
 
|proof=Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для <tex>head_{i-1}</tex>, но мы продолжили бы сканирование по ребру дальше и получили две вершины <tex>head_{i-1}.suf,\ head_i</tex> с неопределенными суффиксными ссылками.  
 
|proof=Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для <tex>head_{i-1}</tex>, но мы продолжили бы сканирование по ребру дальше и получили две вершины <tex>head_{i-1}.suf,\ head_i</tex> с неопределенными суффиксными ссылками.  
Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j..n],\ j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1..n]</tex>. Тогда и <tex>s[i..n]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
+
Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j \ldots n],\ j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1 \ldots n]</tex>. Тогда и <tex>s[i \ldots n]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
 
}}
 
}}
  
Строка 51: Строка 50:
 
В вершинах дерева <tex>Node</tex> будем хранить следующую информацию:
 
В вершинах дерева <tex>Node</tex> будем хранить следующую информацию:
 
* <tex>parent</tex> {{---}} предок
 
* <tex>parent</tex> {{---}} предок
* <tex>s[start, end]</tex> {{---}} метка подстроки на ребре от предка
+
* <tex>start, end</tex> {{---}} метка подстроки <tex> s[start \ldots end] </tex> на ребре от предка
 
* <tex>length = end - start + 1</tex> {{---}} длина ребра до предка
 
* <tex>length = end - start + 1</tex> {{---}} длина ребра до предка
 
* <tex>depth</tex> {{---}} глубина вершины в символах
 
* <tex>depth</tex> {{---}} глубина вершины в символах
Строка 58: Строка 57:
  
 
Конструктор будет иметь вид <code>Node(Node parent, '''int''' start, '''int''' end, '''int''' depth)</code>.
 
Конструктор будет иметь вид <code>Node(Node parent, '''int''' start, '''int''' end, '''int''' depth)</code>.
Пусть глобально известна строка <tex>s</tex> со специальным символом на конце, ее длина <tex>n</tex> и используемый алфавит <tex>\Sigma</tex>.
+
Пусть глобально известна строка <tex>s</tex> со специальным символом на конце, её длина <tex>n</tex> и используемый алфавит <tex>\Sigma</tex>.
  
 
<code>
 
<code>
Строка 66: Строка 65:
 
     root = Node(superRoot, 0, -1, 0)
 
     root = Node(superRoot, 0, -1, 0)
 
     root.suf = superRoot
 
     root.suf = superRoot
     '''for''' c '''in''' <tex>\Sigma</tex>:
+
     '''for''' c '''in''' <tex>\Sigma</tex>
 
       superRoot.children[c] = root
 
       superRoot.children[c] = root
 
     head = root  
 
     head = root  
     '''for''' i = 1 '''to''' n:
+
     '''for''' i = 1 '''to''' n
 
       head = addSuffix(head, i)
 
       head = addSuffix(head, i)
 
     '''return''' root
 
     '''return''' root
Строка 79: Строка 78:
  
 
  Node fastScan(Node head):
 
  Node fastScan(Node head):
     '''if''' head {{---}} корень:
+
     '''if''' head {{---}} корень
 
       '''return''' head
 
       '''return''' head
     '''if''' не существует суффиксной ссылки head:
+
     '''if''' не существует суффиксной ссылки head
 
       skipped = head.length    <font color=green> // Сколько символов нам осталось пропустить без проверки </font>
 
       skipped = head.length    <font color=green> // Сколько символов нам осталось пропустить без проверки </font>
 
       curPos = head.start      <font color=green> // Текущая позиция на ребре, нужна для создания ребра по соответствующему символу </font>
 
       curPos = head.start      <font color=green> // Текущая позиция на ребре, нужна для создания ребра по соответствующему символу </font>
       '''if''' head совпадает с корнем:
+
       '''if''' head совпадает с корнем
 
           skipped--
 
           skipped--
 
           curPos++
 
           curPos++
 
       curNode = head.parent.suf <font color=green> // Текущая вершина </font>
 
       curNode = head.parent.suf <font color=green> // Текущая вершина </font>
       '''while''' непройденная длина больше длины ребра:
+
       '''while''' непройденная длина больше длины ребра
 
           curNode = curNode.children[s[curPos]]  
 
           curNode = curNode.children[s[curPos]]  
 
           skipped -= curNode.length
 
           skipped -= curNode.length
 
           curPos += curNode.length
 
           curPos += curNode.length
       '''if''' остались непройденные символы:
+
       '''if''' остались непройденные символы
 
           разделим ребро и запишем новую вершину в curNode
 
           разделим ребро и запишем новую вершину в curNode
 
       head.suf = curNode
 
       head.suf = curNode
Строка 100: Строка 99:
 
     curNode = node                        <font color=green> // Текущая вершина </font>
 
     curNode = node                        <font color=green> // Текущая вершина </font>
 
     curPos = start + node.depth            <font color=green> // Текущий символ суффикса </font>
 
     curPos = start + node.depth            <font color=green> // Текущий символ суффикса </font>
     '''while''' существует ребро по символу curPos:
+
     '''while''' существует ребро по символу curPos
 
       child = curNode.children[s[curPos]] <font color=green> // Ребенок по символу суффикса </font>
 
       child = curNode.children[s[curPos]] <font color=green> // Ребенок по символу суффикса </font>
 
       edgePos = 0                        <font color=green> // Текущая позиция на ребре </font>
 
       edgePos = 0                        <font color=green> // Текущая позиция на ребре </font>
       '''while''' символы на ребре совпадают с суффиксом:   
+
       '''while''' символы на ребре совпадают с суффиксом
 
           curPos++
 
           curPos++
 
           edgePos++
 
           edgePos++
       '''if''' ребро пройдено до конца:
+
       '''if''' ребро пройдено до конца
 
           curNode = child
 
           curNode = child
       '''else''':
+
       '''else'''
 
           разделим ребро в месте несовпадения, запишем в curNode и выйдем из цикла
 
           разделим ребро в месте несовпадения, запишем в curNode и выйдем из цикла
 
     '''return''' curNode
 
     '''return''' curNode
Строка 118: Строка 117:
 
''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> операций.
 
''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>.
+
''Fast scanning'' работает с целыми рёбрами, поэтому будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. Из структуры [[Сжатое суффиксное дерево| суффиксного дерева]] мы знаем, что суффиксная ссылка может уменьшить глубину вершины не более, чем на <tex>1</tex>, так что мы на каждой итерации поднимаемся не более, чем на <tex>2</tex> {{---}} один раз к предку, а потом по суффиксной ссылке, что составляет <tex>O(n)</tex> за весь алгоритм. Соответственно, спустимся мы тоже суммарно <tex>O(n)</tex> раз, так как и максимальная глубина составляет <tex>O(n)</tex>.
  
 
Итоговая асимптотика алгоритма {{---}} <tex>O(n)</tex>.
 
Итоговая асимптотика алгоритма {{---}} <tex>O(n)</tex>.
Строка 130: Строка 129:
 
* Преимущества: мы строим суффиксное дерево в явной форме, что может облегчить понимание алгоритма.
 
* Преимущества: мы строим суффиксное дерево в явной форме, что может облегчить понимание алгоритма.
 
* Недостатки: является offline алгоритмом, то есть требует для начала работы всю строку целиком.
 
* Недостатки: является offline алгоритмом, то есть требует для начала работы всю строку целиком.
 
== Источники ==
 
* [[wikipedia:en:Suffix_tree| Suffix tree - Wikipedia]]
 
* [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]
 
  
 
== См. также ==
 
== См. также ==
 
* [[Сжатое суффиксное дерево]]
 
* [[Сжатое суффиксное дерево]]
 
* [[Алгоритм Укконена]]
 
* [[Алгоритм Укконена]]
 +
* [[Алгоритм Фарача]]
 +
 +
== Примечания ==
 +
<references />
 +
 +
== Источники информации ==
 +
* [http://www.academia.edu/3146231/Algorithms_on_strings_trees_and_sequences_computer_science_and_computational_biology Dan Gusfield, 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]
 +
* [[wikipedia:en:Suffix_tree| Wikipedia {{---}} Suffix tree ]]
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Словарные структуры данных]]

Текущая версия на 19:21, 4 сентября 2022

Алгоритм МакКрейта (англ. McCreight's algorithm) — алгоритм построения суффиксного дерева для заданной строки [math]s[/math] за линейное время. Отличается от алгоритма Укконена тем, что добавляет суффиксы в порядке убывания длины.

Историческая справка

Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году предложил свой алоритм[1], в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил свою версию алгоритма[2], которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.

Теоретическое обоснование

Рассмотрим строку [math]s[/math] длины [math]n[/math], которая заканчивается специальным символом, не встречающимся больше в строке. Заметим, что если два суффикса имеют [math]lcp[/math] (largest common prefix) общих символов, то в построенном суффиксном дереве они будут иметь наименьшего общего предка на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее [math]lcp[/math] с новым суффиксом среди всех суффиксов, добавленных раньше. Обозначим как [math]head_i[/math] — максимальный префикс [math]s[j \ldots n][/math] и [math]s[i \ldots n][/math] среди всех [math]j \lt i[/math].

Пусть мы знаем [math]head_i[/math] и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать [math]head_i[/math] по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.

Лемма:
Пусть [math]head_i = s[i \ldots i+h][/math], тогда [math]s[i+1 \ldots i+h][/math] — префикс [math]head_{i+1}[/math].
Доказательство:
[math]\triangleright[/math]
  • При [math]h=0[/math], очевидно, пустая строка является префиксом любой другой.
  • Пусть [math]h \gt 0[/math]. Из определения [math]head_i[/math] существует суффикс [math]s[j \ldots n][/math], имеющий [math]h[/math] общих символов с [math]s[i \ldots n][/math]. Тогда [math]s[j+1 \ldots n][/math] будет иметь с [math]s[i+1 \ldots n][/math] общий префикс длины [math]h-1[/math]. Поскольку любой общий префикс будет по определению также являться и префиксом [math]head_{i+1}[/math], получаем искомое утверждение.
[math]\triangleleft[/math]

Если нам известны суффиксные ссылки [math]u.suf[/math] для каждой вершины [math]u[/math], мы можем быстро перейти от позиции [math]head_i[/math] к её суффиксу и продолжить сравнение символов оттуда. Если бы новая позиция [math]head_i[/math] всегда оказывалась существующей вершиной построенного дерева, этот алгоритм бы уже работал, но в реальности можно оказаться на середине ребра, для которой суффиксная ссылка неизвестна. Для нахождения её суффиксной ссылки на следующей итерации мы сначала перейдем к предку, пройдем по суффиксной ссылке, а уже затем будем продолжать сравнение.

Алгоритм

Для удобства реализации вместе с корнем [math]root[/math] создадим вспомогательную вершину [math]superRoot[/math], обладающую свойствами:

  • [math]root.suf = superRoot[/math]
  • Для любого символа [math]c[/math] из вершины [math]superRoot[/math] есть ребро в [math]root[/math].

Будем поддерживать инвариант:

  1. Для всех вершин, кроме, возможно, последней добавленной [math]head_i[/math], известны суффиксные ссылки.
  2. Суффиксная ссылка всегда ведет в вершину, а не в середину ребра.

При добавлении каждого следующего суффикса будем выполнять следующие шаги:

  • Если суффиксная ссылка [math]head_{i-1}[/math] не определена:
    1. Поднимемся вверх к её предку;
    2. Пройдем по суффиксной ссылке;
    3. Спустимся вниз на столько символов, сколько мы прошли вверх к предку (fast scanning).
    4. Если мы оказались посередине ребра, разрежем его и добавим вершину.
    5. Установим суффиксную ссылку для [math]head_{i-1}[/math]
  • Иначе просто пройдем по суффиксной ссылке.
  • Будем идти по дереву вниз, пока либо не будет перехода по символу, либо очередной символ на ребре не совпадет с символом нового суффикса (slow scanning)
  • Добавим ребро/разрежем существующее, запомним новую позицию [math]head_i[/math] и добавим оставшуюся часть суффикса в качестве листа.
Утверждение:
Инвариант алгоритма сохраняется
[math]\triangleright[/math]

Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для [math]head_{i-1}[/math], но мы продолжили бы сканирование по ребру дальше и получили две вершины [math]head_{i-1}.suf,\ head_i[/math] с неопределенными суффиксными ссылками.

Покажем, что это невозможно. Рассмотрим, что значит, что [math]head_{i-1}.suf[/math] остановилась посередине ребра. Это означает, что все суффиксы [math]s[j \ldots n],\ j \lt i - 1[/math], которые дошли до этого места, имеют совпадающие следующие символы, по определению [math]head_{i-1}[/math] отличающиеся от символа суффикса [math]s[i - 1 \ldots n][/math]. Тогда и [math]s[i \ldots n][/math] должен отличаться в этом символе, значит [math]head_i = head_{i-1}.suf[/math].
[math]\triangleleft[/math]

Псевдокод

В вершинах дерева [math]Node[/math] будем хранить следующую информацию:

  • [math]parent[/math] — предок
  • [math]start, end[/math] — метка подстроки [math] s[start \ldots end] [/math] на ребре от предка
  • [math]length = end - start + 1[/math] — длина ребра до предка
  • [math]depth[/math] — глубина вершины в символах
  • [math]suf[/math] — суффиксная ссылка
  • [math]children[][/math] — массив детей

Конструктор будет иметь вид Node(Node parent, int start, int end, int depth). Пусть глобально известна строка [math]s[/math] со специальным символом на конце, её длина [math]n[/math] и используемый алфавит [math]\Sigma[/math].

Node buildSuffixTree():
   superRoot = Node(null, 0, -1, 0)
   superRoot.suf = superRoot
   root = Node(superRoot, 0, -1, 0)
   root.suf = superRoot
   for c in [math]\Sigma[/math]
      superRoot.children[c] = root
   head = root 
   for i = 1 to n
      head = addSuffix(head, i)
   return root
Node addSuffix(Node head, int start):
   newHead = slowScan(fastScan(head), start)
   добавим новый лист к newHead
   return newHead
Node fastScan(Node head):
   if head — корень
      return head
   if не существует суффиксной ссылки head
      skipped = head.length     // Сколько символов нам осталось пропустить без проверки 
      curPos = head.start       // Текущая позиция на ребре, нужна для создания ребра по соответствующему символу 
      if head совпадает с корнем
         skipped--
         curPos++
      curNode = head.parent.suf  // Текущая вершина 
      while непройденная длина больше длины ребра
         curNode = curNode.children[s[curPos]] 
         skipped -= curNode.length
         curPos += curNode.length
      if остались непройденные символы
         разделим ребро и запишем новую вершину в curNode
      head.suf = curNode
   return head.suf
Node slowScan(Node node, int start):
   curNode = node                          // Текущая вершина 
   curPos = start + node.depth             // Текущий символ суффикса 
   while существует ребро по символу curPos
      child = curNode.children[s[curPos]]  // Ребенок по символу суффикса 
      edgePos = 0                          // Текущая позиция на ребре 
      while символы на ребре совпадают с суффиксом
         curPos++
         edgePos++
      if ребро пройдено до конца
         curNode = child
      else
         разделим ребро в месте несовпадения, запишем в curNode и выйдем из цикла
   return curNode

Асимптотическая оценка

В приведенном алгоритме используется константное число операций на добавление одного суффикса, не считая slow scanning и fast scanning.

Slow scanning делает [math]\left\vert head_i \right\vert - \left\vert head_{i-1} \right\vert + 1[/math] операций, что суммарно дает [math]\left\vert head_n \right\vert - \left\vert head_0 \right\vert + n = O(n)[/math] операций.

Fast scanning работает с целыми рёбрами, поэтому будем использовать в качестве потенциала глубину в вершинах. Из структуры суффиксного дерева мы знаем, что суффиксная ссылка может уменьшить глубину вершины не более, чем на [math]1[/math], так что мы на каждой итерации поднимаемся не более, чем на [math]2[/math] — один раз к предку, а потом по суффиксной ссылке, что составляет [math]O(n)[/math] за весь алгоритм. Соответственно, спустимся мы тоже суммарно [math]O(n)[/math] раз, так как и максимальная глубина составляет [math]O(n)[/math].

Итоговая асимптотика алгоритма — [math]O(n)[/math].

Сравнение с другими алгоритмами

В сравнении с алгоритмом Вайнера:

  • Преимущества: каждая вершина хранит только суффиксную ссылку, а не массивы размера алфавита.
  • Недостатки: нет.

В сравнении с алгоритмом Укконена:

  • Преимущества: мы строим суффиксное дерево в явной форме, что может облегчить понимание алгоритма.
  • Недостатки: является offline алгоритмом, то есть требует для начала работы всю строку целиком.

См. также

Примечания

Источники информации