Рубрики

Построение суффикс-дерева Укконена — часть 4

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

Пожалуйста, просмотрите Часть 1 , Часть 2 и Часть 3 , прежде чем заглянуть в текущую статью, где мы увидели несколько основ дерева суффиксов, алгоритм высокого уровня ukkonen, ссылку на суффикс и три трюка реализации, а также некоторые подробности об ActivePoint вместе с примером строки « abcabxabcd », где мы прошли четыре этапа построения суффиксного дерева.

Давайте вернемся к этим четырем фазам, которые мы уже видели в части 3 , с точки зрения уловки 2, уловки 3 и ActivePoint.

  • activePoint инициализируется как (root, NULL, 0), то есть activeNode является root, activeEdge равен NULL (для простоты понимания мы передаем значение символа для activeEdge, но в реализации кода это будет индекс символа), а activeLength равно ZERO ,
  • Глобальная переменная END и ОстальноеSuffixCount инициализируются в ноль

*********************Фаза 1*************************** ******
На этапе 1 мы читаем 1- й символ (а) из строки S

  • Установите END на 1
  • Увеличьте оставшийсяSuffixCount на 1 (оставшийсяSuffixCount здесь будет равен 1, т. Е. Осталось выполнить 1 расширение)
  • Запустите цикл оставшиеся времена (например, один раз), как показано ниже:
    • Если activeLength равно ZERO, установите activeEdge на текущий символ (здесь activeEdge будет «a»). Это APCFALZ .
    • Проверьте, есть ли ребро, выходящее из activeNode (который является корневым в этой фазе 1) для activeEdge. Если нет, создайте край листа. Если есть, идите вниз. В нашем примере создается край листа (Правило 2).
    • Как только расширение выполнено, уменьшите оставшийсяSuffixCount на 1
    • На данный момент ActivePoint является (root, a, 0)

В конце фазы 1 оставшийсяSuffixCount равен нулю (все суффиксы добавляются явно).
Рисунок 20 в части 3 представляет собой результирующее дерево после фазы 1.

*********************Фаза 2*************************** ******
На этапе 2 мы читаем 2- й символ (b) из строки S

  • Установите END на 2 (это сделает расширение 1)
  • Увеличьте оставшийсяSuffixCount на 1 (оставшийсяSuffixCount здесь будет равен 1, т. Е. Осталось выполнить 1 расширение)
  • Запустите цикл оставшиеся времена (например, один раз), как показано ниже:
    • Если activeLength равно ZERO, установите activeEdge на текущий символ (здесь activeEdge будет «b»). Это APCFALZ .
    • Проверьте, есть ли ребро, выходящее из activeNode (который является корневым в этой фазе 2) для activeEdge. Если нет, создайте край листа. Если есть, идите вниз. В нашем примере создается край листа.
    • Как только расширение выполнено, уменьшите оставшийсяSuffixCount на 1
    • На данный момент ActivePoint является (root, b, 0)

В конце фазы 2 оставшийсяSuffixCount равен нулю (все суффиксы добавляются явно).
Рисунок 22 в части 3 представляет собой результирующее дерево после фазы 2.

********************* Фаза 3 *************************** ******
На этапе 3 мы читаем 3- й символ (с) из строки S

  • Установите END на 3 (это будет делать расширения 1 и 2)
  • Увеличьте оставшийсяSuffixCount на 1 (оставшийсяSuffixCount здесь будет равен 1, т. Е. Осталось выполнить 1 расширение)
  • Запустите цикл оставшиеся времена (например, один раз), как показано ниже:
    • Если activeLength равно ZERO, установите activeEdge на текущий символ (здесь activeEdge будет «c»). Это APCFALZ .
    • Проверьте, есть ли ребро, выходящее из activeNode (который является корневым в этой фазе 3) для activeEdge. Если нет, создайте край листа. Если есть, идите вниз. В нашем примере создается край листа.
    • Как только расширение выполнено, уменьшите оставшийсяSuffixCount на 1
    • На данный момент ActivePoint является (root, c, 0)

В конце фазы 3 оставшийсяSuffixCount равен нулю (все суффиксы добавляются явно).
Рисунок 25 в части 3 представляет собой результирующее дерево после фазы 3.

********************* Фаза 4 *************************** ******
На этапе 4 мы читаем 4- й символ (а) из строки S

  • Установите END на 4 (это будет делать расширения 1, 2 и 3)
  • Увеличьте оставшийсяSuffixCount на 1 (оставшийсяSuffixCount здесь будет равен 1, т. Е. Осталось выполнить 1 расширение)
  • Запустите цикл оставшиеся времена (например, один раз), как показано ниже:
    • Если activeLength равно ZERO, установите activeEdge на текущий символ (здесь activeEdge будет «a»). Это APCFALZ .
    • Проверьте, есть ли ребро, выходящее из activeNode (который является корневым в этой фазе 3) для activeEdge. Если нет, создайте край листа. Если есть, идите вниз (Трюк 1 — пропустить / считать). В нашем примере ребро 'a' присутствует вне activeNode (т.е. root). Нет необходимости идти вниз, так как activeLength <edgeLength. Мы увеличиваем activeLength с нуля до 1 ( APCFER3 ) и прекращаем любую дальнейшую обработку (Правило 3).
    • На этом этапе activePoint имеет значение (root, a, 1), а остальная частьSuffixCount остается равной 1 (без изменений)

В конце фазы 4, Остальная часть Суффикса составляет 1 (один суффикс 'а', последний, не добавляется явно в дерево, но он присутствует в дереве неявно).
Рисунок 28 в Части 3 является результирующим деревом после фазы 4.

Пересмотр завершен в течение 1- го четырех этапов, мы продолжим строить дерево и посмотрим, как оно пойдет.

********************* Фаза 5 *************************** ******
На этапе 5 мы читаем 5- й символ (b) из строки S

  • Установите END на 5 (это будет делать расширения 1, 2 и 3). Смотрите рисунок 29, показанный ниже.
  • Увеличьте оставшийсяSuffixCount на 1 (оставшийся здесь будет равен 2, т. Е. Осталось выполнить 2 расширения, которые являются расширениями 4 и 5. Расширение 4 должно добавить суффикс «ab», а расширение 5 должно добавить суффикс «b» в дерево)
  • Запустите цикл оставшиеся времена (например, два раза), как показано ниже:
    • Проверьте, есть ли ребро, выходящее из activeNode (который является корневым в этой фазе 3) для activeEdge. Если нет, создайте край листа. Если есть, идите вниз. В нашем примере ребро 'a' присутствует вне activeNode (т.е. root).
    • Пройдите назад (трюк 1 — пропустить / посчитать), если это необходимо. В текущей фазе 5 переход вниз не требуется, так как activeLength <edgeLength. Здесь activePoint (root, a, 1) для расширения 4 (ОстальноеSuffixCount = 2)
    • Проверьте, присутствует ли текущий символ строки S (который является 'b') после activePoint. Если да, больше нет обработки (правило 3). То же самое и в нашем примере, поэтому мы увеличиваем activeLength с 1 до 2 ( APCFER3 ) и на этом остановимся (Правило 3).
    • На этом этапе activePoint имеет значение (root, a, 2), а остальная частьSuffixCount остается равной 2 (без изменений в остальной частиSuffixCount)

В конце 5-го этапа оставшийсяSuffixCount равен 2 (два суффикса, 'ab' и 'b', последние два, явно не добавляются в дерево, но неявно находятся в дереве).

********************* Фаза 6 *************************** ******
На этапе 6 мы читаем 6- й символ (x) из строки S

  • Установите END на 6 (это будет делать расширения 1, 2 и 3)
  • Увеличьте оставшийсяSuffixCount на 1 (здесь осталось 3, т. Е. Осталось выполнить 3 расширения, которые являются расширениями 4, 5 и 6 для суффиксов «abx», «bx» и «x» соответственно)
  • Выполните цикл оставшихся раз (например, три раза), как показано ниже:
    • В то время как расширение 4, ActivePoint (root, a, 2) указывает на «b» на ребре, начиная с «a».
    • В расширении 4 текущий символ 'x' из строки S не совпадает со следующим символом на ребре после activePoint, так что это случай правила расширения 2. Таким образом, здесь создается край листа с меткой ребра x. Кроме того, здесь обход заканчивается в середине ребра, поэтому новый внутренний узел также создается в конце activePoint.
    • Уменьшите оставшуюся сумму SuffixCount на 1 (с 3 до 2), добавив в дерево суффикс «abx».

Теперь activePoint изменится после применения правила 2. Три других случая ( APCFER3 , APCFWD и APCFALZ ), где изменения activePoint, уже обсуждались в части 3 .

Изменение activePoint для правила расширения 2 (APCFER2):
Случай 1 (APCFER2C1): если activeNode является root и activeLength больше ZERO , тогда уменьшите activeLength на 1, и activeEdge будет установлен «S [i — оставшийсяSuffixCount + 1]», где i — номер текущей фазы. Вы видите, почему это изменение в ActivePoint? Посмотрите на текущее расширение, которое мы только что обсудили для фазы 6 (i = 6) снова, где мы добавили суффикс «abx». Там activeLength равно 2, а activeEdge равно 'a'. Теперь в следующем расширении нам нужно добавить суффикс «bx» в дереве, то есть метка пути в следующем расширении должна начинаться с «b». Таким образом, «b» (5- й символ в строке S) должен быть активным ребром для следующего расширения, а индекс b будет «i — оставшийсяSuffixCount + 1» (6 — 2 + 1 = 5). activeLength уменьшается на 1, потому что activePoint становится ближе к корню на длину 1 после каждого расширения.
Что произойдет, если activeNode — это root, а activeLength — это ZERO? APCFALZ уже занимается этим делом .

Случай 2 (APCFER2C2): если activeNode не является пользователем root , перейдите по ссылке суффикса из текущего activeNode. Новый узел (который может быть корневым или другим внутренним узлом), на который указывает ссылка с суффиксом, будет активным узлом для следующего расширения. Без изменений в activeLength и activeEdge. Вы видите, почему это изменение в ActivePoint? Это связано с тем, что: если два узла соединены суффиксной ссылкой, то метки на всех путях, идущих вниз от этих двух узлов, начиная с одного и того же символа, будут точно такими же, и поэтому для двух соответствующих одинаковых точек на этих путях activeEdge и activeLength будут будет одинаковым, и два узла будут активным узлом. Посмотрите на рисунок 18 в части 2 . Скажем, в фазе i и расширении j в дереве был добавлен суффикс «xAabcdedg». В этот момент, скажем, activePoint был (Node-V, a, 7), то есть точка «g». Таким образом , для следующего расширения J + 1, мы добавим суффикс «Aabcdefg» и для этого нам нужно пройти 2 — й пути показан на рисунке 18. Это можно сделать с помощью следующей ссылки суффикса из текущей activeNode ст. Суффикс ссылка ведет нас на путь быть пройденным где-то между [Node s (v)], ниже которого путь точно такой же, как он был ниже предыдущего activeNode v. Как сказано ранее, «activePoint становится ближе к корню на длину 1 после каждого расширения», это сокращение по длине будет выше узла s (v), но ниже s (v), никаких изменений не будет. Таким образом, когда activeNode не является корневым в текущем расширении, то для следующего расширения изменяется только activeNode (без изменений в activeEdge и activeLength).

    • На данный момент в расширении 4 текущая активная точка (root, a, 2) и на основе APCFER2C1 , новая активная точка для следующего расширения 5 будет (корневая, b, 1)
    • Следующий добавляемый суффикс — «bx» (с оставшимся SuffixCount 2).
    • Текущий символ 'x' из строки S не совпадает со следующим символом на ребре после activePoint, так что это случай правила расширения 2. Таким образом, здесь создается край листа с меткой ребра x. Кроме того, здесь обход заканчивается в середине ребра, поэтому новый внутренний узел также создается в конце activePoint.
      Суффиксная ссылка также создается от предыдущего внутреннего узла (расширения 4) к новому внутреннему узлу, созданному в текущем расширении 5.
    • Уменьшите оставшуюся сумму SuffixCount на 1 (от 2 до 1), добавив в дерево суффикс «bx».

    • На данный момент в расширении 5 текущая активная точка (root, b, 1) и на основе APCFER2C1 новая активная точка для следующего расширения 6 будет (корневая, х, 0)
    • Следующий добавляемый суффикс — «x» (с оставшимся SuffixCount 1).
    • В следующем расширении 6 символ x не будет соответствовать ни одному существующему ребру из корня, поэтому новое ребро с меткой x будет создано из корневого узла. Также суффиксная ссылка с внутреннего узла предыдущего расширения переходит в корневой каталог (поскольку в текущем расширении 6 новый внутренний узел не создан).
    • Уменьшите оставшийсяSuffixCount на 1 (от 1 до 0), добавив в дерево суффикс «x»

Это завершает фазу 6.
Обратите внимание, что фаза 6 завершила все свои 6 расширений (Почему? Поскольку текущий символ c не был замечен в строке до сих пор, поэтому правило 3, которое останавливает дальнейшие расширения, никогда не получало применения в фазе 6), и поэтому дерево, сгенерированное после Фаза 6 является истинным деревом суффиксов (то есть не неявным деревом) для символов «abcabx», которые были прочитаны до сих пор, и в нем есть все суффиксы в дереве.

При построении дерева выше были замечены следующие факты:

  • Вновь созданный внутренний узел в расширении i указывает на другой внутренний узел или корень (если activeNode является корнем в расширении i + 1) к концу расширения i + 1 через ссылку суффикса (Каждый внутренний узел ДОЛЖЕН иметь ссылку суффикса, указывающую на другой внутренний узел или корень)
  • Суффиксная ссылка обеспечивает короткий путь при поиске конца пути следующего суффикса метки
  • При правильном отслеживании активных точек между расширениями / фазами можно избежать ненужного перехода от root.

Мы пройдем остальные этапы (с 7 по 11) в части 5 и полностью построим дерево, а после этого увидим код для алгоритма в части 6 .

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

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

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

Построение суффикс-дерева Укконена — часть 4

0.00 (0%) 0 votes