string - языка - Алгоритм дерева суффикса Ukkonen на простом английском языке




сайты для изучения английского языка для детей (4)

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

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

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

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

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

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

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

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

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

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

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

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

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

https://code.i-harness.com

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

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

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

Мое основное понимание, до сих пор:

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

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

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

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

Вот законченный исходный код 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 edge до ab
  • вставка одного нового края для b

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

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

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

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

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

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

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

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

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

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

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

abcabxabcd

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

Шаги с 1 по 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 до ab .
  • И нам нужно вставить новый конечный край b .

На практике это означает, что мы переходим к активной точке (которая указывает на то, что теперь находится на краю 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 край abcabx и abcabx внутренний узел:

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

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

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

  • active_node остается root
  • 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,'\0x',0) . Здесь я использую node1 для обозначения внутреннего узла, на котором заканчивается край ab .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Итак, какова сложность всего алгоритма? Если текст имеет 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 2 ), поскольку на каждом шаге remainder обычно равен O (n), а пост-корректировки на активном узле после ссылки на суффикс могут также быть O (n)?

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


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

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

  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 пор, пока edge_length будет строго больше, чем active_length .

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

Правило 1

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

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

Правило 2

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

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

Правило 3

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

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

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

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

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

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

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

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

  2. Если мы подключим узлы через ссылку суффикса:

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

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

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

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

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

  1. Java
  2. C++

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


@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);
        }
    });
  }
}




suffix-tree