Рубрики

Поиск по шаблону с использованием дерева всех суффиксов

Постановка задачи: учитывая текст txt [0..n-1] и шаблон pat [0..m-1], напишите функцию поиска (char pat [], char txt []), которая печатает все вхождения pat [ ] в текстовом формате []. Вы можете предположить, что n> m.

Как обсуждалось в предыдущем посте , мы обсуждали, что есть два способа эффективно решить вышеупомянутую проблему.

1) Схема предварительной обработки: алгоритм KMP, алгоритм Рабина Карпа , конечные автоматы , алгоритм Бойера-Мура .

2) Текст препроцессора: Суффикс-дерево

Наилучшая возможная временная сложность, достигаемая первым (шаблон предварительной обработки), составляет O (n), а второй (текст предварительной обработки) — O (m), где m и n — длины шаблона и текста соответственно.

Обратите внимание, что второй способ выполняет поиск только за время O (m), и он предпочтителен, когда текст меняется не очень часто и имеется много поисковых запросов. Мы обсудили Suffix Tree (сжатый Trie всех суффиксов текста) .

Внедрение Suffix Tree может занять много времени для кодирования проблем в техническом интервью или в контексте программирования. В этом посте обсуждается простая реализация стандартного дерева всех суффиксов. Реализация близка к суффиксному дереву, единственное, это простой Trie вместо сжатого Trie.

Как обсуждалось в посте Suffix Tree , идея в том, что каждый шаблон, присутствующий в тексте (или мы можем сказать каждую подстроку текста), должен быть префиксом одного из всех возможных суффиксов. Таким образом, если мы построим Trie из всех суффиксов, мы можем найти шаблон за O (m) время, где m — длина шаблона.

Построение Три Суффиксов
1) Генерация всех суффиксов данного текста.
2) Рассмотрите все суффиксы как отдельные слова и создайте дерево.

Давайте рассмотрим пример текста «банан / 0», где «/ 0» — символ завершения строки. Ниже приведены все суффиксы «банан / 0»

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

Если мы рассмотрим все вышеприведенные суффиксы как отдельные слова и построим Trie, мы получим следующее.

Как искать шаблон во встроенном трие?
Ниже приведены шаги для поиска шаблона во встроенном Trie.
1) Начиная с первого символа шаблона и корня Trie, выполните следующие действия для каждого символа.
… .. a) Для текущего символа шаблона, если есть ребро от текущего узла, следуйте за ребром.
… .. б) Если края не заданы, выведите «образец не существует в тексте» и вернитесь.
2) Если все символы шаблона были обработаны, т. Е. Есть путь от корня для символов данного шаблона, то выведите в печать все индексы, в которых присутствует шаблон. Для хранения индексов мы используем список с каждым узлом, в котором хранятся индексы суффиксов, начиная с узла.

Ниже приводится реализация вышеуказанной идеи.

C ++

// Простая реализация подстроки в C ++ с использованием трех суффиксов
#include<iostream>
#include<list>
#define MAX_CHAR 256

using namespace std;

  
// Суффикс Trie (Три всех суффиксов) Узел

class SuffixTrieNode

{

private:

    SuffixTrieNode *children[MAX_CHAR];

    list<int> *indexes;

public:

    SuffixTrieNode() // Конструктор

    {

        // Создать пустой связанный список для индексов

        // суффиксы, начинающиеся с этого узла

        indexes = new list<int>;

  

        // Инициализируем все дочерние указатели как NULL

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

          children[i] = NULL;

    }

  

    // Рекурсивная функция для вставки суффикса текста

    // в поддереве с этим узлом

    void insertSuffix(string suffix, int index);

  

    // Функция для поиска шаблона в поддереве с корнем

    // с этим узлом. Функция возвращает указатель на связанный

    // список, содержащий все индексы, в которых присутствует шаблон.

    // Возвращаемые индексы являются индексами последних символов

    // сопоставленного текста.

    list<int>* search(string pat);

};

  
// Три всех суффиксов

class SuffixTrie

{

private:

    SuffixTrieNode root;

public:

    // Конструктор (Создает три суффикса данного текста)

    SuffixTrie(string txt)

    {

        // Рассмотрим все суффиксы заданной строки и вставим

        // их в суффикс Trie с использованием рекурсивной функции

        // insertSuffix () в классе SuffixTrieNode

        for (int i = 0; i < txt.length(); i++)

            root.insertSuffix(txt.substr(i), i);

    }

  

    // Функция для поиска шаблона в этом суффиксе.

    void search(string pat);

};

  
// Рекурсивная функция для вставки суффикса текста в
// поддерево укоренено в этом узле

void SuffixTrieNode::insertSuffix(string s, int index)

{

    // Сохранить индекс в связанном списке

    indexes->push_back(index);

  

    // Если в строке больше символов

    if (s.length() > 0)

    {

        // Находим первый символ

        char cIndex = s.at(0);

  

        // Если для этого символа нет ребра, добавьте новое ребро

        if (children[cIndex] == NULL)

            children[cIndex] = new SuffixTrieNode();

  

        // Повтор для следующего суффикса

        children[cIndex]->insertSuffix(s.substr(1), index+1);

    }

}

  
// Рекурсивная функция для поиска шаблона в поддереве с корнем
// этот узел

list<int>* SuffixTrieNode::search(string s)

{

    // Если все символы шаблона были обработаны,

    if (s.length() == 0)

        return indexes;

  

    // если есть ребро от текущего узла суффикса trie,

    // следуем за краем.

    if (children[s.at(0)] != NULL)

        return (children[s.at(0)])->search(s.substr(1));

  

    // Если края нет, шаблон не существует в тексте

    else return NULL;

}

  
/ * Печатает все вхождения pat в суффиксе Trie S (построено для текста) * /

void SuffixTrie::search(string pat)

{

    // Давайте назовем рекурсивную функцию поиска для корня Trie.

    // Мы получаем список всех индексов (где pat присутствует в тексте) в

    // переменная 'result'

    list<int> *result = root.search(pat);

  

    // Проверяем, пуст ли список индексов или нет

    if (result == NULL)

        cout << "Pattern not found" << endl;

    else

    {

       list<int>::iterator i;

       int patLen = pat.length();

       for (i = result->begin(); i != result->end(); ++i)

         cout << "Pattern found at position " << *i - patLen<< endl;

    }

}

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

int main()

{

    // Давайте создадим три-суффикс для текста "geeksforgeeks.org"

    string txt = "geeksforgeeks.org";

    SuffixTrie S(txt);

  

    cout << "Search for 'ee'" << endl;

    S.search("ee");

  

    cout << "\nSearch for 'geek'" << endl;

    S.search("geek");

  

    cout << "\nSearch for 'quiz'" << endl;

    S.search("quiz");

  

    cout << "\nSearch for 'forgeeks'" << endl;

    S.search("forgeeks");

  

    return 0;

}

Джава

import java.util.LinkedList;

import java.util.List;

class SuffixTrieNode {

  

    final static int MAX_CHAR = 256;

  

    SuffixTrieNode[] children = new SuffixTrieNode[MAX_CHAR];

    List<Integer> indexes;

  

    SuffixTrieNode() // Конструктор

    {

        // Создать пустой связанный список для индексов

        // суффиксы, начинающиеся с этого узла

        indexes = new LinkedList<Integer>();

  

        // Инициализируем все дочерние указатели как NULL

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

            children[i] = null;

    }

  

    // Рекурсивная функция для вставки суффикса

    // текст в поддереве с корнем из этого узла

    void insertSuffix(String s, int index) {

          

        // Сохранить индекс в связанном списке

        indexes.add(index);

  

        // Если в строке больше символов

        if (s.length() > 0) {

          

            // Находим первый символ

            char cIndex = s.charAt(0);

  

            // Если для этого символа нет ребра,

            // добавить новое ребро

            if (children[cIndex] == null)

                children[cIndex] = new SuffixTrieNode();

  

            // Повтор для следующего суффикса

            children[cIndex].insertSuffix(s.substring(1),

                                              index + 1);

        }

    }

  

    // Функция для поиска шаблона в поддереве с корнем

    // с этим узлом. Функция возвращает указатель на

    // связанный список, содержащий все индексы, где шаблон

    // настоящее. Возвращенные индексы являются индексами

    // последние символы сопоставленного текста.

    List<Integer> search(String s) {

          

        // Если все символы шаблона были

        // обработанный,

        if (s.length() == 0)

            return indexes;

  

        // если есть ребро от текущего узла

        // дерево суффиксов, следуем за краем.

        if (children[s.charAt(0)] != null)

            return (children[s.charAt(0)]).search(s.substring(1));

  

        // Если ребра нет, шаблон не существует в

        // текст

        else

            return null;

    }

}

  
// Три всех суффиксов

class Suffix_tree{

  

    SuffixTrieNode root = new SuffixTrieNode();

  

    // Конструктор (Строит три суффикса из

    // заданный текст)

    Suffix_tree(String txt) {

      

        // Рассмотрим все суффиксы данной строки и

        // вставляем их в суффикс Trie, используя

        // рекурсивная функция insertSuffix () в

        // SuffixTrieNode class

        for (int i = 0; i < txt.length(); i++)

            root.insertSuffix(txt.substring(i), i);

    }

  

    / * Печатает все вхождения pat в Suffix Trie S

    (построено для текста) * /

    void search_tree(String pat) {

      

        // Давайте вызовем рекурсивную функцию поиска для

        // корень три.

        // Получаем список всех индексов (где pat

        // присутствует в тексте) в переменной 'result'

        List<Integer> result = root.search(pat);

  

        // Проверяем, пуст ли список индексов или нет

        if (result == null)

            System.out.println("Pattern not found");

        else {

  

            int patLen = pat.length();

  

            for (Integer i : result)

                System.out.println("Pattern found at position " +

                                                (i - patLen));

        }

    }

  

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

    public static void main(String args[]) {

          

        // Давайте построим суффикс три для текста

        // "geeksforgeeks.org"

        String txt = "geeksforgeeks.org";

        Suffix_tree S = new Suffix_tree(txt);

  

        System.out.println("Search for 'ee'");

        S.search_tree("ee");

  

        System.out.println("\nSearch for 'geek'");

        S.search_tree("geek");

  

        System.out.println("\nSearch for 'quiz'");

        S.search_tree("quiz");

  

        System.out.println("\nSearch for 'forgeeks'");

        S.search_tree("forgeeks");

    }

}
// Этот код предоставлен Sumit Ghosh

C #

// C # реализация подхода

using System;

using System.Collections.Generic;

class SuffixTrieNode

{

    static int MAX_CHAR = 256;

  

    public SuffixTrieNode[] children = new SuffixTrieNode[MAX_CHAR];

    public List<int> indexes;

  

    public SuffixTrieNode() // Конструктор

    {

        // Создать пустой связанный список для индексов

        // суффиксы, начинающиеся с этого узла

        indexes = new List<int>();

  

        // Инициализируем все дочерние указатели как NULL

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

            children[i] = null;

    }

  

    // Рекурсивная функция для вставки суффикса

    // текст в поддереве с корнем из этого узла

    public void insertSuffix(String s, int index) 

    {

          

        // Сохранить индекс в связанном списке

        indexes.Add(index);

  

        // Если в строке больше символов

        if (s.Length > 0)

        {

          

            // Находим первый символ

            char cIndex = s[0];

  

            // Если для этого символа нет ребра,

            // добавить новое ребро

            if (children[cIndex] == null)

                children[cIndex] = new SuffixTrieNode();

  

            // Повтор для следующего суффикса

            children[cIndex].insertSuffix(s.Substring(1),

                                              index + 1);

        }

    }

  

    // Функция для поиска шаблона в поддереве с корнем

    // с этим узлом. Функция возвращает указатель на

    // связанный список, содержащий все индексы, где шаблон

    // настоящее. Возвращенные индексы являются индексами

    // последние символы сопоставленного текста.

    public List<int> search(String s) 

    {

          

        // Если все символы шаблона были

        // обработанный,

        if (s.Length == 0)

            return indexes;

  

        // если есть ребро от текущего узла

        // дерево суффиксов, следуем за краем.

        if (children[s[0]] != null)

            return (children[s[0]]).search(s.Substring(1));

  

        // Если ребра нет, шаблон не существует в

        // текст

        else

            return null;

    }

}

  
// Три всех суффиксов

public class Suffix_tree

{

  

    SuffixTrieNode root = new SuffixTrieNode();

  

    // Конструктор (Строит три суффикса из

    // заданный текст)

    Suffix_tree(String txt) 

    {

      

        // Рассмотрим все суффиксы данной строки и

        // вставляем их в суффикс Trie, используя

        // рекурсивная функция insertSuffix () в

        // SuffixTrieNode class

        for (int i = 0; i < txt.Length; i++)

            root.insertSuffix(txt.Substring(i), i);

    }

  

    / * Печатает все вхождения pat в

    Суффикс Trie S (построен для текста) * /

    void search_tree(String pat) 

    {

      

        // Давайте вызовем рекурсивную функцию поиска

        // для корня Trie.

        // Получаем список всех индексов (где pat

        // присутствует в тексте) в переменной 'result'

        List<int> result = root.search(pat);

  

        // Проверяем, пуст ли список индексов или нет

        if (result == null)

            Console.WriteLine("Pattern not found");

        else 

        {

            int patLen = pat.Length;

  

            foreach (int i in result)

                Console.WriteLine("Pattern found at position " +

                                                  (i - patLen));

        }

    }

  

    // Код драйвера

    public static void Main(String []args) 

    {

          

        // Давайте построим суффикс три для текста

        // "geeksforgeeks.org"

        String txt = "geeksforgeeks.org";

        Suffix_tree S = new Suffix_tree(txt);

  

        Console.WriteLine("Search for 'ee'");

        S.search_tree("ee");

  

        Console.WriteLine("\nSearch for 'geek'");

        S.search_tree("geek");

  

        Console.WriteLine("\nSearch for 'quiz'");

        S.search_tree("quiz");

  

        Console.WriteLine("\nSearch for 'forgeeks'");

        S.search_tree("forgeeks");

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

Search for 'ee'
Pattern found at position 1
Pattern found at position 9

Search for 'geek'
Pattern found at position 0
Pattern found at position 8

Search for 'quiz'
Pattern not found

Search for 'forgeeks'
Pattern found at position 5

Сложность по времени вышеупомянутой функции поиска составляет O (m + k), где m — длина шаблона, а k — количество вхождений шаблона в текст.

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

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

Поиск по шаблону с использованием дерева всех суффиксов

0.00 (0%) 0 votes