Рубрики

Приложение суффиксного дерева 1 — Проверка подстроки

Учитывая текстовую строку и строку шаблона, проверьте, существует ли шаблон в тексте или нет.

Несколько алгоритмов поиска по шаблону ( KMP , Rabin-Karp , Naive Algorithm , Finite Automata ) уже обсуждались, которые можно использовать для этой проверки.
Здесь мы обсудим алгоритм на основе суффиксного дерева.

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

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

Реализация базового обхода для проверки подстроки может быть изменена соответствующим образом для деревьев суффиксов, построенных другими алгоритмами.

// Программа 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);

}

  

int traverseEdge(char *str, int idx, int start, int end)

{

    int k = 0;

    // Обход края с посимвольным соответствием

    for(k=start; k<=end && str[idx] != '\0'; k++, idx++)

    {

        if(text[k] != str[idx])

            return -1;  // мо совпадение

    }

    if(str[idx] == '\0')

        return 1;  // совпадение

    return 0;  // еще символы, которые должны соответствовать

}

  

int doTraversal(Node *n, char* str, int idx)

{

    if(n == NULL)

    {

        return -1; // не совпадает

    }

    int res = -1;

    // Если узел n не является корневым узлом, то пересекаем ребро

    // от родительского узла n к узлу n.

    if(n->start != -1)

    {

        res = traverseEdge(str, idx, n->start, *(n->end));

        if(res != 0)

            return res;  // совпадение (res = 1) или нет совпадения (res = -1)

    }

    // Получить индекс символа для поиска

    idx = idx + edgeLength(n);

    // Если выходит ребро из узла n

    // с текущим символом str [idx], пройти через этот край

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

        return doTraversal(n->children[str[idx]], str, idx);

    else

        return -1;  // не совпадает

}

  

void checkForSubString(char* str)

{

    int res = doTraversal(root, str, 0);

    if(res == 1)

        printf("Pattern <%s> is a Substring\n", str);

    else

        printf("Pattern <%s> is NOT a Substring\n", str);

}

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

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

{

    strcpy(text, "THIS IS A TEST TEXT$"); 

    buildSuffixTree();    

  

    checkForSubString("TEST");

    checkForSubString("A");

    checkForSubString(" ");

    checkForSubString("IS A");

    checkForSubString(" IS A ");

    checkForSubString("TEST1");

    checkForSubString("THIS IS GOOD");

    checkForSubString("TES");

    checkForSubString("TESA");

    checkForSubString("ISB");

  

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

    freeSuffixTreeByPostOrder(root);

  

    return 0;

}

Выход:

Pattern <TEST> is a Substring
Pattern <A> is a Substring
Pattern < > is a Substring
Pattern <IS A> is a Substring
Pattern < IS A > is a Substring
Pattern <TEST1> is NOT a Substring
Pattern <THIS IS GOOD> is NOT a Substring
Pattern <TES> is a Substring
Pattern <TESA> is NOT a Substring
Pattern <ISB> is NOT a Substring

Построение дерева суффиксов Укконена занимает O (N) время и пространство для построения дерева суффиксов для строки длины N, и после этого для проверки подстроки требуется O (M) для шаблона длины M.

С небольшой модификацией в алгоритме обхода, обсужденном здесь, мы можем ответить на следующее:

  1. Найти все вхождения данного шаблона P, присутствующего в тексте T.
  2. Как проверить, является ли шаблон префиксом текста?
  3. Как проверить, является ли шаблон суффиксом текста?

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

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

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

Приложение суффиксного дерева 1 — Проверка подстроки

0.00 (0%) 0 votes