Рубрики

Обобщенное дерево суффиксов 1

Поиск по шаблону, Продвинутые Структуры данных

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

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

Для таких операций все задействованные строки должны быть проиндексированы для более быстрого поиска и извлечения. Один из способов сделать это — использовать суффикс trie или суффиксное дерево. Мы обсудим здесь дерево суффиксов.
Дерево суффиксов, созданное из набора строк, называется обобщенным деревом суффиксов .
Мы обсудим простой способ построения обобщенного суффиксного дерева здесь только для двух строк .
Позже мы обсудим другой подход к созданию обобщенного суффиксного дерева для двух или более строк .

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

Давайте рассмотрим две строки X и Y, для которых мы хотим построить обобщенное суффиксное дерево. Для этого мы создадим новую строку X # Y $, где # и $ оба являются терминальными символами (должны быть уникальными). Затем мы создадим дерево суффиксов для X # Y $, которое будет обобщенным деревом суффиксов для X и Y. Та же логика будет применяться для более чем двух строк (т.е. объединить все строки с использованием уникальных терминальных символов, а затем построить дерево суффиксов для объединенной строки) ,

Допустим, X = xabxa, а Y = babxba, тогда
X # Y $ = xabxa # babxba $
Если мы запустим код, реализованный в Ukkonen's Suffix Tree Construction — часть 6 для строки xabxa # babxba $, мы получим следующий вывод:
Выход:

Графический вид:

Мы можем использовать это дерево для решения некоторых проблем, но мы можем немного его уточнить, удалив ненужные подстроки в метке пути. У метки пути должна быть подстрока только из одной входной строки, поэтому, если есть метки пути, имеющие подстроки из нескольких входных строк, мы можем оставить только начальную часть, соответствующую одной строке, и удалить всю последующую часть. Например, для пути этикетки # babxba $, A # babxba $ и BXA # babxba $, мы можем удалить babxba $ (принадлежит 2 — й строке ввода) , а затем новые этикетки пути будут #, A # и BXA # соответственно. С этим изменением приведенная выше диаграмма будет выглядеть следующим образом:

Ниже реализация построена поверх оригинальной реализации . Здесь мы удаляем нежелательные символы на метках пути. Если метка пути содержит символ «#», то мы обрезаем все символы после «#» в этой метке пути.
Примечание. Эта реализация создает обобщенное суффиксное дерево только для двух строк X и Y, которые объединяются в X # Y $.

// 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 && text[k] != '#'; k++)

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

    if(k<=j)

        printf("#");

}

   
// Выводим также дерево суффиксов вместе с настройкой индекса суффикса
// Таким образом, дерево будет напечатано в 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)

    {

        for(i= n->start; i<= *(n->end); i++)

        {

            if(text[i] == '#') // Обрезать нежелательных персонажей

            {

                n->end = (int*) malloc(sizeof(int));

                *(n->end) = i;

            }

        }

        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, "xabxac # abcabxabcd $"); buildSuffixTree ();

    strcpy(text, "xabxa#babxba$"); buildSuffixTree();

    return 0;

}

Вывод: (Вы можете видеть, что нижеприведенный вывод соответствует 2- му рисунку, показанному выше)

# [5]
$ [12]
a [-1]
# [4]
$ [11]
bx [-1]
a# [1]
ba$ [7]
b [-1]
a [-1]
$ [10]
bxba$ [6]
x [-1]
a# [2]
ba$ [8]
x [-1]
a [-1]
# [3]
bxa# [0]
ba$ [9]

Если две строки имеют размер M и N, эта реализация займет O (M + N) времени и пространства.
Если входные строки еще не конкатенированы, то всего потребуется 2 (M + N) пространства, пространство M + N для хранения обобщенного суффиксного дерева и другое пространство M + N для хранения сцепленной строки.

Следовать за:
Расширить вышеприведенную реализацию более чем на две строки (т.е. объединить все строки, используя уникальные символы терминала, а затем построить дерево суффиксов для объединенной строки)

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

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

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

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

Обобщенное дерево суффиксов 1

0.00 (0%) 0 votes