Рубрики

Suffix Tree Application 4 — построение линейного суффиксного массива времени

Учитывая строку, создайте суффиксный массив
Мы уже обсудили следующие два способа построения суффиксного массива:

Пожалуйста, пройдите через это, чтобы иметь базовое понимание.
Здесь мы увидим, как построить суффиксный массив за линейное время, используя суффиксное дерево.

В качестве предварительного условия мы должны знать, как построить дерево суффиксов тем или иным способом.
Здесь мы построим дерево суффиксов, используя алгоритм Укконена, который уже обсуждался ниже:
Построение суффикс-дерева Укконена — часть 1
Построение Суффикса Укконена — Часть 2
Построение Суффикса Укконена — Часть 3
Построение суффикс-дерева Укконена — часть 4
Построение Суффикса Укконена — Часть 5
Построение Суффикса Укконена — Часть 6

Давайте рассмотрим строку abcabxabcd.
Это суффиксный массив будет:

0 6 3 1 7 4 2 8 9 5

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

Если мы сделаем обход DFS, посетив ребра в лексикографическом порядке (мы делали то же самое и в других статьях Suffix Tree Application) и напечатав индексы суффиксов на листьях, мы получим следующее:

10 0 6 3 1 7 4 2 8 9 5

«$» Лексикографически меньше, чем [a-zA-Z].
Индекс суффикса 10 соответствует ребру с меткой «$».
За исключением этого 1- го индекса суффикса, последовательность всех других чисел дает массив суффиксов строки.

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

// 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) {

    if(n == root)

        return 0;

    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);

}

  

void doTraversal(Node *n, int suffixArray[], int *idx)

{

    if(n == NULL)

    {

        return;

    }

    int i=0;

    if(n->suffixIndex == -1) // Если это внутренний узел

    {

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

        {

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

            {

                doTraversal(n->children[i], suffixArray, idx);

            }

        }

    }

    // Если это листовой узел, отличный от метки "$"

    else if(n->suffixIndex > -1 && n->suffixIndex < size)

    {

        suffixArray[(*idx)++] = n->suffixIndex;

    }

}

  

void buildSuffixArray(int suffixArray[])

{

    int i = 0;

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

        suffixArray[i] = -1;

    int idx = 0;

    doTraversal(root, suffixArray, &idx);

    printf("Suffix Array for String ");

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

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

    printf(" is: ");

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

        printf("%d ", suffixArray[i]);

    printf("\n");

}

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

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

{

    strcpy(text, "banana$"); 

    buildSuffixTree();        

    size--;

    int *suffixArray =(int*) malloc(sizeof(int) * size);

    buildSuffixArray(suffixArray);

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

    freeSuffixTreeByPostOrder(root);

    free(suffixArray);

  

    strcpy(text, "GEEKSFORGEEKS$"); 

    buildSuffixTree();        

    size--;

    suffixArray =(int*) malloc(sizeof(int) * size);

    buildSuffixArray(suffixArray);

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

    freeSuffixTreeByPostOrder(root);

    free(suffixArray);

  

    strcpy(text, "AAAAAAAAAA$"); 

    buildSuffixTree();        

    size--;

    suffixArray =(int*) malloc(sizeof(int) * size);

    buildSuffixArray(suffixArray);

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

    freeSuffixTreeByPostOrder(root);

    free(suffixArray);

  

    strcpy(text, "ABCDEFG$"); 

    buildSuffixTree();        

    size--;

    suffixArray =(int*) malloc(sizeof(int) * size);

    buildSuffixArray(suffixArray);

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

    freeSuffixTreeByPostOrder(root);

    free(suffixArray);

  

    strcpy(text, "ABABABA$"); 

    buildSuffixTree();        

    size--;

    suffixArray =(int*) malloc(sizeof(int) * size);

    buildSuffixArray(suffixArray);

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

    freeSuffixTreeByPostOrder(root);

    free(suffixArray);

  

    strcpy(text, "abcabxabcd$"); 

    buildSuffixTree();        

    size--;

    suffixArray =(int*) malloc(sizeof(int) * size);

    buildSuffixArray(suffixArray);

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

    freeSuffixTreeByPostOrder(root);

    free(suffixArray); 

  

    strcpy(text, "CCAAACCCGATTA$"); 

    buildSuffixTree();        

    size--;

    suffixArray =(int*) malloc(sizeof(int) * size);

    buildSuffixArray(suffixArray);

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

    freeSuffixTreeByPostOrder(root);

    free(suffixArray);

  

    return 0;

}

Выход:

Suffix Array for String banana is: 5 3 1 0 4 2 
Suffix Array for String GEEKSFORGEEKS is: 9 1 10 2 5 8 0 11 3 6 7 12 4 
Suffix Array for String AAAAAAAAAA is: 9 8 7 6 5 4 3 2 1 0 
Suffix Array for String ABCDEFG is: 0 1 2 3 4 5 6 
Suffix Array for String ABABABA is: 6 4 2 0 5 3 1 
Suffix Array for String abcabxabcd is: 0 6 3 1 7 4 2 8 9 5
Suffix Array for String CCAAACCCGATTA is: 12 2 3 4 9 1 0 5 6 7 8 11 10

Построение дерева суффиксов Укконена требует O (N) времени и пространства для построения дерева суффиксов для строки длины N, а после этого обход дерева занимает O (N) для построения массива суффиксов.
Таким образом, в целом, это линейно во времени и пространстве.
Вы видите, почему обход O (N) ?? Поскольку дерево суффиксов строки длиной N будет иметь не более N-1 внутренних узлов и N листьев. Обход этих узлов может быть сделан в O (N).

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

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

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

Suffix Tree Application 4 — построение линейного суффиксного массива времени

0.00 (0%) 0 votes