Рубрики

Построение Суффикса Укконена — Часть 3

Эта статья является продолжением следующих двух статей:
Построение суффикс-дерева Укконена — часть 1
Построение Суффикса Укконена — Часть 2

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

Здесь мы возьмем строку S = «abcabxabcd» в качестве примера, пройдемся по всем шагам и создадим дерево.
Мы добавим $ (обсуждается в части 1, почему мы это делаем), чтобы строка S была «abcabxabcd $».

При построении дерева суффиксов для строки S длиной m:

  • Будет m фаз от 1 до m (одна фаза для каждого персонажа)
    В нашем текущем примере m равно 11, поэтому будет 11 фаз.
  • Первая фаза добавит первый символ «a» в дереве, вторая фаза добавит второй символ «b» в дереве, третья фаза добавит третий символ «c» в дереве, ……, m- я фаза добавит m- й символ в дереве (Это делает алгоритм Укконена онлайн-алгоритмом)
  • Каждую фазу я буду проходить через самое большее i расширений (от 1 до i). Если текущий символ, добавляемый в дерево, пока не виден, все расширения i будут завершены (правило 3 расширений не будет применяться на этом этапе). Если текущий символ, добавляемый в дерево, уже виден ранее, то фаза i завершится раньше (как только будет применено правило 3 расширения), не пройдя все i расширения.
  • Существует три правила расширения (1, 2 и 3), и каждое расширение j (от 1 до i) любой фазы i будет придерживаться одного из этих трех правил.
  • Правило 1 добавляет нового персонажа на существующий край листа
  • Правило 2 создает новый край листа (а также может создавать новый внутренний узел, если метка пути заканчивается между краем)
  • Правило 3 заканчивает текущую фазу (когда текущий символ найден в текущем ребре, проходящем через него)
  • Фаза 1 будет читать первый символ из строки, будет проходить через 1 расширение.
    (На рисунках мы показываем символы на метках ребер только для пояснения, при написании кода мы будем использовать только начальный и конечный индексы — сжатие меток краев, обсуждаемое в части 2 )
    Расширение 1 добавит суффикс «а» в дереве. Мы начинаем с корневого и обходного пути с меткой «а». Там нет пути от корня, выходящего с меткой «а», поэтому создайте край листа (Правило 2).

    Этап 1 завершается завершением расширения 1 (поскольку этап i имеет не более i расширений)
    Для любой строки у Фазы 1 будет только одно расширение, и оно всегда будет следовать Правилу 2.

  • Фаза 2 будет читать второй символ, пройдет как минимум 1 и максимум 2 расширения.
    В нашем примере фаза 2 будет читать второй символ «b». Суффиксами для добавления являются «ab» и «b».
    Расширение 1 добавляет суффикс «ab» в дереве.
    Путь для метки «a» заканчивается на краю листа, поэтому добавьте «b» в конце этого края.
    Расширение 1 просто увеличивает конечный индекс на 1 (от 1 до 2) на первом ребре (Правило 1).

    Расширение 2 добавляет суффикс «b» в дереве. Там нет пути от корня, выходящего с меткой «b», поэтому создает край листа (Правило 2).

    Этап 2 завершается завершением расширения 2.
    Этап 2 прошел через два расширения здесь. Правило 1, применяемое в 1-м Расширении, и Правило 2, применяемое во 2-м Расширении.

  • Фаза 3 будет читать третий символ, пройдет как минимум 1 и максимум 3 расширения.
    В нашем примере фаза 3 будет читать третий символ «с». Суффиксами для добавления являются «abc», «bc» и «c».
    Расширение 1 добавляет суффикс «abc» в дерево.
    Путь для метки 'ab' заканчивается на краю листа, поэтому добавьте 'c' в конце этого края.
    Расширение 1 просто увеличивает конечный индекс на 1 (от 2 до 3) на этом ребре (Правило 1).

    Расширение 2 добавляет суффикс «bc» в дерево.
    Путь для метки «b» заканчивается на краю листа, поэтому добавьте «c» в конце этого края.
    Расширение 2 просто увеличивает конечный индекс на 1 (с 2 до 3) на этом ребре (Правило 1).

    Расширение 3 добавляет суффикс «c» в дереве. Там нет пути от корня, идущего с меткой 'c', поэтому создает край листа (Правило 2).

    Этап 3 завершается завершением расширения 3.
    Этап 3 прошел три расширения здесь. Правило 1, примененное в первых двух расширениях, и правило 2, примененное в третьем расширении.

  • Фаза 4 будет читать четвертый символ, перейдет как минимум к 1 и максимум к 4 расширениям.
    В нашем примере фаза 4 будет читать четвертый символ «а». Суффиксами, которые нужно добавить, являются «abca», «bca», «ca» и «a».
    Расширение 1 добавляет суффикс «abca» в дереве.
    Путь для надписи «abc» заканчивается на краю листа, поэтому добавьте «a» в конце этого края.
    Расширение 1 просто увеличивает конечный индекс на 1 (с 3 до 4) на этом ребре (Правило 1).

    Расширение 2 добавляет суффикс «bca» в дереве.
    Путь для метки 'bc' заканчивается на краю листа, поэтому добавьте 'a' в конце этого края.
    Расширение 2 просто увеличивает конечный индекс на 1 (с 3 до 4) на этом ребре (Правило 1).

    Расширение 3 добавляет суффикс «ca» в дереве.
    Путь для метки «c» заканчивается на краю листа, поэтому добавьте «a» в конце этого края.
    Расширение 3 просто увеличивает конечный индекс на 1 (с 3 до 4) на этом ребре (Правило 1).

    Расширение 4 добавляет суффикс «а» в дереве.
    Путь для метки «а» существует в дереве. Больше не нужно работать, и фаза 4 заканчивается здесь (правило 3 и уловка 2). Это пример неявного суффиксного дерева. Здесь суффикс «а» явно не виден (потому что он не заканчивается у края листа), но он неявно присутствует в дереве. Таким образом, после расширения 4 не происходит никаких изменений в древовидной структуре. Оно останется таким же, как на рисунке 28.
    Фаза 4 завершается, как только Правило 3 применяется в то время как Расширение 4.
    Этап 4 прошел четыре расширения здесь. Правило 1, примененное в первых трех расширениях, и правило 3, применяемое в четвертом расширении.

Теперь мы увидим немного наблюдений и как их реализовать.

  1. В конце любой фазы i существует не более i ребер листа (если i- й символ не виден до сих пор, будут i ребра листа, иначе будет меньше, чем i ребра листа).
    Например, после фаз 1, 2 и 3 в нашем примере, соответственно, есть 1, 2 и 3 ребра листа, но после фазы 4 есть только 3 ребра листа (не 4).
  2. После завершения фазы i «конечными» индексами всех ребер листа являются i. Как мы реализуем это в коде? Нужно ли нам перебирать все эти расширения, находить концы листьев, перемещаясь от корня к листу и увеличивая индекс «конец»? Ответ «НЕТ».
    Для этого мы сохраним глобальную переменную (скажем, «END») и просто увеличим глобальную переменную «END», и все конечные индексы будут указывать на эту глобальную переменную. Таким образом, если у нас есть j листовых ребер после фазы i, то в фазе i + 1 первые j расширений (от 1 до j) будут выполнены путем простого увеличения переменной «END» на 1 (END будет i + 1 в точка).
    Здесь мы только что реализовали трюк 3 — Однажды лист, всегда лист . Этот трюк обрабатывает все ребра j-листа (т. Е. От 1 до j), используя правило 1, за постоянное время в любой фазе. Правило 1 не будет применяться к последующим расширениям на том же этапе. Это можно проверить в четырех фазах, которые мы обсуждали выше. Если вообще Правило 1 применяется в какой-либо фазе, оно применяется только в начальных нескольких фазах непрерывно (скажем, от 1 до j). Правило 1 никогда не применяется позднее на данном этапе, если на этом этапе применяется правило 2 или правило 3.
  3. В приведенном выше примере в каждом расширении (где трюк 3 не применяется) любой фазы для добавления суффикса в дерево мы выполняем обход от корня путем сопоставления меток пути с добавляемым суффиксом. Если после фазы i есть j листовых ребер, то в фазе i + 1 первые j расширений будут следовать правилу 1 и будут выполняться в постоянное время с использованием трюка 3. Есть i + 1-j расширения, которые еще предстоит выполнить. Для этих расширений, с какого узла (корневого или другого внутреннего узла) начинать и с какого пути идти? Ответ на это зависит от того, как завершен предыдущий этап.
    Если на предыдущем этапе я прошел все расширения i (когда i- й символ пока уникален), то на следующем этапе i + 1 трюк 3 позаботится сначала о суффиксах i (ребра i-листа), а затем о расширении i + 1. начнется с корневого узла и вставит в дерево только один символьный суффикс [(i + 1) th ], создав край листа с помощью правила 2.
    Если предыдущий этап i завершается раньше (и это произойдет, если и только если применяется правило 3 — когда i- й символ уже виден ранее), скажем, при j- м расширении (то есть правило 3 применяется при j- м расширении), то есть j -1 край листа пока.
    Мы изложим еще несколько фактов (которые могут быть повторением, но мы хотим убедиться, что это ясно для вас на данном этапе) здесь, основываясь на обсуждении до сих пор:
    • Этап 1 начинается с Правила 2, все остальные этапы начинаются с Правила 1
    • Любая фаза заканчивается либо правилом 2, либо правилом 3
    • Любая фаза i может проходить через серию j расширений (1 <= j <= i). В этих j расширениях первые p (0 <= p <i) будут следовать правилу 1, следующие q (0 <= q <= ip) будут следовать правилу 2, а следующие r (0 <= r <= 1) расширения будет следовать правилу 3. Порядок, в котором применяются правило 1, правило 2 и правило 3, никогда не смешивается в фазе. Они применяются в порядке их количества (если вообще применяются), то есть на этапе, правило 1 применяется 1-е, затем правило 2, а затем правило 3
    • В фазе i p + q + r <= i
    • В конце любой фазы i будут ребра листа p + q, а следующая фаза i + 1 пройдет правило 1 для первых расширений p + q

    На следующем этапе i + 1, уловка 3 (Правило 1) позаботится о первых суффиксах j-1 (ребра листа j-1), затем начнется расширение j, где мы добавим j- й суффикс в дерево. Для этого нам нужно найти наилучший из возможных подходящих ребер, а затем добавить новый символ в конце этого ребра. Как найти конец лучшего подходящего края? Нужно ли переходить от корневого узла и сопоставлять края дерева с j- ным суффиксом, добавляемым символ за символом? Это займет время, и общий алгоритм не будет линейным. На помощь приходит activePoint.
    На предыдущей фазе i, в то время как j- е расширение, обход пути заканчивался в точке (которая может быть внутренним узлом или некоторой точкой в середине ребра), где i- й добавляемый символ был найден в дереве, и применялось правило 3, j го расширение фазы I + 1 начнет именно с той же точки , и мы начинаем соответствующий путь к (I + 1) -го символа. ActivePoint помогает избежать ненужного обхода пути от корня в любом расширении на основе знаний, полученных в обходах, сделанных в предыдущем расширении. В расширениях 1- го параграфа, где применяется правило 1, обход не требуется. Обход выполняется там, где применяется правило 2 или правило 3, и именно там activePoint указывает начальную точку обхода, где мы сопоставляем путь с текущим символом, добавляемым в дерево. Реализация осуществляется таким образом, что в любом расширении, где нам нужен обход, activePoint уже установлен в правильное местоположение (за одним исключением, APCFALZ, обсуждаемым ниже), и в конце текущего расширения мы сбрасываем activePoint как apprppriate, чтобы следующий расширение (той же или следующей фазы), где требуется обход, activePoint уже указывает на правильное место.

    activePoint : это может быть корневой узел, любой внутренний узел или любая точка в середине ребра. Это точка, с которой начинается обход в любом расширении. Для 1-го расширения фазы 1 activePoint установлен как root. Другое расширение получит ActivePoint, правильно установленный предыдущим расширением (за исключением одного случая APCFALZ, обсуждаемого ниже), и текущее расширение несет ответственность за соответствующий сброс ActivePoint в конце, который будет использоваться в следующем расширении, где применяется Правило 2 или Правило 3 ( того же или следующего этапа).
    Для этого нам нужен способ хранения ActivePoint. Мы будем хранить это, используя три переменные: activeNode , activeEdge , activeLength .
    activeNode : это может быть корневой узел или внутренний узел.
    activeEdge : когда мы находимся на корневом узле или на внутреннем узле и нам нужно идти вниз, нам нужно знать, какое ребро выбрать. ActiveEdge будет хранить эту информацию. В случае, если сам activeNode является точкой, откуда начинается обход, тогда activeEdge будет установлен на следующий символ, обрабатываемый в следующей фазе.
    activeLength : сообщает, сколько символов нам нужно пройти (по пути, представленному activeEdge) от activeNode, чтобы достичь activePoint, где начинается обход. В случае, если сам activeNode является точкой, с которой начинается обход, тогда activeLength будет нулевым.

    После фазы i, если есть j листовых ребер, то в фазе i + 1 первые j расширений будут выполнены с помощью трюка 3. ActivePoint потребуется для расширений от j + 1 до i + 1, и activePoint может изменяться или не изменяться между два расширения в зависимости от того, где заканчивается предыдущее расширение.

    Изменение activePoint для правила расширения 3 (APCFER3) : если правило 3 применяется на любой фазе i, то перед тем, как перейти к следующей фазе i + 1, мы увеличиваем activeLength на 1. Нет изменений в activeNode и activeEdge. Почему? Поскольку в случае правила 3 текущий символ из строки S сопоставляется с тем же путем, который представлен текущей activePoint, поэтому для следующего activePoint, activeNode и activeEdge остаются прежними, только activeLenth увеличивается на 1 (из-за сопоставленного символа в текущей фазе ). Эта новая активная точка (тот же узел, тот же край и увеличенная длина) будет использоваться в фазе i + 1.

    Изменение activePoint для перехода вниз (APCFWD) : activePoint может измениться в конце расширения в зависимости от примененного правила расширения. ActivePoint также может измениться во время расширения, когда мы спустимся. Давайте рассмотрим значение activePoint (A, s, 11) на приведенном выше рисунке примера activePoint. Если это activePoint в начале какого-либо расширения, то при переходе от activeNode A будут видны другие внутренние узлы. В любое время, когда мы сталкиваемся с внутренним узлом во время ходьбы, этот узел станет активным узлом (он изменит activeEdge и activeLenght в зависимости от ситуации, так что новая activePoint представляет ту же точку, что и ранее). В этом шаге ниже приведена последовательность изменений в ActivePoint:
    (A, s, 11) — >>> (B, w, 7) — >>> (C, a, 3)
    Все вышеперечисленные три активные точки указывают на одну и ту же точку «с»
    Давайте возьмем другой пример.
    Если activePoint имеет значение (D, a, 11) в начале расширения, то при переходе вниз приведена последовательность изменений в activePoint:
    (D, a, 10) — >>> (E, d, 7) — >>> (F, f, 5) — >> (G, j, 1)
    Все вышеуказанные активные точки относятся к одной и той же точке 'k'.
    Если активными точками являются (A, s, 3), (A, t, 5), (B, w, 1), (D, a, 2) и т. Д., Когда ни один внутренний узел не мешает во время перехода, тогда будет не будет никаких изменений в ActivePoint для APCFWD.
    Идея состоит в том, что в любое время ближайшим внутренним узлом от точки, в которую мы хотим попасть, должна быть activePoint. Почему? Это минимизирует длину прохождения в следующем расширении.

    Изменение activePoint для Active Length ZERO (APCFALZ) : Давайте рассмотрим activePoint (A, s, 0) на приведенном выше примере activePoint. И скажем, текущий символ, обрабатываемый из строки S, это 'x' (или любой другой символ). В начале расширения, когда activeLength равно ZERO, activeEdge устанавливается на текущий обрабатываемый символ, то есть 'x', потому что здесь не требуется переход вниз (поскольку activeLength равно ZERO), и поэтому следующий символ, который мы ищем, является текущим символом обрабатывается.

  4. При реализации кода мы будем последовательно проходить все символы строки S один за другим. Каждый цикл для i- го символа будет выполнять обработку для фазы i. Цикл будет выполняться один или несколько раз в зависимости от того, сколько расширений осталось выполнить (обратите внимание, что на этапе i + 1 нам не обязательно выполнять все расширения i + 1 явно, так как трюк 3 позаботится о j расширений для всех j ребер листьев из предыдущего этапа i). Мы будем использовать переменную ОстальноеSuffixCount , чтобы отслеживать, сколько расширений еще предстоит выполнить явно на любой фазе (после выполнения трюка 3). Кроме того, в конце любой фазы, если оставшийсяSuffixCount равен нулю, это говорит о том, что все суффиксы, которые должны быть добавлены в дерево, добавляются явно и присутствуют в дереве. Если в конце какой-либо фазы оставшийся ненулевой остаток не равен нулю, это говорит о том, что суффиксы такого количества не добавляются явно в дерево (из-за правила 3 мы остановились раньше), но они неявно присутствуют в дереве (такие деревья называются неявное суффиксное дерево). Эти неявные суффиксы будут добавлены явным образом на последующих этапах, когда на пути появится уникальный символ.

Мы продолжим наше обсуждение в части 4 и части 5 . Реализация кода будет обсуждаться в части 6 .

Рекомендации :
http://web.stanford.edu/~mjkay/gusfield.pdf
Алгоритм дерева суффиксов Укконена на простом английском

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

Рекомендуемые посты:

Построение Суффикса Укконена — Часть 3

0.00 (0%) 0 votes