Рубрики

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

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

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

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

  • Установите END на 7 (это будет делать расширения 1, 2, 3, 4, 5 и 6) — потому что к концу предыдущей фазы 6 у нас есть 6 ребер листа.

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

В конце 7-го этапа оставшийсяSuffixCount равен 1 (один суффикс 'a', последний, явно не добавляется в дерево, но неявно присутствует в дереве).
На рисунке 33 показано дерево после фазы 7.

********************* Фаза 8 *************************** ******
В фазе 8 мы читаем 8- й символ (b) из строки S

  • Установите END на 8 (это будет делать расширения 1, 2, 3, 4, 5 и 6) — потому что к концу предыдущей фазы 7 у нас есть 6 ребер листа (Рисунок 34).

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

В конце фазы 8, visibleSuffixCount равен 2 (два суффикса, 'ab' и 'b', последние два, явно не добавляются в дереве явно, но они неявно находятся в дереве).

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

  • Установите END на 9 (это будет делать расширения 1, 2, 3, 4, 5 и 6) — потому что к концу предыдущей фазы 8 у нас есть 6 ребер листа.

  • Увеличьте оставшийсяSuffixCount на 1 (здесь осталось 3, т. Е. Осталось выполнить три расширения, которые являются расширениями 7, 8 и 9 для суффиксов 'abc', 'bc' и 'c' соответственно)
  • Выполните цикл оставшихся раз (например, три раза), как показано ниже:
    • Проверьте, есть ли ребро, выходящее из activeNode (который является корневым в этой фазе 9) для activeEdge. Если нет, создайте край листа. Если есть, идите вниз. В нашем примере ребро 'a' присутствует вне activeNode (т.е. root).
    • Пройдите назад (трюк 1 — пропустить / посчитать), если это необходимо. В текущей фазе 9 необходимо пройти как activeLength (2)> = edgeLength (2). Во время перехода activePoint изменяется на (Узел A, c, 0) на основе APCFWD (это первый раз, когда APCFWD применяется в нашем примере).
    • Проверьте, присутствует ли текущий символ строки S (который является 'c') после activePoint. Если да, больше нет обработки (правило 3). То же самое имеет место в нашем примере, поэтому мы увеличиваем activeLength от 0 до 1 ( APCFER3 ) и на этом остановимся (Правило 3).
    • На этом этапе activePoint имеет значение (Узлы A, c, 1), а остальная частьSuffixCount остается равной 3 (без изменений в остающейся точкеSuffixCount)

В конце фазы 9, visibleSuffixCount равен 3 (три суффикса, 'abc', 'bc' и 'c', последние три, явно не добавляются в дереве явно, но они неявно находятся в дереве).

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

  • Установите END на 10 (это будет делать расширения 1, 2, 3, 4, 5 и 6) — потому что к концу предыдущей фазы 9 у нас есть 6 ребер листа.

  • Увеличьте оставшийсяSuffixCount на 1 (здесь осталось 4, т. Е. Осталось выполнить четыре расширения, которые являются расширениями 7, 8, 9 и 10 для суффиксов 'abcd', 'bcd', 'cd' и 'd' соответственно)
  • Запустите цикл оставшиеся времена (например, четыре раза), как показано ниже:
    • ********************* расширение 7 *************************** ******

    • Проверьте, есть ли ребро, выходящее из activeNode (Узел A) для activeEdge (c). Если нет, создайте край листа. Если есть, идите вниз. В нашем примере край 'c' присутствует, выходя из activeNode (Узел A).
    • Пройдите назад (трюк 1 — пропустить / посчитать), если это необходимо. В текущем добавочном номере 7 переход вниз не требуется, так как activeLength <edgeLength.
    • Проверьте, присутствует ли текущий символ строки S (который является 'd') после activePoint. Если нет, то будет применяться правило 2. В нашем примере нет пути, начинающегося с 'd', выходящего из activePoint, поэтому мы создаем край листа с меткой 'd'. Поскольку ActivePoint заканчивается в середине ребра, мы создадим новый внутренний узел сразу после ActivePoint (Правило 2).

      Вновь созданный внутренний узел c (на рисунке выше) в текущем расширении 7 получит свою суффиксную ссылку, установленную в следующем расширении 8 (см. Рисунок 38 ниже).

    • Уменьшите оставшуюся сумму SuffixCount на 1 (с 4 до 3), добавив в дерево суффикс «abcd».
    • Теперь activePoint изменится для следующего расширения 8. Текущий activeNode является внутренним узлом (Node A), поэтому оттуда должна быть ссылка на суффикс, и мы будем следовать этому, чтобы получить новый activeNode, и это будет «Node B». Нет изменений в activeEdge и activeLength (это APCFER2C2 ). Таким образом, новая активная точка (Узел B, C, 1).
    • ********************* Extension 8 *************************** ******

    • Теперь в расширении 8 (здесь мы добавим суффикс «bcd»), при добавлении символа «d» после текущей activePoint будет применяться та же логика, что и в предыдущем расширении 7. В предыдущем расширении 7 мы добавили символ «d» в activePoint ( Узлы A, c, 1) и в текущем расширении 8 мы собираемся добавить тот же символ 'd' в activePoint (Узел B c, 1). Таким образом, логика будет такой же, и здесь у нас будет новый край листа с меткой «d» и новый внутренний узел. И новый внутренний узел (C) предыдущего расширения будет указывать на новый узел (D) текущего расширения через суффиксную ссылку.

      Обратите внимание, что узел C из предыдущего расширения (см. Рис. 37 выше) получил здесь свою суффиксную ссылку, а узел D, созданный в текущем расширении, получит свою суффиксную ссылку, установленную в следующем расширении. Что произойдет, если в следующих расширениях не будет создан новый узел? Мы видели это раньше в Фазе 6 ( Часть 4 ) и увидим снова в последнем продолжении этой Фазы 10. Оставайтесь с нами.

    • Уменьшите оставшуюся сумму SuffixCount на 1 (с 3 до 2), добавив в дерево суффикс «bcd».
    • Теперь activePoint изменится для следующего расширения 9. Текущий activeNode — это внутренний узел (Узел B), поэтому оттуда должна быть ссылка на суффикс, и мы будем следовать этому, чтобы получить новый activeNode и это «Root Node». Нет изменений в activeEdge и activeLength (это APCFER2C2 ). Итак, новая ActivePoint — это (root, c, 1).
    • ********************* расширение 9 *************************** ******

    • Теперь в расширении 9 (здесь мы добавим суффикс «cd»), при добавлении символа «d» после текущей activePoint будет применяться та же логика, что и в предыдущих расширениях 7 и 8. Обратите внимание, что внутренний узел D, созданный в предыдущем расширении 8, теперь указывает на внутренний узел E (созданный в текущем расширении) через суффиксную ссылку.

    • Уменьшите оставшуюся сумму SuffixCount на 1 (от 2 до 1), добавив в дерево суффикс «cd».
    • Теперь activePoint изменится для следующего расширения 10. Текущий activeNode — root, а activeLength — 1, на основе APCFER2C1 , activeNode останется «root», activeLength будет уменьшен на 1 (от 1 до нуля), а activeEdge будет «d». Таким образом, новая активная точка (root, d, 0).
    • ********************* расширение 10 *************************** ******

    • Теперь в расширении 10 (здесь мы добавим суффикс «d»), при добавлении символа «d» после текущей activePoint нет ребра, начинающегося с d, выходящего из корня activeNode, поэтому создается новый край листа с меткой d ( Правило 2). Обратите внимание, что внутренний узел E, созданный в предыдущем расширении 9, теперь указывает на корневой узел через суффиксную ссылку (поскольку новый внутренний узел не создан в этом расширении).

      Внутренний узел, созданный в предыдущем расширении, ожидает установки суффиксной ссылки в следующем расширении, указывает на root, если внутренний узел не создан в следующем расширении. В реализации кода, как только новый внутренний узел (скажем, A) будет создан в расширении j, мы установим его суффиксную ссылку на корневой узел и в следующем расширении j + 1, если правило 2 применяется к существующему или вновь созданному узлу. (Скажем, B) или Правило 3 применяется с некоторым активным узлом (Скажем, B), тогда суффиксная ссылка узла A изменится на новый узел B, в противном случае узел A будет продолжать указывать на корень

    • Уменьшите оставшуюся сумму SuffixCount на 1 (от 1 до 0), добавив в дерево суффикс «d». Это означает, что больше не нужно добавлять суффикс, и фаза 10 заканчивается здесь. Обратите внимание, что это дерево является явным деревом, поскольку все суффиксы добавляются в дерево явно (почему ??, потому что символ d ранее не был виден в строке S)
    • activePoint для следующей фазы 11 — это (root, d, 0).

Мы видим следующие факты в Фазе 10:

  • Внутренние узлы, соединенные через суффиксные ссылки, имеют точно такое же дерево под ними, например, на рисунке 40 выше, A и B имеют одно и то же дерево под ними, аналогично C, D и E имеют одно и то же дерево под ними.
  • Из-за вышеупомянутого факта, в любом расширении, когда текущий activeNode получен через суффиксную ссылку из activeNode предыдущего расширения, тогда в текущем расширении применяется точно такая же логика расширения, как и в предыдущем расширении. (На этапе 10 такая же логика расширения применяется в расширениях 7, 8 и 9)
  • Если новый внутренний узел создается в расширении j любой фазы i, то этот вновь созданный внутренний узел получит свою суффиксную ссылку, установленную к концу следующего расширения j + 1 той же фазы, то есть узел C был создан в расширении 7 фазы 10 (Рисунок 37), и он получил суффиксную ссылку на узел D в расширении 8 той же фазы 10 (рисунок 38). Точно так же узел D был создан в расширении 8 фазы 10 (рисунок 38), и его суффиксная ссылка была установлена на узел E в расширении 9 той же фазы 10 (рисунок 39). Точно так же узел E был создан в расширении 9 фазы 10 (рисунок 39), и его суффиксная ссылка была установлена на root в расширении 10 той же фазы 10 (рисунок 40).
  • Исходя из вышеизложенного, каждый внутренний узел будет иметь суффиксную ссылку на какой-либо другой внутренний узел или корень. Корень не является внутренним узлом, и у него не будет суффиксной ссылки.

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

  • Установите END на 11 (это будет делать расширения с 1 по 10) — потому что к концу предыдущей фазы 10 у нас есть 10 ребер листа.

  • Увеличьте оставшийсяSuffixCount на 1 (от 0 до 1), т.е. в дереве нужно добавить только один суффикс «$».
  • Поскольку activeLength имеет значение ZERO, activeEdge изменится на текущий символ '$' обрабатываемой строки S ( APCFALZ ).
  • Нет ребра, выходящего из корня activeNode, поэтому будет создан ребро листа с меткой '$' (Правило 2).

  • Уменьшите оставшуюся сумму SuffixCount на 1 (от 1 до 0), добавив в дерево суффикс «$». Это означает, что больше не нужно добавлять суффикс, и фаза 11 заканчивается здесь. Обратите внимание, что это дерево является явным деревом, так как все суффиксы добавляются в дерево явно (почему ??, потому что символ $ ранее не был замечен в строке S)

Теперь мы добавили все суффиксы строки 'abcabxabcd $' в дерево суффиксов. В этом дереве 11 концов листа, и метки на пути от корня к концу листа представляют собой один суффикс. Теперь остается только назначить номер (индекс суффикса) каждому концу листа, и этот номер будет начальной позицией суффикса в строке S. Это можно сделать с помощью обхода DFS по дереву. Во время обхода DFS следите за длиной метки и, когда найден конец листа, установите индекс суффикса как «stringSize — labelSize + 1». Индексированное дерево суффиксов будет выглядеть так:

На приведенном выше рисунке индексы суффикса показаны в виде позиции символа, начиная с 1 (индекс не нуля). В реализации кода индекс суффикса будет установлен как индекс с нулем, т.е. где мы видим индекс суффикса j (от 1 до m для строки длины m) на рисунке выше, в реализации кода это будет j-1 (от 0 до m-1). )
И мы сделали !!!!

Структура данных для представления дерева суффиксов

Как представить дерево суффиксов ?? Есть узлы, ребра, метки и суффиксные ссылки и индексы.
Ниже приведены некоторые операции / запросы, которые мы будем выполнять при построении дерева суффиксов, а затем при использовании дерева суффиксов в различных приложениях / использованиях:

  • Какова длина пути метки на каком-нибудь ребре?
  • Что такое метка пути на каком-нибудь ребре?
  • Проверьте, есть ли исходящее ребро для данного символа из узла.
  • Каково значение символа на ребре на некотором заданном расстоянии от узла?
  • Куда указывает внутренний узел через суффиксную ссылку?
  • Что такое индекс суффикса на пути от корня к листу?
  • Проверить, присутствует ли данная строка в дереве суффиксов (как подстрока, суффикс или префикс)?

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

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

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

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

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

0.00 (0%) 0 votes