Рубрики

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

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

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

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

У нас будет структура SuffixTreeNode для представления каждого узла в дереве. Структура SuffixTreeNode будет иметь следующие члены:

  • дети — это будет массив размера алфавита. Это сохранит все дочерние узлы текущего узла на разных ребрах, начиная с разных символов.
  • суффиксLink — это будет указывать на другой узел, где текущий узел должен указывать через ссылку суффикса.
  • start, end — эти два элемента будут хранить данные метки ребра от родительского узла до текущего узла. Интервал (начало, конец) указывает ребро, по которому узел подключен к своему родительскому узлу. Каждое ребро соединит два узла, один родительский и один дочерний, а интервал (начало, конец) данного ребра будет сохранен в дочернем узле. Допустим, есть два узла A (родитель) и B (ребенок), соединенные ребром с индексами (5, 8), тогда эти индексы (5, 8) будут храниться в узле B.
  • suffixIndex — это будет неотрицательным для листьев и даст индекс суффикса для пути от корня до этого листа. Для неконечного узла это будет -1.

Эта структура данных будет отвечать на требуемые запросы быстро, как показано ниже:

  • Как проверить, является ли узел корневым? — Root — это специальный узел без родителя, поэтому его начало и конец будут равны -1, для всех остальных узлов начальный и конечный индексы будут неотрицательными.
  • Как проверить, является ли узел внутренним или конечным? — Суффикс Индекс поможет здесь. Это будет -1 для внутреннего узла и неотрицательный для конечных узлов.
  • Какова длина метки пути на некотором ребре? — Каждое ребро будет иметь начальный и конечный индексы, а длина метки пути будет end-start + 1
  • Что такое метка пути на каком-нибудь ребре? — Если строка S, метка пути будет подстрокой S от начального индекса до конечного индекса включительно, [начало, конец].
  • Как проверить, есть ли исходящее ребро для данного символа c из узла A? — Если A-> children [c] не NULL, существует путь, если NULL, пути нет.
  • Каково значение символа на ребре на некотором заданном расстоянии d от узла A? — Символ на расстоянии d от узла A будет S [A-> start + d], где S — строка.
  • Куда указывает внутренний узел через суффиксную ссылку? — Узел A будет указывать на A-> SuffixLink
  • Что такое индекс суффикса на пути от корня к листу? — Если конечным узлом является A на пути, то индекс суффикса на этом пути будет A-> suffixIndex

Следующее — реализация C Суффикс-Конструкции Укконена. Код может выглядеть немного длинным, возможно, из-за большого количества комментариев.

// AC-программа для реализации Ukkonen's Suffix Tree Construction
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_CHAR 256

  

struct SuffixTreeNode {

    struct SuffixTreeNode *children[MAX_CHAR];

  

    // указатель на другой узел через суффиксную ссылку

    struct SuffixTreeNode *suffixLink;

  

    / * (начало, конец) интервал определяет ребро, по которому

     узел связан с его родительским узлом. Каждый край будет

     соединить два узла, один родительский и один дочерний, и

     (начало, конец) интервал данного ребра будет сохранен

     в дочернем узле. Допустим, есть два куска A и B

     связаны ребром с индексами (5, 8), то это

     индексы (5, 8) будут храниться в узле B. * /

    int start;

    int *end;

  

    / * для конечных узлов хранит индекс суффикса для

      путь от корня до листа * /

    int suffixIndex;

};

  

typedef struct SuffixTreeNode Node;

  

char text[100]; //Строка ввода

Node *root = NULL; // Указатель на корневой узел

  
/ * lastNewNode будет указывать на вновь созданный внутренний узел,

  ожидание установки суффиксной ссылки, которая может получить

  новая ссылка суффикса (кроме корня) в следующем расширении

  та же фаза. lastNewNode будет установлен в NULL, когда последний

  вновь созданный внутренний узел (если есть) получил его

  сброс суффиксной ссылки на новый внутренний узел, созданный в следующем

  продление той же фазы. * /

Node *lastNewNode = NULL;
Node *activeNode = NULL;

  
/ * activeEdge представлен как символ входной строки

  индекс (не сам символ) * /

int activeEdge = -1;

int activeLength = 0;

  
// Остальная часть суффиксов сообщает, сколько суффиксов еще предстоит
// быть добавленным в дерево

int remainingSuffixCount = 0;

int leafEnd = -1;

int *rootEnd = NULL;

int *splitEnd = NULL;

int size = -1; // Длина входной строки

  

Node *newNode(int start, int *end)

{

    Node *node =(Node*) malloc(sizeof(Node));

    int i;

    for (i = 0; i < MAX_CHAR; i++)

          node->children[i] = NULL;

  

    / * Для корневого узла СуффиксLink будет установлен в NULL

    Для внутренних узлов СуффиксLink будет установлен как root

    по умолчанию в текущем расширении и может измениться в

    следующее расширение * /

    node->suffixLink = root;

    node->start = start;

    node->end = end;

  

    / * суффиксIndex будет установлен в -1 по умолчанию и

      фактический индекс суффикса будет установлен позже для листьев

      в конце всех фаз * /

    node->suffixIndex = -1;

    return node;

}

  

int edgeLength(Node *n) {

    return *(n->end) - (n->start) + 1;

}

  

int walkDown(Node *currNode)

{

    / * изменение activePoint для перехода вниз (APCFWD) с помощью

     Пропустить / считать трюк (трюк 1). Если activeLength больше

     чем текущая длина ребра, установите следующий внутренний узел как

     activeNode и настройте activeEdge и activeLength

     соответственно представлять ту же ActivePoint * /

    if (activeLength >= edgeLength(currNode))

    {

        activeEdge += edgeLength(currNode);

        activeLength -= edgeLength(currNode);

        activeNode = currNode;

        return 1;

    }

    return 0;

}

  

void extendSuffixTree(int pos)

{

    / * Правило расширения 1, оно заботится о расширении всех

    листья, созданные до сих пор в дереве * /

    leafEnd = pos;

  

    / * Увеличивать оставшийсяSuffixCount, указывая, что

    добавлен новый суффикс в список суффиксов

    добавлено в дерево * /

    remainingSuffixCount++;

  

    / * установить lastNewNode в NULL при запуске новой фазы,

     указывает на то, что внутренний узел не ожидает

     это суффикс сброса ссылки в текущей фазе * /

    lastNewNode = NULL;

  

    // Добавить все суффиксы (еще не добавленные) по одному в дереве

    while(remainingSuffixCount > 0) {

  

        if (activeLength == 0)

            activeEdge = pos; // APCFALZ

  

        // Нет исходящего ребра, начинающегося с

        // activeEdge из activeNode

        if (activeNode->children] == NULL)

        {

            // Расширение правила 2 (создается новый край листа)

            activeNode->children] =

                                          newNode(pos, &leafEnd);

  

            / * Новый край листа создается в начале строки выше

             от существующего узла (текущий активный узел), и

             если есть какой-либо внутренний узел, ожидающий своего суффикса

             ссылка получить сброс, указать ссылку суффикса из этого последнего

             внутренний узел к текущему активному узлу. Затем установите lastNewNode

             значение NULL, указывающее, что больше нет узлов, ожидающих суффиксную ссылку

             сброс настроек.*/

            if (lastNewNode != NULL)

            {

                lastNewNode->suffixLink = activeNode;

                lastNewNode = NULL;

            }

        }

        // Есть исходящий фронт, начинающийся с activeEdge

        // из activeNode

        else

        {

            // Получить следующий узел в конце начала ребра

            // с activeEdge

            Node *next = activeNode->children];

            if (walkDown(next))// Пройдемся

            {

                // Начать со следующего узла (новый активный узел)

                continue;

            }

            / * Правило расширения 3 (текущий символ обрабатывается

              уже на грани) * /

            if (text[next->start + activeLength] == text[pos])

            {

                // Если недавно созданный узел ожидает его

                // суффиксная ссылка, которую нужно установить, затем установить суффиксную ссылку

                // этого ожидающего узла к текущему активному узлу

                if(lastNewNode != NULL && activeNode != root)

                {

                    lastNewNode->suffixLink = activeNode;

                    lastNewNode = NULL;

                }

  

                // APCFER3

                activeLength++;

                / * ОСТАНОВИТЬ всю дальнейшую обработку на этом этапе

                и перейти к следующему этапу * /

                break;

            }

  

            / * Мы будем здесь, когда activePoint будет в середине

              пройденный край и текущий символ

              обрабатывается не на краю (мы падаем

              дерево). В этом случае мы добавляем новый внутренний узел

              и новый край листа выходит из этого нового узла. Эта

              это расширение правила 2, где новый край листа и новый

            внутренний узел создан * /

            splitEnd = (int*) malloc(sizeof(int));

            *splitEnd = next->start + activeLength - 1;

  

            // Новый внутренний узел

            Node *split = newNode(next->start, splitEnd);

            activeNode->children] = split;

  

            // Новый лист выходит из нового внутреннего узла

            split->children] = newNode(pos, &leafEnd);

            next->start += activeLength;

            split->children] = next;

  

            / * Мы получили новый внутренний узел здесь. Если есть

              внутренний узел создан в последних расширениях того же

              фаза, которая все еще ждет своего суффикса

              сбросьте, сделайте это сейчас. * /

            if (lastNewNode != NULL)

            {

            / * СуффиксLink из lastNewNode указывает на текущий недавно

              создан внутренний узел * /

                lastNewNode->suffixLink = split;

            }

  

            / * Сделать текущий вновь созданный внутренний узел ожидающим

              для сброса ссылки суффикса (который указывает на root

              в настоящий момент). Если мы сталкиваемся с любым другим внутренним узлом

              (существующий или вновь созданный) в следующем расширении того же

              фаза, когда добавляется новый край листа (т.е. когда

              Расширение Правило 2 применяется к любому следующему расширению

              той же фазы) в этой точке, СуффиксЛинк этого узла

              будет указывать на этот внутренний узел. * /

            lastNewNode = split;

        }

  

        / * В дерево добавлен один суффикс, уменьшающий счетчик

          суффиксы еще предстоит добавить. * /

        remainingSuffixCount--;

        if (activeNode == root && activeLength > 0) // APCFER2C1

        {

            activeLength--;

            activeEdge = pos - remainingSuffixCount + 1;

        }

        else if (activeNode != root) // APCFER2C2

        {

            activeNode = activeNode->suffixLink;

        }

    }

}

  

void print(int i, int j)

{

    int k;

    for (k=i; k<=j; k++)

        printf("%c", text[k]);

}

  
// Выводим также дерево суффиксов вместе с настройкой индекса суффикса
// Таким образом, дерево будет напечатано в DFS-стиле
// Каждое ребро вместе с индексом суффикса будет напечатано

void setSuffixIndexByDFS(Node *n, int labelHeight)

{

    if (n == NULL)  return;

  

    if (n->start != -1) // некорневой узел

    {

        // Распечатать метку по краю от родителя к текущему узлу

        print(n->start, *(n->end));

    }

    int leaf = 1;

    int i;

    for (i = 0; i < MAX_CHAR; i++)

    {

        if (n->children[i] != NULL)

        {

            if (leaf == 1 && n->start != -1)

                printf(" [%d]\n", n->suffixIndex);

  

            // Текущий узел не является листом, так как имеет исходящий

            // края от него.

            leaf = 0;

            setSuffixIndexByDFS(n->children[i], labelHeight +

                                  edgeLength(n->children[i]));

        }

    }

    if (leaf == 1)

    {

        n->suffixIndex = size - labelHeight;

        printf(" [%d]\n", n->suffixIndex);

    }

}

  

void freeSuffixTreeByPostOrder(Node *n)

{

    if (n == NULL)

        return;

    int i;

    for (i = 0; i < MAX_CHAR; i++)

    {

        if (n->children[i] != NULL)

        {

            freeSuffixTreeByPostOrder(n->children[i]);

        }

    }

    if (n->suffixIndex == -1)

        free(n->end);

    free(n);

}

  
/ * Построить дерево суффиксов и напечатать края меток вместе с
suffixIndex. СуффиксИндекс для краев листа будет> = 0 и
для не листовых ребер будет -1 * /

void buildSuffixTree()

{

    size = strlen(text);

    int i;

    rootEnd = (int*) malloc(sizeof(int));

    *rootEnd = - 1;

  

    / * Root - это специальный узел с индексами начала и конца, равными -1,

    так как у него нет родителя, откуда ребро приходит к корню * /

    root = newNode(-1, rootEnd);

  

    activeNode = root; // Первый активный узел будет корневым

    for (i=0; i<size; i++)

        extendSuffixTree(i);

    int labelHeight = 0;

    setSuffixIndexByDFS(root, labelHeight);

  

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

}

  
// программа драйвера для проверки вышеуказанных функций

int main(int argc, char *argv[])

{
// strcpy (text, "abc"); buildSuffixTree ();
// strcpy (text, "xabxac #"); buildSuffixTree ();
// strcpy (text, "xabxa"); buildSuffixTree ();
// strcpy (text, "xabxa $"); buildSuffixTree ();

    strcpy(text, "abcabxabcd$"); buildSuffixTree();

// strcpy (text, "geeksforgeeks $"); buildSuffixTree ();
// strcpy (text, "ЭТО ТЕСТ ТЕСТА $"); buildSuffixTree ();
// strcpy (text, "AABAACAADAABAAABAA $"); buildSuffixTree ();

    return 0;

}

Вывод (каждое ребро дерева вместе с индексом суффикса дочернего узла на ребре печатается в порядке DFS. Чтобы лучше понять вывод, сопоставьте его с последним рисунком № 43 в предыдущей части 5 ):

$ [10]
ab [-1]
c [-1]
abxabcd$ [0]
d$ [6]
xabcd$ [3]
b [-1]
c [-1]
abxabcd$ [1]
d$ [7]
xabcd$ [4]
c [-1]
abxabcd$ [2]
d$ [8]
d$ [9]
xabcd$ [5]

Теперь мы можем построить суффиксное дерево за линейное время и эффективно решить многие строковые задачи:

  • Проверьте, является ли данный шаблон P подстрокой текста T (полезно, когда текст фиксирован и шаблон меняется, в противном случае KMP
  • Найти все вхождения данного шаблона P, присутствующего в тексте T
  • Найти самую длинную повторяющуюся подстроку
  • Создание массива линейного суффикса времени

Указанные выше основные проблемы могут быть решены путем обхода DFS по суффиксному дереву.
Мы скоро опубликуем статьи по вышеуказанным проблемам и другим, как показано ниже:

И многое другое

Проверьте ваше понимание?

  1. Нарисуйте на бумаге дерево суффиксов (с соответствующей ссылкой суффикса, индексами суффикса) для строки «AABAACAADAABAAABAA $» и посмотрите, соответствует ли это выводу кода.
  2. Каждое продление должно следовать одному из трех правил: Правило 1, Правило 2 и Правило 3.
    Ниже приведены правила, применяемые к пяти последовательным расширениям в некоторой Фазе i (i> 5), которые действительны:
    А) Правило 1, Правило 2, Правило 2, Правило 3, Правило 3
    Б) Правило 1, Правило 2, Правило 2, Правило 3, Правило 2
    C) Правило 2, Правило 1, Правило 1, Правило 3, Правило 3
    D) Правило 1, Правило 1, Правило 1, Правило 1, Правило 1
    E) Правило 2, Правило 2, Правило 2, Правило 2, Правило 2
    F) Правило 3, Правило 3, Правило 3, Правило 3, Правило 3
  3. Каковы действительные последовательности в фазе 5 выше?
  4. Каждый внутренний узел ДОЛЖЕН иметь свою суффиксную ссылку, установленную на другой узел (внутренний или корневой). Может ли вновь созданный узел указывать на уже существующий внутренний узел или нет? Может ли случиться так, что новый узел, созданный в расширении j, может не получить правильную суффиксную ссылку в следующем расширении j + 1 и получить правильный в последующих расширениях, таких как j + 2, j + 3 и т. Д.?
  5. Попробуйте решить основные проблемы, которые обсуждались выше.

Мы опубликовали следующие статьи о приложениях дерева суффиксов:

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

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

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

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

0.00 (0%) 0 votes