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

Ответ 1

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

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

• То, что мы строим, в основном похоже на поисковое трю. Так что является корнем node, края, выходящие из него, приводящие к новым узлам, и другие ребра, выходящие из них, и т.д.

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

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

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

abc

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

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

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

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

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

• расширение существующего a -edge до ab
• вставка одного нового края для b

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

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

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

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

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

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

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

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

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

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

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

abcabxabcd

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

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

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

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

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

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

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

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

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

• не не вставляем свежий край [4,#] в корневой каталог node. Вместо этого мы просто заметим, что суффикс a уже находится в нашем дерево. Он заканчивается в середине более длинного края, но мы не обеспокоенный этим. Мы просто оставляем вещи такими, какие они есть.
• Мы установите для активной точки значение (root,'a',1). Это означает, что точка теперь находится где-то посередине выходящего края корня node, который начинается с 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) (тот же node и край как и раньше, но теперь мы указываем на b)
• Увеличьте remainder до 3, потому что мы все еще не имеем должным образом вставил последний край из предыдущего шага, и мы не вставляем текущий конечный край.

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

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

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

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

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

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

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

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

<Т411 >

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это был последний шаг, и мы закончили. Существует число final наблюдения:

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

Наблюдение 1

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

Наблюдение 2

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

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

Правило 1

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

• active node не изменен
• активная длина уменьшается
• активная граница сдвигается вправо (к первому символу следующего суффикса, который мы должны вставить)

Правило 2

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

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

Правило 3

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

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

И, наконец, Observation 3:

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

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

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

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

• Если мы DO соединяем узлы через суффиксную ссылку:

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

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

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

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

• Java
• С++

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

Ответ 3

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

Ответ 4

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

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

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

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

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

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

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

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

• питон

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

Ответ 5

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 6

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

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

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

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

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

public class ST {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  private static int idGenerator;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 7

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

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

его также присутствует в 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[[email protected]_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 @[email protected]_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

Ответ 8

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

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

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

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

Предпосылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 9

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

active.node = root
active.edge = None
active.length = 0
remainder = 0

for i=0 to length(S): # we work with string S$

    if character of i is next to active point: # we don't need to insert an internal node
            active.length += 1
            remainder += 1
            continue # continue for loop, we go to next phase

    # character of i is not next to active point then we need to insert an internal node

    last_inserted_node = None

    while remainder != 0:

        insert an internal node
        remainder -= 1;

        if last_inserted_node != None: # It is not first internal node created
        create a suffix link from last_inserted_node to new internal node created
    last_inserted_node = new node created   

        if active node == root then:
            # active.node is not changed
            active.length -= 1
            active.edge is shifted right (to the first character of the next suffix we must insert)

        elif active.node has not suffix link: # active.node is not root and has not suffix link
            active.node = root
            # active edge and active length stay unchanged.

        else: # active.node is not root and has suffix link
            We must follow the suffix link and set the active node to the node it points to.
            # active edge and active length stay unchanged.