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

Question

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

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

Для справки, вот статья Укконена об алгоритме: 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

Answer 1

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

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

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, нет исходящего ребра, мы вставляем новое ребро:

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

Мы переходим к шагу 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'. Получается out 'c' уже существует на этом краю, поэтому мы устанавливаем активную точку в (node1,'c',1), увеличить remainder и больше ничего не делать.

Теперь в step # = 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,'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 (или п + 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 ² ), потому что на каждом шаге remainder обычно O (n), и пост-корректировки к активному узлу после ссылки суффикса тоже может быть O (n)?

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

Answer 2

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

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

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

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

Наблюдение 1

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

Наблюдение 2

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

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

Правило 1

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

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

Правило 2

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

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

Правило 3

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

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

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

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

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

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

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

   

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

   

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

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

   

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

   

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

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

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

1. Java
2. C ++

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

Answer 3

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

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

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

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

   

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

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

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

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

• Python

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

Answer 4

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

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

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

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

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

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

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

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

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

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

Понятие «активная точка»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если присутствует суффиксная ссылка: Нам нужно только обработать часть 'active length' . 'остаток' не имеет значения, потому что узел, к которому мы переходим через суффиксную ссылку, уже неявно кодирует правильный «остаток» , просто благодаря тому, что находится в дереве, где он находится .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 5

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

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

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

Итак, я закончил с такой реализацией на 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);
        }
    });
  }
}

Answer 6

Моя интуиция такова:

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

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

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

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

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

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

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

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

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

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

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

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

Answer 7

Привет! Я попытался реализовать описанную выше реализацию в 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