Рубрики

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

В Построении дерева суффиксов Укконена — часть 1 , мы увидели алгоритм Укконена высокого уровня. Эта 2- я часть является продолжением части 1 .
Пожалуйста, просмотрите Часть 1 , прежде чем смотреть текущую статью.

В Построении дерева суффиксов строки S длиной m имеется m фаз, и для фазы j (1 <= j <= m) мы добавляем j- й символ в построенное дерево, и это делается с помощью j расширений. Все расширения следуют одному из трех правил расширения (обсуждается в части 1 ).

Чтобы сделать j- е расширение фазы i + 1 (добавив символ S [i + 1]), нам сначала нужно найти конец пути от корня, помеченного S [j..i], в текущем дереве. Один из способов — начать с корня и пройти по ребрам, соответствующим строке S [j..i]. Для построения дерева суффиксов потребуется O (м 3 ) времени. Используя несколько наблюдений и приемов реализации, это можно сделать в O (m), который мы увидим сейчас.

Суффикс ссылки
Для внутреннего узла v с меткой пути xA, где x обозначает один символ, а A обозначает подстроку (возможно, пустую), если есть другой узел s (v) с меткой пути A, то указатель от v к s ( v) называется суффиксной ссылкой.
Если A — пустая строка, суффиксная ссылка с внутреннего узла перейдет на корневой узел.
Не будет никакой суффиксной ссылки от корневого узла (поскольку он не считается внутренним узлом).

В расширении j некоторой фазы i, если добавлен новый внутренний узел v с меткой пути xA, то в расширении j + 1 в той же фазе i:

  • Либо путь, помеченный A, уже заканчивается на внутреннем узле (или корневой узел, если A пуст)
  • ИЛИ будет создан новый внутренний узел в конце строки A

В расширении j + 1 той же фазы i мы создадим суффиксную ссылку от внутреннего узла, созданного в j- м расширении, к узлу с путем, помеченным как A.

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

В любом неявном дереве суффиксов T i после фазы i, если внутренний узел v имеет метку пути xA, то в T i есть узел s (v) с меткой пути A, и узел v будет указывать на узел s (v), используя суффиксная ссылка.

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

Как используются суффиксные ссылки для ускорения реализации?
В расширении j фазы i + 1 нам нужно найти конец пути от корня с меткой S [j..i] в текущем дереве. Один из способов — начать с корня и пройти по ребрам, соответствующим строке S [j..i]. Суффиксные ссылки обеспечивают короткий путь для поиска конца пути.

Итак, мы можем видеть, что, чтобы найти конец пути S [j..i], нам не нужно проходить от корня. Мы можем начать с конца пути S [j-1..i], пройти вверх по одному краю к узлу v (т.е. перейти к родительскому узлу), перейти по суффиксной ссылке к s (v), затем пройти по пути y ( который находится здесь на рисунке 17).
Это показывает, что использование суффиксной ссылки является улучшением процесса.
Примечание: в следующей части 3 мы представим ActivePoint, которая поможет избежать «подъема». Мы можем напрямую перейти к узлу s (v) из узла v.

Когда существует суффиксная ссылка от узла v к узлу s (v), то если существует путь, помеченный строкой y, от узла v к листу, то должен быть путь, помеченный строкой y, от узла s (v) к лист. На рисунке 17 есть метка пути «abcd» от узла v к листу, а затем путь будет такой же метки «abcd» от узла s (v) к листу.
Этот факт может быть использован для улучшения перехода от s (v) к листу вдоль пути y. Это называется трюк «пропустить / считать».

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

Используя суффиксную связь вместе с трюком с пропуском / подсчетом, дерево суффиксов может быть построено в O (m 2 ), поскольку существует m фаз, и каждая фаза занимает O (m).

Сжатие краевой метки
Пока что метки пути представлены в виде символов в строке. Такое суффиксное дерево займет O (m 2 ) места для хранения меток пути. Чтобы избежать этого, мы можем использовать две пары индексов (начало, конец) на каждом ребре для меток пути вместо самой подстроки. Индексы start и end указывают начальную и конечную позиции метки пути в строке S. При этом дереву суффиксов требуется пространство O (m).

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

Наблюдение 1: Правило 3 — шоу-стоппер
На этапе i необходимо выполнить i расширений (от 1 до i).
Если правило 3 применяется в любом расширении j фазы i + 1 (т. Е. Путь, помеченный как S [j..i], продолжается с символа S [i + 1]), то оно также будет применяться во всех дальнейших расширениях той же фазы (т.е. расширениях от j + 1 до i + 1 в фазе i + 1). Это потому, что если путь с меткой S [j..i] продолжается с символа S [i + 1], то путь с меткой S [j + 1..i], S [j + 2..i], S [j + 3 ..i],…, S [i..i] также продолжится с символа S [i + 1].
Рассмотрим рисунок 11, рисунок 12 и рисунок 13 в части 1, где применяется правило 3.
На рисунке 11 «xab» добавляется в дерево, а на рисунке 12 (фаза 4) мы добавляем следующий символ «x». В этом 3 расширения сделаны (что добавляет 3 суффикса). Последний суффикс «x» уже присутствует в дереве.
На рисунке 13 мы добавляем символ «а» в дереве (фаза 5). Первые 3 суффикса добавляются в дерево, а последние два суффикса «xa» и «a» уже присутствуют в дереве. Это показывает, что если суффикс S [j..i] присутствует в дереве, то ВСЕ оставшиеся суффиксы S [j + 1..i], S [j + 2..i], S [j + 3..i] ,…, S [i..i] также будет присутствовать в дереве, и для добавления оставшихся суффиксов не требуется никакой работы.
Таким образом, больше нет необходимости выполнять какую-либо работу на каком-либо этапе, как только правило 3 будет применяться при любом продлении на этом этапе. Если новый внутренний узел v создается в расширении j, а правило 3 применяется в следующем расширении j + 1, то нам нужно добавить суффиксную ссылку из узла v в текущий узел (если мы на внутреннем узле) или корневой узел. ActiveNode, который будет обсуждаться в части 3, поможет при настройке суффиксных ссылок.

Трюк 2
Остановите обработку любого этапа, как только правило 3 будет применено. Все дальнейшие расширения уже присутствуют в дереве неявно.

Наблюдение 2: Однажды лист, всегда лист
Как только лист создан и помечен как j (для суффикса, начинающегося в позиции j в строке S), этот лист всегда будет листом в последовательных фазах и расширениях. После того как лист помечен как j, правило расширения 1 всегда будет применяться к расширению j на всех последовательных этапах.
Рассмотрим рисунки с 9 по 14 в части 1 .
На рисунке 10 (этап 2) правило 1 применяется к листу, помеченному 1. После этого на всех последовательных этапах правило 1 всегда применяется к этому листу.
На рисунке 11 (этап 3) правило 1 применяется к листу, помеченному 2. После этого на всех последовательных этапах правило 1 всегда применяется к этому листу.
На рисунке 12 (этап 4) правило 1 применяется к листу, помеченному 3. После этого на всех последовательных этапах правило 1 всегда применяется к этому листу.

На любой фазе i существует начальная последовательность последовательных расширений, где применяется правило 1 или правило 2, а затем, как только правило 3 применяется, этап i заканчивается.
Также правило 2 всегда создает новый лист (и иногда внутренний узел).
Если J i представляет последнее расширение в фазе i, когда было применено правило 1 или 2 (т. Е. После i- й фазы, будут J i- листья, помеченные 1, 2, 3,…, J i ), тогда J i <= J i +1
J i будет равен J i + 1, когда в фазе i + 1 не будет создан новый лист (т.е. правило 3 применяется в расширении J i + 1 )
На рисунке 11 (фаза 3) правило 1 применяется в первых двух расширениях, а правило 2 — в третьем расширении, поэтому здесь J 3 = 3
На рисунке 12 (этап 4) новый лист не создается (правило 1 применяется в 1-м 3 расширениях, а затем правило 3 применяется в 4-м расширении, которое завершает фазу). Здесь J 4 = 3 = J 3
На рисунке 13 (фаза 5) новый лист не создан (правило 1 применяется в 1-м 3 расширениях, а затем правило 3 применяется в 4-м расширении, которое завершает фазу). Здесь J 5 = 3 = J 4
J i будет меньше, чем J i + 1, когда в фазе i + 1 будет создано несколько новых листов.
На рисунке 14 (фаза 6) создан новый лист (правило 1 применяется в первых 3 расширениях, а затем правило 2 применяется в последних 3 расширениях, которые заканчивают фазу). Здесь J 6 = 6> J 5

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

Трюк 3
На любой фазе i ребра листьев могут выглядеть как (p, i), (q, i), (r, i),…. где p, q, r — начальная позиция разных ребер, а i — конечная позиция всех. Тогда в фазе i + 1 эти ребра листьев будут иметь вид (p, i + 1), (q, i + 1), (r, i + 1),…. Таким образом, в каждой фазе конечное положение должно увеличиваться по всем краям листа. Для этого нам нужно пройти через все ребра листа и увеличить конечную позицию для них. Чтобы сделать то же самое в постоянное время, поддержите глобальный индекс e, и e будет равен числу фаз. Таким образом, теперь ребра листа будут выглядеть как (p, e), (q, e), (r, e). На любом этапе будет сделано просто увеличение e и расширение на всех ребрах листа. Рисунок 19 показывает это.

Таким образом, используя суффиксные ссылки и трюки 1, 2 и 3, суффиксное дерево может быть построено за линейное время.

Дерево Tm может быть неявным деревом, если суффикс является префиксом другого. Таким образом, мы можем сначала добавить символ $ Terminal, а затем запустить алгоритм, чтобы получить дерево истинных суффиксов (Дерево истинных суффиксов содержит все суффиксы в явном виде). Чтобы пометить каждый лист соответствующей стартовой позицией суффикса (все листы помечены как глобальный индекс e), на дереве может быть выполнен линейный обход времени.

На этом этапе мы прошли через большинство вещей, которые нам нужно было знать, чтобы создать дерево суффиксов с использованием алгоритма Укконена. В следующей части 3 мы возьмем в качестве примера строку S = «abcabxabcd», шаг за шагом пройдемся по всем вещам и создадим дерево. При построении дерева мы обсудим еще несколько вопросов реализации, которые будут решаться ActivePoints.
Мы продолжим обсуждение алгоритма в части 4 и части 5 . Реализация кода будет обсуждаться в части 6 .

Рекомендации :
http://web.stanford.edu/~mjkay/gusfield.pdf

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

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

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

0.00 (0%) 0 votes