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

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

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

Итак, оставаясь с предыдущим примером строки ABCXABCY , мы сопоставляем повторяемую часть ABC «неявно», увеличивая remainder каждый раз, что приводит к остатку 3.

Затем мы встречаем неповторяющийся символ «Y» . Здесь мы разбиваем ранее добавленные ABCX на ABC -{amp}gt; X и ABC -{amp}gt; Y. Затем мы уменьшаем remainder с 3 до 2, потому что мы уже позаботились о разветвлении ABC .

Теперь мы повторяем операцию, сопоставляя последние 2 символа — BC — от корня до точки, где нам нужно разделить, и мы также разделяем BCX на BC -{amp}gt; X и BC -{amp}gt; Y.

Снова уменьшаем remainder до 1 и повторяем операцию; пока remainder станет 0. Наконец, нам нужно добавить сам текущий символ ( Y ) в корень.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Понравилась статья? Поделиться с друзьями:
JavaScript & TypeScript
Adblock
detector