Рубрики

Приложение Suffix Tree 2 — Поиск по всем паттернам

Учитывая текстовую строку и строку шаблона, найдите все вхождения шаблона в строку.

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

В 1 — й суффикса дерева Application ( Substring Check ), мы увидели , как проверить , является ли данный шаблон подстроки текста или нет. Рекомендуется пройти проверку подстроки 1 ст .
В этой статье мы пойдем немного дальше по той же проблеме. Если шаблон является подстрокой текста, то мы найдем все позиции шаблона в тексте.

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

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

Это дерево суффиксов для строки «abcabxabcd $», показывающее индексы суффиксов и индексы меток ребер (начало, конец). Значение (под) строки по краям показано только для пояснения. Мы никогда не храним строку метки пути в дереве.
Суффикс Индекс пути указывает индекс подстроки (начиная с корня) на этом пути.
Рассмотрим путь «bcd $» в вышеприведенном дереве с индексом 7. Он говорит, что подстроки b, bc, bcd, bcd $ находятся в индексе 7 в строке.
Аналогично, путь «bxabcd $» с суффиксным индексом 4 говорит о том, что подстроки b, bx, bxa, bxab, bxabc, bxabcd, bxabcd $ находятся в индексе 4.
Аналогично, путь «bcabxabcd $» с индексом суффикса 1 говорит о том, что подстроки b, bc, bca, bcab, bcabx, bcabxa, bcabxab, bcabxabc, bcabxabcd, bcabxabcd $ находятся в индексе 1.

Если мы увидим все три вышеупомянутых пути вместе, мы увидим, что:

  • Подстрока «b» находится в индексах 1, 4 и 7
  • Подстрока «bc» находится в индексах 1 и 7

С приведенным выше объяснением мы должны увидеть следующее:

  • Подстрока «ab» находится в индексах 0, 3 и 6
  • Подстрока «abc» находится в индексах 0 и 6
  • Подстрока «с» находится в индексах 2 и 8
  • Подстрока «xab» находится в индексе 5
  • Подстрока «d» имеет индекс 9
  • Подстрока «cd» находится в индексе 8
  • … ..
    … ..

Можете ли вы увидеть, как найти все вхождения шаблона в строке?

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

// 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 doTraversalToCountLeaf(Node *n)

{

    if(n == NULL)

        return 0;

    if(n->suffixIndex > -1)

    {

        printf("\nFound at position: %d", n->suffixIndex);

        return 1;

    }

    int count = 0;

    int i = 0;

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

    {

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

        {

            count += doTraversalToCountLeaf(n->children[i]);

        }

    }

    return count;

}

  

int countLeaf(Node *n)

{

    if(n == NULL)

        return 0;

    return doTraversalToCountLeaf(n);

}

  

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 == -1)  //не совпадает

            return -1;

        if(res == 1) //совпадение

        {

            if(n->suffixIndex > -1)

                printf("\nsubstring count: 1 and position: %d",

                               n->suffixIndex);

            else

                printf("\nsubstring count: %d", countLeaf(n));

            return 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("\nPattern <%s> is a Substring\n", str);

    else

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

}

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

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

{

    strcpy(text, "GEEKSFORGEEKS$"); 

    buildSuffixTree();    

    printf("Text: GEEKSFORGEEKS, Pattern to search: GEEKS");

    checkForSubString("GEEKS");

    printf("\n\nText: GEEKSFORGEEKS, Pattern to search: GEEK1");

    checkForSubString("GEEK1");

    printf("\n\nText: GEEKSFORGEEKS, Pattern to search: FOR");

    checkForSubString("FOR");

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

    freeSuffixTreeByPostOrder(root);

  

    strcpy(text, "AABAACAADAABAAABAA$");

    buildSuffixTree();    

    printf("\n\nText: AABAACAADAABAAABAA, Pattern to search: AABA");

    checkForSubString("AABA");

    printf("\n\nText: AABAACAADAABAAABAA, Pattern to search: AA");

    checkForSubString("AA");

    printf("\n\nText: AABAACAADAABAAABAA, Pattern to search: AAE");

    checkForSubString("AAE");

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

    freeSuffixTreeByPostOrder(root);

  

    strcpy(text, "AAAAAAAAA$");

    buildSuffixTree();    

    printf("\n\nText: AAAAAAAAA, Pattern to search: AAAA");

    checkForSubString("AAAA");

    printf("\n\nText: AAAAAAAAA, Pattern to search: AA");

    checkForSubString("AA");

    printf("\n\nText: AAAAAAAAA, Pattern to search: A");

    checkForSubString("A");

    printf("\n\nText: AAAAAAAAA, Pattern to search: AB");

    checkForSubString("AB");

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

    freeSuffixTreeByPostOrder(root);

  

    return 0;

}

Выход:

Text: GEEKSFORGEEKS, Pattern to search: GEEKS
Found at position: 8
Found at position: 0
substring count: 2
Pattern <GEEKS> is a Substring


Text: GEEKSFORGEEKS, Pattern to search: GEEK1
Pattern <GEEK1> is NOT a Substring


Text: GEEKSFORGEEKS, Pattern to search: FOR
substring count: 1 and position: 5
Pattern <FOR> is a Substring


Text: AABAACAADAABAAABAA, Pattern to search: AABA
Found at position: 13
Found at position: 9
Found at position: 0
substring count: 3
Pattern <AABA> is a Substring


Text: AABAACAADAABAAABAA, Pattern to search: AA
Found at position: 16
Found at position: 12
Found at position: 13
Found at position: 9
Found at position: 0
Found at position: 3
Found at position: 6
substring count: 7
Pattern <AA> is a Substring


Text: AABAACAADAABAAABAA, Pattern to search: AAE
Pattern <AAE> is NOT a Substring


Text: AAAAAAAAA, Pattern to search: AAAA
Found at position: 5
Found at position: 4
Found at position: 3
Found at position: 2
Found at position: 1
Found at position: 0
substring count: 6
Pattern <AAAA> is a Substring


Text: AAAAAAAAA, Pattern to search: AA
Found at position: 7
Found at position: 6
Found at position: 5
Found at position: 4
Found at position: 3
Found at position: 2
Found at position: 1
Found at position: 0
substring count: 8
Pattern <AA> is a Substring


Text: AAAAAAAAA, Pattern to search: A
Found at position: 8
Found at position: 7
Found at position: 6
Found at position: 5
Found at position: 4
Found at position: 3
Found at position: 2
Found at position: 1
Found at position: 0
substring count: 9
Pattern <A> is a Substring


Text: AAAAAAAAA, Pattern to search: AB
Pattern <AB> is NOT a Substring

Построение дерева суффиксов Укконена требует O (N) времени и пространства для построения дерева суффиксов для строки длины N, и после этого для проверки подстроки требуется O (M) для шаблона длины M, а затем, если есть Z вхождений шаблон, это займет O (Z), чтобы найти индексы всех этих вхождений Z.
Общая сложность паттерна линейна: O (M + Z).

Немного более подробный анализ
Сколько внутренних узлов будет в дереве суффиксов строки длины N ??
Ответ: N-1 (почему ??)
Там будет N суффиксов в строке длиной N.
Каждый суффикс будет иметь один лист.
Таким образом, дерево суффиксов строки N будет иметь N листьев.
Поскольку у каждого внутреннего узла есть по крайней мере 2 дочерних элемента, дерево суффиксов из N-листьев имеет максимум N-1 внутренних узлов.
Если шаблон встречается Z раз в строке, это означает, что он будет частью суффикса Z, поэтому в точке (внутреннем узле и между ребрами) будет Z листьев, где сопоставление с шаблоном заканчивается в дереве, и поэтому поддерево с Z оставляет ниже этой точки. будет иметь внутренние узлы Z-1. Дерево с Z листьями можно пройти за O (Z).
Общая сложность паттерна линейна: O (M + Z).
Для данного шаблона Z (количество вхождений) может быть не более N.
Таким образом, сложность наихудшего случая может быть: O (M + N), если Z близко / равно N (обход дерева с N узлами занимает O (N) времени).

Последующие вопросы:

  1. Проверить, является ли шаблон префиксом текста?
  2. Проверить, является ли шаблон суффиксом текста?

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

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

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

Приложение Suffix Tree 2 — Поиск по всем паттернам

0.00 (0%) 0 votes