Алгоритм дерева суффиксов Укконена на простом английском

Я чувствую себя немного толстым в этот момент. Я потратил несколько дней, пытаясь полностью обернуть голову вокруг построения суффиксного дерева, но, поскольку у меня нет математического фона, многие объяснения ускользают от меня, поскольку они начинают чрезмерно использовать математические символы. Наиболее близким к хорошему объяснению, которое я нашел, является быстрый поиск строк с суффиксными деревьями, но он закрывает глаза на различные моменты, и некоторые аспекты алгоритма остаются неясными.

Я уверен, что пошаговое объяснение этого алгоритма здесь, на переполнении стека, было бы неоценимо для многих других, кроме меня.

Для справки вот статья Укконена об алгоритме: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Мое базовое понимание, пока:

  • Мне нужно перебрать каждый префикс P данной строки T
  • Мне нужно перебрать каждый суффикс S в префиксе P и добавить его в дерево
  • Чтобы добавить суффикс S к дереву, мне нужно выполнить итерацию по каждому символу в S, причем итерации состоят из перехода по существующей ветви, начинающейся с того же набора символов C в S, и потенциального разбиения ребра на дочерние узлы, когда я достигните другого символа в суффиксе, ИЛИ, если не было подходящего края, чтобы идти вниз. Когда не найдено подходящего ребра для C, создается новый лист для ребра C.

Базовый алгоритм выглядит как O (n2), как указано в большинстве объяснений, так как нам нужно пройти по всем префиксам, а затем нам нужно пройти по каждому из суффиксов для каждого префикса. Алгоритм Укконена, по-видимому, уникален из-за техники указателя суффикса, которую он использует, хотя я думаю, что это то, что мне трудно понять

У меня также есть проблемы с пониманием:

  • когда и как назначается, используется и изменяется "активная точка"
  • что происходит с аспектом канонизации алгоритма
  • Почему реализации, которые я видел, должны "исправить" ограничивающие переменные, которые они используют

Вот завершенный исходный код C#. Он не только работает правильно, но поддерживает автоматическую канонизацию и визуализирует текстовый график с более приятным видом. Исходный код и пример выходных данных находятся по адресу:

https://gist.github.com/2373868

Обновление 2017-11-04

Спустя много лет я нашел новое применение для деревьев суффиксов и реализовал алгоритм в JavaScript. Суть ниже. Это должно быть без ошибок. Записать его в файл JS, npm install chalk из того же места, а затем запустите с node.js, чтобы увидеть некоторые красочные выходные данные. В том же Gist есть урезанная версия без какого-либо кода отладки.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6

Источник

6 ответов

Решение

Следующее является попыткой описать алгоритм Укконена, сначала показывая, что он делает, когда строка простая (то есть не содержит повторяющихся символов), а затем расширяя его до полного алгоритма.

Сначала несколько предварительных заявлений.

  1. То, что мы строим, в основном похоже на поиск. Таким образом, есть корневой узел, выходящие из него ребра, ведущие к новым узлам, и выходящие из них ребра и т. Д.

  2. Но: в отличие от поиска, метки ребер не являются одиночными символами. Вместо этого каждое ребро помечается с использованием пары целых чисел [from,to], Это указатели на текст. В этом смысле каждое ребро несет строковую метку произвольной длины, но занимает только O(1) пробел (два указателя).

Основной принцип

Я хотел бы сначала продемонстрировать, как создать дерево суффиксов для особенно простой строки, строки без повторяющихся символов:

abc

Алгоритм работает пошагово, слева направо. Существует один шаг для каждого символа строки. Каждый шаг может включать более одной отдельной операции, но мы увидим (см. Заключительные наблюдения в конце), что общее количество операций составляет O(n).

Итак, мы начинаем слева и сначала вставляем только один символ a создав ребро от корневого узла (слева) до листа и пометив его как [0,#], что означает, что край представляет подстроку, начинающуюся в позиции 0 и заканчивающуюся в текущем конце. Я использую символ # означать текущий конец, который находится в позиции 1 (сразу после a).

Итак, у нас есть начальное дерево, которое выглядит так:

И что это значит, это:

Теперь мы переходим к позиции 2 (сразу после b). Наша цель на каждом шаге - вставить все суффиксы до текущей позиции. Мы делаем это путем

  • расширение существующих a к ab
  • вставив один новый край для b

В нашем представлении это выглядит так

И что это значит:

Мы наблюдаем две вещи:

  • Представление края для ab такой же, какой был в исходном дереве: [0,#], Его значение автоматически изменилось, потому что мы обновили текущую позицию # от 1 до 2.
  • Каждое ребро занимает O(1) места, потому что оно состоит только из двух указателей на текст, независимо от того, сколько символов оно представляет.

Затем мы снова увеличиваем позицию и обновляем дерево, добавляя c к каждому существующему ребру и вставляя одно новое ребро для нового суффикса c,

В нашем представлении это выглядит так

И что это значит:

Мы наблюдаем:

  • Дерево - это правильное суффиксное дерево до текущей позиции после каждого шага
  • Есть столько шагов, сколько символов в тексте
  • Объем работы на каждом шаге равен O(1), потому что все существующие ребра обновляются автоматически путем увеличения # и вставка одного нового ребра для последнего символа может быть выполнена за O(1) раз. Следовательно, для строки длины n требуется только время O(n).

Первое расширение: простые повторения

Конечно, это работает очень хорошо только потому, что наша строка не содержит повторений. Теперь посмотрим на более реалистичную строку:

abcabxabcd

Начинается с abc как в предыдущем примере, то ab повторяется и сопровождается x, а потом abc повторяется с последующим d,

Шаги с 1 по 3: после первых 3 шагов у нас есть дерево из предыдущего примера:

Шаг 4: Мы двигаемся # в положение 4. Это неявно обновляет все существующие ребра до этого:

и нам нужно вставить окончательный суффикс текущего шага, a в корне.

Прежде чем сделать это, мы вводим еще две переменные (в дополнение к #), которые, конечно, были там все время, но мы до сих пор их не использовали:

  • Активная точка, которая является тройной (active_node,active_edge,active_length)
  • remainder, которое является целым числом, указывающим, сколько новых суффиксов нам нужно вставить

Точное значение этих двух скоро станет ясным, но сейчас давайте просто скажем:

  • В простом abc Например, активная точка всегда была (root,'\0x',0) т.е. active_node был корневым узлом, active_edge был указан как нулевой символ '\0x', а также active_length был ноль. Результатом этого было то, что одно новое ребро, которое мы вставляли на каждом шаге, было вставлено в корневой узел как вновь созданное ребро. Скоро мы увидим, почему тройка необходима для представления этой информации.
  • remainder всегда был равен 1 в начале каждого шага. Смысл этого состоял в том, что число суффиксов, которые мы должны были активно вставлять в конце каждого шага, равнялось 1 (всегда только последний символ).

Теперь это изменится. Когда мы вставляем текущий последний символ a в корне мы замечаем, что уже существует исходящий фронт, начинающийся с a в частности: abca, Вот что мы делаем в таком случае:

  • Мы не вставляем свежий край [4,#] в корневом узле. Вместо этого мы просто замечаем, что суффикс a уже в нашем дереве. Это заканчивается в середине более длинного края, но нас это не беспокоит. Мы просто оставляем вещи такими, какие они есть.
  • Мы устанавливаем активную точку (root,'a',1), Это означает, что активная точка сейчас находится где-то посередине исходящего края корневого узла, который начинается с a в частности, после позиции 1 на этом краю. Мы замечаем, что ребро определяется просто его первым символом a, Этого достаточно, потому что может быть только одно ребро, начинающееся с любого конкретного символа (подтвердите, что это верно после прочтения всего описания).
  • Мы также увеличиваем remainder, поэтому в начале следующего шага это будет 2.

Наблюдение: когда будет найдено, что последний суффикс, который нам нужно вставить, уже существует в дереве, само дерево вообще не изменяется (мы только обновляем активную точку и remainder). Тогда дерево больше не является точным представлением дерева суффиксов вплоть до текущей позиции, но оно содержит все суффиксы (потому что последний суффикс a содержится неявно). Следовательно, кроме обновления переменных (которые имеют фиксированную длину, то есть O(1)), на этом этапе не было выполнено никакой работы.

Шаг 5: Обновляем текущую позицию # до 5. Это автоматически обновляет дерево к этому:

И потому что remainder 2, нам нужно вставить два последних суффикса текущей позиции: ab а также b, Это в основном потому, что:

  • a суффикс предыдущего шага никогда не вставлялся должным образом. Так оно и осталось, и с тех пор, как мы продвинулись на один шаг, теперь оно выросло из a в ab,
  • И нам нужно вставить новый окончательный край b,

На практике это означает, что мы идем к активной точке (которая указывает на a на то, что сейчас abcab край) и вставьте текущий последний символ b, Но: опять же, получается, что b также уже присутствует на том же краю.

Итак, опять же, мы не меняем дерево. Мы просто:

  • Обновите активную точку до (root,'a',2) (тот же узел и ребро, что и раньше, но теперь мы указываем на b)
  • Увеличить remainder в 3, потому что мы все еще не вставили должным образом последний край из предыдущего шага, и мы также не вставляем текущий последний край.

Чтобы было ясно: мы должны были вставить ab а также b на текущем этапе, но потому что ab уже найден, мы обновили активную точку и даже не пытались вставить b, Зачем? Потому что, если ab находится в дереве, каждый его суффикс (включая b) тоже должно быть в дереве. Возможно, только неявно, но это должно быть там, из-за того, как мы построили дерево до сих пор.

Переходим к шагу 6, увеличивая #, Дерево автоматически обновляется до:

Так как remainder 3, мы должны вставить abx, bx а также x, Активная точка говорит нам, где ab заканчивается, так что нам нужно просто прыгнуть туда и вставить x, В самом деле, x еще не там, поэтому мы разделили abcabx край и вставьте внутренний узел:

Представления ребер по-прежнему являются указателями на текст, поэтому разбиение и вставка внутреннего узла могут быть выполнены за O(1) времени.

Итак, мы имели дело с abx и декремент remainder 2. Теперь нам нужно вставить следующий оставшийся суффикс, bx, Но прежде чем мы это сделаем, нам нужно обновить активную точку. Правило для этого, после разделения и вставки ребра, будет называться Правилом 1 ниже, и оно применяется всякий раз, когда active_node является корнем (мы изучим правило 3 для других случаев ниже). Вот правило 1:

После вставки из рута,

  • active_node остается корнем
  • active_edge устанавливается на первый символ нового суффикса, который нам нужно вставить, т.е. b
  • active_length уменьшается на 1

Следовательно, новая тройка активной точки (root,'b',1) указывает на то, что следующая вставка должна быть сделана на bcabx край, позади 1 символа, то есть позади b, Мы можем определить точку вставки в O(1) времени и проверить, x уже присутствует или нет. Если бы он присутствовал, мы бы завершили текущий шаг и оставили все как есть. Но x отсутствует, поэтому мы вставим его, разделив край:

Опять же, это заняло O(1) время, и мы обновляем remainder 1 и активная точка (root,'x',0) как гласит правило 1.

Но есть еще одна вещь, которую нам нужно сделать. Мы назовем это Правило 2:

Если мы разделим ребро и вставим новый узел, и если это не первый узел, созданный во время текущего шага, мы соединим ранее вставленный узел и новый узел через специальный указатель - суффиксную ссылку. Позже мы увидим, почему это полезно. Вот что мы получаем, суффиксная ссылка представляется в виде пунктирного края:

Нам все еще нужно вставить окончательный суффикс текущего шага, x, Так как active_length Компонент активного узла упал до 0, последняя вставка производится прямо в корень. Поскольку в корневом узле нет исходящего ребра, начинающегося с x вставляем новое ребро:

Как видим, на текущем шаге все остальные вставки были сделаны.

Переходим к шагу 7, установив # =7, который автоматически добавляет следующий символ, a по всем краям листа, как всегда. Затем мы пытаемся вставить новый последний символ в активную точку (корень) и обнаруживаем, что он уже там. Таким образом, мы заканчиваем текущий шаг, ничего не вставляя, и обновляем активную точку до (root,'a',1),

На шаге 8 # =8, мы добавляем b и, как видно ранее, это только означает, что мы обновляем активную точку до (root,'a',2) и приращение remainder ничего не делая, потому что b уже присутствует. Тем не менее, мы замечаем (за время O(1)), что активная точка теперь находится в конце ребра. Мы отражаем это, восстанавливая его (node1,'\0x',0), Здесь я использую node1 ссылаться на внутренний узел ab край заканчивается в.

Затем в шаге # = 9, нам нужно вставить 'c', и это поможет нам понять последний трюк:

Второе расширение: использование суффиксных ссылок

Как всегда, # обновление добавляет c автоматически до краев листа, и мы идем к активной точке, чтобы посмотреть, можем ли мы вставить 'c'. Оказывается, "с" уже существует на этом краю, поэтому мы устанавливаем активную точку в (node1,'c',1), приращение remainder и больше ничего не делать.

Сейчас в шаге # = 10, remainder is 4 и так нам сначала нужно вставить abcd (который остается от 3 шагов назад), вставив d в активной точке.

Попытка вставить d в активной точке вызывает разрыв ребра за время O(1):

active_node, с которого было начато разделение, отмечено красным цветом выше. Вот последнее правило, правило 3:

После разделения края от active_node это не корневой узел, мы следуем по суффиксной ссылке, выходящей из этого узла, если она есть, и сбрасываем active_node на узел, на который он указывает. Если нет суффиксной ссылки, мы устанавливаем active_node в корень. active_edge а также active_length остается неизменным.

Итак, активная точка сейчас (node2,'c',1), а также node2 помечено красным ниже:

С момента вставки abcd завершено, мы уменьшаем remainder 3 и рассмотрим следующий оставшийся суффикс текущего шага, bcd, Правило 3 установило активной точкой только правый узел и ребро, поэтому вставка bcd можно сделать, просто вставив его последний символ d в активной точке.

Это вызывает другое разделение ребер, и из-за правила 2 мы должны создать суффиксную ссылку от ранее вставленного узла к новому:

Мы наблюдаем: Суффиксные ссылки позволяют нам сбросить активную точку, чтобы мы могли выполнить следующую оставшуюся вставку за O(1). Посмотрите на график выше, чтобы подтвердить, что действительно узел на метке ab связан с узлом в b (его суффикс) и узел в abc связан с bc,

Текущий шаг еще не закончен. remainder сейчас 2, и нам нужно следовать правилу 3, чтобы снова сбросить активную точку. Так как текущий active_node (красный цвет выше) не имеет суффиксной ссылки, мы сбрасываем root. Активная точка сейчас (root,'c',1),

Следовательно, следующая вставка происходит на одном исходящем ребре корневого узла, чья метка начинается с c: cabxabcd позади первого символа, то есть позади c, Это вызывает еще один раскол:

И поскольку это включает создание нового внутреннего узла, мы следуем правилу 2 и устанавливаем новую ссылку на суффикс из ранее созданного внутреннего узла:

(Я использую Graphviz Dot для этих маленьких графиков. Новая ссылка на суффикс заставила точку переставить существующие ребра, поэтому проверьте, чтобы убедиться, что единственное, что было вставлено выше, это новая ссылка на суффикс.)

С этим, remainder может быть установлен в 1 и так как active_node root, мы используем правило 1 для обновления активной точки до (root,'d',0), Это означает, что последняя вставка текущего шага состоит в том, чтобы вставить одну d в корне:

Это был последний шаг, и мы сделали. Есть несколько заключительных замечаний:

  • На каждом шагу мы движемся # вперед на 1 позицию. Это автоматически обновляет все конечные узлы за O(1) раз.

  • Но это не касается а) любых суффиксов, оставшихся от предыдущих шагов, и б) с одним последним символом текущего шага.

  • remainder говорит нам, сколько дополнительных вставок нам нужно сделать. Эти вставки соответствуют один к одному конечным суффиксам строки, которая заканчивается в текущей позиции #, Рассмотрим один за другим и сделаем вкладыш. Важное замечание : Каждая вставка выполняется за O(1) раз, так как активная точка говорит нам точно, куда идти, и нам нужно добавить только один единственный символ в активной точке. Зачем? Потому что другие символы содержатся неявно (в противном случае активная точка не будет там, где она есть).

  • После каждой такой вставки мы уменьшаем remainder и перейдите по ссылке суффикса, если есть. Если нет, мы идем к корню (правило 3). Если мы уже в корне, мы модифицируем активную точку, используя правило 1. В любом случае, это займет всего O(1) времени.

  • Если во время одной из этих вставок мы обнаружим, что символ, который мы хотим вставить, уже есть, мы ничего не делаем и завершаем текущий шаг, даже если remainder >0. Причина в том, что любые оставшиеся вставки будут суффиксами той, которую мы только что попытались сделать. Следовательно, они все неявные в текущем дереве. Дело в том, что remainder > 0 гарантирует, что мы будем иметь дело с остальными суффиксами позже.

  • Что делать, если в конце алгоритма remainder >0? Это будет иметь место всякий раз, когда конец текста является подстрокой, которая произошла где-то раньше. В этом случае мы должны добавить один дополнительный символ в конец строки, чего раньше не было. В литературе обычно знак доллара $ используется в качестве символа для этого. Почему это имеет значение? -> Если позже мы используем заполненное дерево суффиксов для поиска суффиксов, мы должны принимать совпадения, только если они заканчиваются на листе. В противном случае мы получили бы много ложных совпадений, потому что в дереве много неявно содержащихся строк, которые не являются действительными суффиксами основной строки. форсирование remainder быть 0 в конце - это, по сути, способ гарантировать, что все суффиксы заканчиваются на листовом узле. Однако, если мы хотим использовать дерево для поиска общих подстрок, а не только суффиксов основной строки, этот последний шаг действительно не требуется, как предлагается в комментарии ОП ниже.

  • Так в чем же сложность всего алгоритма? Если длина текста n символов, очевидно, что n шагов (или n+1, если мы добавим знак доллара). На каждом шаге мы либо ничего не делаем (кроме обновления переменных), либо делаем remainder вставки, каждая занимает O(1) раз. поскольку remainder указывает, сколько раз мы ничего не делали на предыдущих шагах, и уменьшается для каждой вставки, которую мы делаем сейчас, общее количество раз, когда мы что-то делаем, равно n (или n+1). Следовательно, общая сложность O(n).

  • Однако есть одна небольшая вещь, которую я не объяснил должным образом: может случиться так, что мы перейдем по суффиксной ссылке, обновим активную точку, а затем обнаружим, что ее active_length компонент плохо работает с новым active_node, Например, рассмотрим ситуацию, подобную этой:

(Пунктирные линии обозначают остальную часть дерева. Пунктирная линия является суффиксной ссылкой.)

Теперь пусть активная точка будет (red,'d',3) так что это указывает на место за f на defg край. Теперь предположим, что мы сделали необходимые обновления, и теперь перейдем по суффиксной ссылке, чтобы обновить активную точку в соответствии с правилом 3. Новая активная точка (green,'d',3), Тем не менее d выход из зеленого узла de так что в нем всего 2 символа. Чтобы найти правильную активную точку, нам, очевидно, нужно пройти по этому краю до синего узла и сбросить на (blue,'f',1),

В особо плохом случае active_length может быть таким большим, как remainder, который может быть большим, чем п. И вполне может случиться, что для нахождения правильной активной точки нам нужно не только перепрыгнуть через один внутренний узел, но, возможно, через несколько, вплоть до n в худшем случае. Означает ли это, что алгоритм имеет скрытую сложность O (n 2), потому что на каждом этапе remainder обычно O(n), и пост-корректировки активного узла после перехода по суффиксной ссылке тоже могут быть O (n)?

Нет. Причина в том, что если нам действительно нужно настроить активную точку (например, с зеленого на синий, как указано выше), это приведет нас к новому узлу, который имеет собственную суффиксную ссылку, и active_length будет уменьшено. Следуя цепочке суффиксных ссылок, мы делаем оставшиеся вставки, active_length может только уменьшаться, и количество корректировок активной точки, которые мы можем сделать на пути, не может быть больше, чем active_length в любой момент времени. поскольку active_length никогда не может быть больше чем remainder, а также remainder O (n) не только на каждом шаге, но и общая сумма приращений, когда-либо сделанных remainder в течение всего процесса также O(n), число корректировок активной точки также ограничено O(n).

Источник

Я попытался внедрить Суффикс-дерево с помощью подхода, приведенного в ответе Джогожапана, но в некоторых случаях это не сработало из-за формулировок, используемых для правил. Более того, я упомянул, что никому не удалось реализовать абсолютно правильное суффиксное дерево с использованием этого подхода. Ниже я напишу "обзор" ответа джогоджапана с некоторыми изменениями в правилах. Я также опишу случай, когда мы забываем создавать важные суффиксные ссылки.

Используются дополнительные переменные

  1. активная точка - тройка (active_node; active_edge; active_length), показывающая, откуда мы должны начать вставлять новый суффикс.
  2. остаток - показывает количество суффиксов, которые мы должны добавить явно. Например, если наше слово "abcaabca", а остаток = 3, это означает, что мы должны обработать 3 последних суффикса: bca, ca и a.

Давайте используем концепцию внутреннего узла - все узлы, кроме корневого и конечного, являются внутренними узлами.

Наблюдение 1

Когда будет найдено, что последний суффикс, который нам нужно вставить, уже существует в дереве, само дерево вообще не изменяется (мы только обновляем active point а также remainder).

Наблюдение 2

Если в какой-то момент active_length больше или равно длине текущего ребра (edge_length), мы двигаем наши active point вниз до edge_length строго больше, чем active_length,

Теперь давайте переопределим правила:

Правило 1

Если после вставки из активного узла = rootактивная длина больше 0, то:

  1. активный узел не изменен
  2. активная длина уменьшается
  3. активное ребро смещено вправо (к первому символу следующего суффикса мы должны вставить)

Правило 2

Если мы создадим новый внутренний узел ИЛИ создадим вставку из внутреннего узла, и это не первый внутренний узел SUCH на текущем шаге, то мы свяжем предыдущий узел SUCH с ЭТИМ через суффиксную ссылку.

Это определение Rule 2 отличается от jogojapan', так как здесь мы учитываем не только вновь созданные внутренние узлы, но и внутренние узлы, из которых мы делаем вставку.

Правило 3

После вставки из активного узла, который не является корневым узлом, мы должны перейти по ссылке суффикса и установить активный узел на узел, на который он указывает. Если нет ссылки на суффикс, установите активный узел в качестве корневого узла. В любом случае, активный край и активная длина остаются неизменными.

В этом определении Rule 3 мы также рассматриваем вставки листовых узлов (не только сплит-узлов).

И наконец, Наблюдение 3:

Когда символ, который мы хотим добавить к дереву, уже на краю, мы, согласно Observation 1только обновление active point а также remainder, оставляя дерево без изменений. НО, если есть внутренний узел, помеченный как нуждающийся в суффиксной ссылке, мы должны соединить этот узел с нашим текущим active node через суффиксную ссылку.

Давайте рассмотрим пример дерева суффиксов для cdddcdc, если мы добавим ссылку на суффикс в таком случае и если мы этого не сделаем:

  1. Если мы НЕ соединяем узлы через суффиксную ссылку:

    • перед добавлением последней буквы c:

    • после добавления последней буквы c:

  2. Если мы действительно подключим узлы через суффиксную ссылку:

    • перед добавлением последней буквы c:

    • после добавления последней буквы c:

Похоже, что нет существенной разницы: во втором случае есть еще две суффиксные ссылки. Но эти суффиксные ссылки верны, и одна из них - от синего до красного - очень важна для нашего подхода с активной точкой. Проблема в том, что если мы не добавим здесь суффиксную ссылку, позже, когда мы добавим несколько новых букв в дерево, мы могли бы пропустить добавление некоторых узлов в дерево из-за Rule 3, потому что, согласно этому, если нет суффиксной ссылки, то мы должны поставить active_node в корень.

Когда мы добавляли последнюю букву к дереву, красный узел уже существовал до того, как мы сделали вставку из синего узла (ребро помечено как 'c'). Поскольку из синего узла была вставка, мы помечаем ее как нужную суффиксную ссылку. Затем, опираясь на подход активной точки, active node был установлен на красный узел. Но мы не делаем вставку из красного узла, так как буква "с" уже на краю. Означает ли это, что синий узел должен быть оставлен без суффиксной ссылки? Нет, мы должны соединить синий узел с красным через суффиксную ссылку. Почему это правильно? Поскольку подход с активной точкой гарантирует, что мы попадем в нужное место, т. Е. В следующее место, где мы должны обработать вставку с более коротким суффиксом.

Наконец, вот мои реализации дерева суффиксов:

  1. Джава
  2. C++

Надеюсь, что этот "обзор" в сочетании с подробным ответом jogojapan поможет кому-то реализовать свое собственное Suffix Tree.

Источник

Извиняюсь, если мой ответ кажется излишним, но я недавно реализовал алгоритм Укконена и столкнулся с ним в течение нескольких дней; Мне пришлось прочитать несколько статей на эту тему, чтобы понять, почему и как некоторые основные аспекты алгоритма.

Я нашел подход "правил" предыдущих ответов бесполезным для понимания основных причин, поэтому я написал все ниже, сосредоточив внимание исключительно на прагматике. Если вы боролись с другими объяснениями, как и я, возможно, мое дополнительное объяснение заставит вас "щелкнуть".

Я опубликовал свою реализацию C# здесь: https://github.com/baratgabor/SuffixTree

Обратите внимание, что я не специалист по этому вопросу, поэтому следующие разделы могут содержать неточности (или еще хуже). Если вы столкнулись с любой, не стесняйтесь редактировать.

Предпосылки

Исходная точка следующего объяснения предполагает, что вы знакомы с содержанием и использованием деревьев суффиксов, а также с характеристиками алгоритма Укконена, например, как вы расширяете дерево суффиксов символ за символом, от начала до конца. По сути, я предполагаю, что вы уже читали некоторые другие объяснения.

(Тем не менее, мне пришлось добавить некоторые основные повествования для потока, так что начало действительно может показаться излишним.)

Самая интересная часть - это объяснение разницы между использованием суффиксных ссылок и повторным сканированием из корня. Это то, что дало мне много ошибок и головных болей в моей реализации.

Открытые конечные узлы и их ограничения

Я уверен, что вы уже знаете, что самым фундаментальным "трюком" является осознание того, что мы можем просто оставить конец суффиксов "открытым", то есть ссылаться на текущую длину строки вместо того, чтобы устанавливать конец в статическое значение. Таким образом, когда мы добавляем дополнительные символы, эти символы будут неявно добавляться ко всем меткам суффиксов без необходимости посещать и обновлять их все.

Но это открытое окончание суффиксов - по очевидным причинам - работает только для узлов, которые представляют конец строки, то есть листовых узлов в древовидной структуре. Операции ветвления, которые мы выполняем в дереве (добавление новых узлов ветвления и конечных узлов), не будут распространяться автоматически везде, где это необходимо.

Вероятно, это элементарно и не требует упоминания, что повторяющиеся подстроки не появляются явно в дереве, поскольку дерево уже содержит их, поскольку они являются повторениями; однако, когда повторяющаяся подстрока заканчивается встречным неповторяющимся символом, нам нужно создать разветвление в этой точке, чтобы представить расхождение с этой точки и далее.

Например, в случае строки "ABCXABCY" (см. Ниже), ветвление к X и Y необходимо добавить к трем различным суффиксам, ABC, BC и C; иначе это не было бы действительным деревом суффиксов, и мы не могли бы найти все подстроки строки, сопоставляя символы от корня вниз.

Еще раз, чтобы подчеркнуть - любая операция, которую мы выполняем с суффиксом в дереве, должна также отражаться его последовательными суффиксами (например, ABC > BC > C), в противном случае они просто перестают быть действительными суффиксами.

Но даже если мы примем, что мы должны выполнить эти обновления вручную, как мы узнаем, сколько суффиксов нужно обновить? Поскольку, когда мы добавляем повторяющийся символ A (и остальные повторяющиеся символы подряд), мы еще не знаем, когда и где нам нужно разделить суффикс на две ветви. Необходимость разделения определяется только тогда, когда мы сталкиваемся с первым неповторяющимся символом, в данном случае Y (вместо X, который уже существует в дереве).

Что мы можем сделать, это сопоставить самую длинную повторяющуюся строку и посчитать, сколько суффиксов нам нужно обновить позже. Это то, что означает "остаток".

Понятие "остаток" и "повторное сканирование"

Переменная remainder говорит нам, сколько повторных символов мы добавили неявно, без разветвления; т.е. сколько суффиксов нам нужно посетить, чтобы повторить операцию ветвления, как только мы нашли первый символ, которому мы не можем сопоставить. По сути это равняется тому, сколько символов "глубоко" мы находимся в дереве от его корня.

Итак, оставаясь с предыдущим примером строки ABCXABCY, мы сопоставляем повторяемую часть ABC "неявно", увеличивая remainder каждый раз, что приводит к остатку 3. Затем мы встречаем неповторяющийся символ "Y". Здесь мы разбиваем ранее добавленные ABCX на ABC -> X и ABC -> Y. Тогда мы уменьшаем remainder от 3 до 2, потому что мы уже позаботились о разветвлении ABC. Теперь мы повторяем операцию, сопоставляя последние 2 символа - BC - от корня до точки, где нам нужно разделить, и мы также разделяем BCX на BC -> X и BC -> Y. Опять мы уменьшаем remainder до 1 и повторите операцию; до remainder равно 0. Наконец, нам нужно добавить сам текущий символ (Y) в корень.

Эта операция, следующая за последовательными суффиксами от корня просто для того, чтобы достичь точки, где нам нужно выполнить операцию, называется так называемым "повторным сканированием" в алгоритме Укконена, и, как правило, это самая дорогая часть алгоритма. Представьте себе более длинную строку, в которой вам нужно "повторно сканировать" длинные подстроки на многих десятках узлов (мы обсудим это позже), возможно, тысячи раз.

В качестве решения мы вводим то, что мы называем "суффиксными ссылками".

Концепция "суффиксных ссылок"

Суффиксные ссылки в основном указывают на позиции, которые мы обычно должны "повторно сканировать", поэтому вместо дорогостоящей операции повторного сканирования мы можем просто перейти к связанной позиции, выполнить нашу работу, перейти к следующей связанной позиции и повторять до тех пор, пока больше нет позиций для обновления.

Конечно, один большой вопрос, как добавить эти ссылки. Существующий ответ заключается в том, что мы можем добавлять ссылки, когда вставляем новые узлы ветвления, используя тот факт, что в каждом расширении дерева узлы ветвления естественным образом создаются один за другим в точном порядке, в котором мы должны связать их вместе., Тем не менее, мы должны связать последний созданный узел ветвления (самый длинный суффикс) с ранее созданным, поэтому нам нужно кэшировать последний созданный нами объект, связать его со следующим созданным нами и кэшировать вновь созданный.

Одним из следствий этого является то, что у нас часто нет ссылок на суффиксы, потому что данный узел ветвления только что создан. В этих случаях мы все еще должны вернуться к вышеупомянутому "повторному сканированию" из корня. Вот почему после вставки вы получаете указание либо использовать суффиксную ссылку, либо перейти к корню.

(Или, в качестве альтернативы, если вы храните родительские указатели в узлах, вы можете попытаться проследить за родителями, проверить, есть ли у них ссылка, и использовать ее. Я обнаружил, что это очень редко упоминается, но использование ссылки суффикса не У вас есть несколько возможных подходов, и если вы понимаете основной механизм, вы можете реализовать тот, который наилучшим образом соответствует вашим потребностям.)

Концепция "активной точки"

До сих пор мы обсуждали несколько эффективных инструментов для построения дерева и смутно ссылались на обход по множеству ребер и узлов, но еще не исследовали соответствующие последствия и сложности.

Ранее объясненное понятие "остаток" полезно для отслеживания того, где мы находимся в дереве, но мы должны понимать, что оно не хранит достаточно информации.

Во-первых, мы всегда находимся на определенном ребре узла, поэтому нам нужно хранить информацию о ребрах. Мы будем называть это "активным краем".

Во-вторых, даже после добавления информации о ребрах у нас все равно нет возможности определить позицию, которая находится ниже в дереве и не связана напрямую с корневым узлом. Таким образом, мы должны хранить узел также. Давайте назовем этот "активный узел".

Наконец, мы можем заметить, что "остаток" не подходит для определения позиции на ребре, которое напрямую не связано с корнем, потому что "остаток" - это длина всего маршрута; и мы, вероятно, не хотим беспокоиться о запоминании и вычитании длины предыдущих ребер. Таким образом, нам нужно представление, которое по сути является остатком на текущем ребре. Это то, что мы называем "активной длиной".

Это приводит к тому, что мы называем "активной точкой" - пакетом из трех переменных, которые содержат всю информацию, которую мы должны поддерживать о нашей позиции в дереве:

Active Point = (Active Node, Active Edge, Active Length)

На следующем изображении вы можете наблюдать, как согласованный маршрут ABCABD состоит из 2 символов на ребре AB (от корня) и 4 символов на ребре CABDABCABD (от узла 4) - в результате получается "остаток" из 6 символов. Итак, наша текущая позиция может быть идентифицирована как активный узел 4, активный край C, активная длина 4.

Другая важная роль "активной точки" заключается в том, что она обеспечивает уровень абстракции для нашего алгоритма, то есть части нашего алгоритма могут выполнять свою работу над "активной точкой" независимо от того, находится ли эта активная точка в корне или где-либо еще., Это позволяет легко и просто реализовать использование суффиксных ссылок в нашем алгоритме.

Отличия повторного сканирования от использования суффиксных ссылок

Теперь сложная часть, которая, по моему опыту, может вызвать множество ошибок и головных болей, и которая в большинстве источников плохо объяснена, заключается в разнице в обработке случаев суффиксной ссылки по сравнению с случаями повторного сканирования.

Рассмотрим следующий пример строки "AAAABAAAABAAC":

Вы можете наблюдать выше, как "остаток" от 7 соответствует общей сумме символов от корня, в то время как "активная длина" 4 соответствует сумме совпавших символов от активного края активного узла.

Теперь, после выполнения операции ветвления в активной точке, наш активный узел может содержать или не содержать суффиксную ссылку.

Если имеется суффиксная ссылка: нам нужно только обработать часть "активной длины". "Остаток" не имеет значения, потому что узел, к которому мы переходим через суффиксную ссылку, уже неявно кодирует правильный "остаток", просто благодаря тому, что находится в дереве, где он находится.

Если суффиксная ссылка НЕ ​​присутствует: нам нужно "повторно сканировать" с нуля / root, что означает обработку всего суффикса с самого начала. Для этого мы должны использовать весь "остаток" в качестве основы для повторного сканирования.

Пример сравнения обработки с и без суффиксной ссылки

Рассмотрим, что происходит на следующем шаге примера выше. Давайте сравним, как добиться того же результата - т.е. перейти к следующему суффиксу для обработки - с суффиксной ссылкой и без нее.

Использование суффиксной ссылки

Обратите внимание, что если мы используем суффиксную ссылку, мы автоматически "в нужном месте". Что часто не совсем верно из-за того, что "активная длина" может быть "несовместима" с новой позицией.

В приведенном выше случае, поскольку "active length" равен 4, мы работаем с суффиксом " ABAA", начиная с связанного узла 4. Но после нахождения ребра, соответствующего первому символу суффикса ("A")), мы замечаем, что наша "активная длина" переполняет это ребро на 3 символа. Поэтому мы перепрыгиваем через весь край к следующему узлу и уменьшаем "активную длину" на символы, которые мы использовали при прыжке.

Затем, после того как мы нашли следующее ребро "B", соответствующее уменьшенному суффиксу "BAA ", мы наконец отметили, что длина ребра больше, чем оставшаяся "активная длина" в 3, что означает, что мы нашли правильное место.

Обратите внимание: кажется, что эта операция обычно не называется "повторным сканированием", хотя мне кажется, что это прямой эквивалент повторного сканирования, только с укороченной длиной и начальной точкой без корня.

Использование 'rescan'

Обратите внимание, что если мы используем традиционную операцию "повторного сканирования" (в данном случае притворяясь, что у нас нет суффиксной ссылки), мы начинаем с вершины дерева, с корня, и нам приходится снова идти вниз в нужное место, следуя по всей длине текущего суффикса.

Длина этого суффикса является "остатком", который мы обсуждали ранее. Мы должны поглотить весь этот остаток, пока он не достигнет нуля. Это может (и часто так) включать прыжки через несколько узлов, при каждом прыжке уменьшая остаток на длину ребра, через которое мы прыгнули. Затем, наконец, мы достигаем края, который длиннее, чем наш оставшийся "остаток"; здесь мы устанавливаем активное ребро на заданное ребро, устанавливаем для "активной длины" оставшееся "остаток ", и все готово.

Обратите внимание, однако, что фактическая переменная 'remainder' должна быть сохранена и только уменьшена после каждой вставки узла. Итак, то, что я описал выше, предполагало использование отдельной переменной, инициализированной как "остаток".

Примечания к суффиксным ссылкам и повторному просмотру

1) Обратите внимание, что оба метода приводят к одному и тому же результату. Однако переход по суффиксным ссылкам в большинстве случаев значительно быстрее; Вот и вся логика суффиксных ссылок.

2) Реальные алгоритмические реализации не должны отличаться. Как я упоминал выше, даже в случае использования суффиксной ссылки "активная длина" часто несовместима со связанной позицией, поскольку эта ветвь дерева может содержать дополнительное ветвление. Поэтому, по сути, вам просто нужно использовать "активную длину" вместо "остаток" и выполнять ту же логику повторного сканирования, пока не найдете край, который короче оставшейся длины суффикса.

3) Одно важное замечание, касающееся производительности, заключается в том, что нет необходимости проверять каждый символ во время повторного сканирования. Благодаря тому, как построено правильное дерево суффиксов, мы можем смело предположить, что символы совпадают. Таким образом, вы в основном рассчитывает длины, и единственная потребность в проверке эквивалентности символов возникает, когда мы переходим к новому ребру, поскольку ребра идентифицируются по их первому символу (который всегда уникален в контексте данного узла). Это означает, что логика "повторного сканирования" отличается от логики полного совпадения строк (т. Е. Поиск подстроки в дереве).

4) Описанное здесь оригинальное суффиксное связывание является лишь одним из возможных подходов. Например, NJ Larsson et al. называет этот подход нод-ориентированным сверху вниз и сравнивает его с нодо-ориентированным снизу-вверх и двумя краев-ориентированными вариантами. Разные подходы имеют разные типичные и наихудшие характеристики, требования, ограничения и т. Д., Но обычно кажется, что краевые подходы являются общим улучшением по сравнению с оригиналом.

Источник

@jogojapan вы привели потрясающее объяснение и визуализацию. Но, как заметил @makagonov, в нем отсутствуют некоторые правила, касающиеся установки ссылок на суффиксы. Это хорошо видно при пошаговом переходе от слова "aabaaabb" к http://brenden.github.io/ukkonen-animation/. Когда вы переходите от шага 10 к шагу 11, нет суффиксной связи от узла 5 к узлу 2, но активная точка внезапно перемещается туда.

@makagonov, так как я живу в мире Java, я также пытался следовать вашей реализации, чтобы понять рабочий процесс построения ST, но мне было трудно из-за:

  • объединение ребер с узлами
  • использование указателей индекса вместо ссылок
  • ломает заявления;
  • продолжить заявления;

В итоге я получил такую ​​реализацию на Java, которая, как я надеюсь, более четко отражает все этапы и сократит время обучения для других людей на Java:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}
Источник

Спасибо за хорошо объясненный учебник @jogojapan, я реализовал алгоритм на Python.

Несколько мелких проблем, упомянутых @jogojapan, оказываются более сложными, чем я ожидал, и к ним нужно относиться очень осторожно. Мне потребовалось несколько дней, чтобы сделать мою реализацию достаточно надежной (я полагаю). Проблемы и решения перечислены ниже:

  1. Конец с Remainder > 0 Оказывается, что такая ситуация также может возникнуть на этапе развертывания, а не только в конце всего алгоритма. Когда это происходит, мы можем оставить остаток, actnode, actedge и actlength без изменений, завершить текущий шаг развертывания и начать другой шаг, продолжая складывать или разворачивать в зависимости от того, находится ли следующий символ в исходной строке на текущем пути или не.

  2. Перепрыгивание через узлы: когда мы переходим по суффиксной ссылке, обновляем активную точку, а затем обнаруживаем, что ее компонент active_length плохо работает с новым active_node. Мы должны двигаться вперед в нужное место, чтобы разделить или вставить лист. Этот процесс может быть не таким простым, потому что во время перемещения длина акта и актига постоянно меняются, когда вам нужно вернуться к корневому узлу, актедж и длина акта могут быть неправильными из-за этих движений. Нам нужны дополнительные переменные для хранения этой информации.

Две другие проблемы были как-то указаны @managonov

  1. Расщепление может вырваться При попытке разбить ребро, иногда вы обнаружите, что операция расщепления находится прямо на узле. В этом случае нам нужно только добавить новый лист к этому узлу, принять его как стандартную операцию разбиения ребер, что означает, что ссылки на суффиксы, если они есть, должны поддерживаться соответственно.

  2. Скрытые суффиксные ссылки Существует еще один особый случай, связанный с проблемой 1 и проблемой 2. Иногда нам нужно перепрыгнуть через несколько узлов в правильную точку для разделения, мы можем превзойти правильную точку, если мы будем двигаться, сравнивая оставшуюся строку и метки пути. В этом случае ссылка на суффикс будет непреднамеренно игнорироваться, если таковая будет. Этого можно избежать, если вспомнить правильную точку при движении вперед. Суффиксная ссылка должна сохраняться, если разделенный узел уже существует, или даже проблема 1 возникает на этапе развертывания.

Наконец, моя реализация в Python выглядит следующим образом:

Советы: в приведенный выше код включена функция печати наивного дерева, что очень важно при отладке. Это сэкономило мне много времени и удобно для поиска особых случаев.

Источник

Моя интуиция заключается в следующем:

После k итераций основного цикла вы создали дерево суффиксов, которое содержит все суффиксы всей строки, начинающиеся с первых k символов.

В начале это означает, что дерево суффиксов содержит один корневой узел, представляющий всю строку (это единственный суффикс, который начинается с 0).

После длинных (строковых) итераций у вас есть дерево суффиксов, которое содержит все суффиксы.

Во время цикла ключ является активной точкой. Я предполагаю, что это представляет самую глубокую точку в дереве суффиксов, которая соответствует правильному суффиксу первых k символов строки. (Я думаю, что правильно означает, что суффикс не может быть всей строкой.)

Например, предположим, что вы видели символы "abcabc". Активная точка будет представлять точку в дереве, соответствующую суффиксу "abc".

Активная точка представлена ​​(начало, начало, конец). Это означает, что вы в данный момент находитесь в той точке дерева, к которой вы попадаете, начиная с начала узла и затем вводя символы в строке [first: last]

Когда вы добавляете нового персонажа, вы смотрите, находится ли активная точка в существующем дереве. Если это так, то все готово. В противном случае вам нужно добавить новый узел к дереву суффиксов в активной точке, вернуться к следующему кратчайшему совпадению и проверить снова.

Примечание 1. Указатели суффиксов дают ссылку на следующее кратчайшее совпадение для каждого узла.

Примечание 2: Когда вы добавляете новый узел и запасной вариант, вы добавляете новый суффиксный указатель для нового узла. Пункт назначения для этого указателя суффикса будет узлом в сокращенной активной точке. Этот узел либо уже существует, либо будет создан на следующей итерации этого резервного цикла.

Примечание 3: Канонизация просто экономит время при проверке активной точки. Например, предположим, что вы всегда использовали origin=0 и просто меняли первый и последний. Чтобы проверить активную точку, вам придется каждый раз следовать дереву суффиксов по всем промежуточным узлам. Имеет смысл кэшировать результат следования по этому пути, записывая только расстояние от последнего узла.

Можете ли вы привести пример кода, который вы подразумеваете под "исправлением" ограничивающих переменных?

Предупреждение о вреде для здоровья: я также нашел этот алгоритм особенно трудным для понимания, поэтому, пожалуйста, поймите, что эта интуиция, вероятно, будет неправильной во всех важных деталях

Источник

Привет, я пытался реализовать вышеописанную реализацию в ruby, пожалуйста, проверьте это. кажется, работает нормально.

единственное отличие в реализации состоит в том, что я пытался использовать объект края вместо использования только символов.

его также присутствует на https://gist.github.com/suchitpuri/9304856

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder

    def initialize
        @root = Edge.new nil
        @active_point = { active_node: @root , active_edge: nil , active_length: 0}
        @remainder = 0
        @pending_prefixes = []
        @last_split_edge = nil
        @remainder = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_length = @active_point[:active_length]

            # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] ==  @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
            #   @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
            #   @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
            # end

            if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length]  )
                @active_point[:active_node] =  @active_point[:active_edge]
                @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
                @active_point[:active_length] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @active_point[:active_node].find_edge(element[0]) != nil)
            @active_point[:active_length] = @active_point[:active_length] + 1               
            @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
            @remainder = @remainder + 1
            return
        end



        @pending_prefixes.each_with_index do |pending_prefix , index|

            # binding.pry           

            if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

                @active_point[:active_node].edges << Edge.new(element)

            else

                @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge]  == nil

                data = @active_point[:active_edge].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @active_point[:active_edge].data
        @remainder.times do |ctr|
                @pending_prefixes << data[-(ctr+1)..data.length-1]
        end

        @pending_prefixes.reverse!

    end

    def split_edge data , index , element
        location = @active_point[:active_length]
        old_edges = []
        internal_node = (@active_point[:active_edge].edges != nil)

        if (internal_node)
            old_edges = @active_point[:active_edge].edges 
            @active_point[:active_edge].edges = []
        end

        @active_point[:active_edge].data = data[0..location-1].join                 
        @active_point[:active_edge].edges << Edge.new(data[location..data.size].join)


        if internal_node
            @active_point[:active_edge].edges << Edge.new(element)
        else
            @active_point[:active_edge].edges << Edge.new(data.last)        
        end

        if internal_node
            @active_point[:active_edge].edges[0].edges = old_edges
        end


        #setup the suffix link
        if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data 

            @last_split_edge.suffix_link = @active_point[:active_edge] 
        end

        @last_split_edge = @active_point[:active_edge]

        update_active_point index

    end


    def update_active_point index
        if(@active_point[:active_node] == @root)
            @active_point[:active_length] = @active_point[:active_length] - 1
            @remainder = @remainder - 1
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry
Источник
Другие вопросы по тегам