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

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

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

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

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

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

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

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

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

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

https://gist.github.com/2373868

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

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

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

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

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

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) места, потому что оно состоит только из двух указателей на текст, независимо от того, сколько символов оно представляет.

Затем мы снова увеличиваем позицию и обновляем дерево, добавляя a 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. Это автоматически обновляет дерево следующим образом:

И поскольку remainder2 , нам нужно вставить два последних суффикса текущей позиции: 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'. Оказывается, «c» уже существует на этом краю, поэтому мы устанавливаем активную точку (node1,'c',1)равной, увеличиваем remainderи ничего больше не делаем.

Теперь на шаге #= 10 , remainderравно 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). Посмотрите на приведенный выше график, чтобы убедиться, что действительно узел at label abсвязан с узлом at b(его суффикс), а узел at 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выход из зеленого узла равен -edge de, поэтому он содержит только 2 символа. Чтобы найти правильную активную точку, нам, очевидно, нужно пройти по этому краю к синему узлу и сбросить на (blue,'f',1).

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

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

Если после вставки от активного узла = корень , то активная длина больше , чем 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.

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

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

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

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

   

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

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

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

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

• питон

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

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

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

Я опубликовал свою реализацию 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'

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

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

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

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

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

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

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

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

@jogojapan вы привели потрясающее объяснение и визуализацию. Но, как заметил @makagonov, в нем отсутствуют некоторые правила, касающиеся установки ссылок на суффиксы. Это хорошо видно, когда вы идете шаг за шагом http://brenden.github.io/ukkonen-animation/ через слово «aabaaabb». При переходе от шага 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);
        }
    });
  }
}

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

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

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

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

Во время цикла ключ является активной точкой. Я предполагаю, что это представляет самую глубокую точку в дереве суффиксов, которая соответствует правильному суффиксу первых 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