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

Эта статья находится в разработке!

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

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

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

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

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

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

Лемма:

Пусть [math]head_i = s[i..i+h][/math], тогда [math]s[i+1..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..n][/math], имеющий [math]h[/math] общих символов с [math]s[i..n][/math]. Тогда [math]s[j+1..n][/math] будет иметь с [math]s[i+1..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..n],\ j \lt i - 1[/math], которые дошли до этого места, имеют совпадающие следующие символы, по определению [math]head_{i-1}[/math] отличающиеся от символа суффикса [math]s[i - 1..n][/math]. Тогда и [math]s[i..n][/math] должен отличаться в этом символе, значит [math]head_i = head_{i-1}.suf[/math].

[math]\triangleleft[/math]

Псевдокод

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

• [math]parent[/math] — предок
• [math]s[start, 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):
   если head — корень:
      return head
   если не существует суффиксной ссылки head:
      skipped = head.length
      curPos = head.start
      если head совпадает с корнем:
         skipped--
         curPos++
      curNode = head.parent.suf
      пока непройденная длина больше длины ребра:
         curNode = curNode.children[s[curPos]] 
         skipped -= curNode.length
         curPos += curNode.length
      если остались непройденные символы:
         разделим ребро и запишем новую вершину в curNode
      head.suf = curNode
   return head.suf

Node slowScan(Node node, int start):
   curNode = node
   curPos = start + node.depth
   пока существует ребро по символу curPos:
      child = curNode.children[s[curPos]]
      edgePos = 0
      пока символы на ребре совпадают с суффиксом:    
         curPos++
         edgePos++
      если ребро пройдено до конца:
         curNode = child
      иначе:
         разделим ребро в месте несовпадения, запишем в 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 алгоритмом, то есть требует для начала работы всю строку целиком.

Источники

• Suffix tree - Wikipedia
• Gusfield, Dan , Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology // Cambridge University Press, — 1999. — ISBN: 0-521-58519-8
• C. N. Storm, McCreight's suffix tree construction algorithm

См. также

• Сжатое суффиксное дерево
• Алгоритм Укконена