Рубрики

Aho-Corasick Алгоритм поиска по шаблону

Для заданного входного текста и массива из k слов arr [] найдите все вхождения всех слов во входном тексте. Пусть n — длина текста, а m — общее количество символов во всех словах, т. Е. M = длина (arr [0]) + длина (arr [1]) +… + длина (arr [k-1]). Здесь k — общее количество введенных слов.

Пример:

Input: text = "ahishers"    
       arr[] = {"he", "she", "hers", "his"}

Output:
   Word his appears from 1 to 3
   Word he appears from 4 to 5
   Word she appears from 3 to 5
   Word hers appears from 4 to 7

Если мы используем алгоритм линейного поиска по времени, такой как KMP , то нам нужно один за другим искать все слова в тексте []. Это дает нам общую сложность времени как O (n + длина (слово [0]) + O (n + длина (слово [1]) + O (n + длина (слово [2]) +… O (n + длина ( слово [k-1]). Эта временная сложность может быть записана как O (n * k + m) .
Алгоритм Aho-Corasick находит все слова за время O (n + m + z), где z — общее количество вхождений слов в текст. Алгоритм сопоставления строк Ахо-Корасика лег в основу оригинальной команды Unix fgrep.

  1. Предварительная обработка: Построить автомат из всех слов в arr []. Автомат имеет в основном три функции:
    Go To :   This function simply follows edges
              of Trie of all words in arr[]. It is
              represented as 2D array g[][] where
              we store next state for current state 
              and character.
    
    Failure : This function stores all edges that are
              followed when current character doesn't
              have edge in Trie.  It is represented as
              1D array f[] where we store next state for
              current state. 
    
    Output :  Stores indexes of all words that end at 
              current state. It is represented as 1D 
              array o[] where we store indexes
              of all matching words as a bitmap for 
              current state.
    
  2. Соответствие: пройти заданный текст через встроенный автомат, чтобы найти все подходящие слова.

Предварительная обработка:

  1. Сначала мы строим Trie (или дерево ключевых слов) из всех слов.

    Эта часть заполняет записи в goto g [] [] и выводе o [].

  2. Далее мы расширяем Три до автомата для поддержки линейного сопоставления времени.

    Эта часть заполняет записи в сбое f [] и выводе o [].

Перейти к :
Мы строим Три . И для всех символов, у которых нет ребра в корне, мы добавляем ребро обратно в корень.

Отказ:
Для состояния s мы находим самый длинный правильный суффикс, который является правильным префиксом некоторого шаблона. Это делается с помощью Breadth First Traversal of Trie.

Выход :
Для состояния s сохраняются индексы всех слов, заканчивающихся на s. Эти индексы хранятся в виде побитовой карты (выполняя побитовое ИЛИ значений). Это также вычисление с использованием Breadth First Traversal с ошибкой.

Ниже приведена реализация алгоритма Aho-Corasick на C ++.

// C ++ программа для реализации алгоритма Aho Corasick
// для сопоставления строк

using namespace std;

#include <bits/stdc++.h>

  
// Максимальное количество состояний в соответствующей машине.
// Должно быть равно сумме длины всех ключевых слов.

const int MAXS = 500;

  
// Максимальное количество символов в алфавите ввода

const int MAXC = 26;

  
// ВЫХОДНАЯ ФУНКЦИЯ ОСУЩЕСТВЛЯЕТСЯ ИСПОЛЬЗОВАТЬ []
// бит i в этой маске равен единице, если слово с индексом i
// появляется, когда машина входит в это состояние.

int out[MAXS];

  
// ФУНКЦИЯ ОТКАЗА ОСУЩЕСТВЛЯЕТСЯ ИСПОЛЬЗОВАНИЕМ f []

int f[MAXS];

  
// GOTO FUNCTION (ИЛИ TRIE) ОСУЩЕСТВЛЯЕТСЯ ИСПОЛЬЗОВАНИЕМ g [] []

int g[MAXS][MAXC];

  
// Строит машину соответствия строк.
// arr - массив слов. Индекс каждого ключевого слова важен:
// "out [state] & (1 << i)" равно> 0, если мы только что нашли слово [i]
// в тексте.
// Возвращает количество состояний, которые имеет собранный компьютер.
// Состояния нумеруются от 0 до возвращаемого значения - 1 включительно.

int buildMatchingMachine(string arr[], int k)

{

    // Инициализируем все значения в выходной функции как 0.

    memset(out, 0, sizeof out);

  

    // Инициализировать все значения в функции goto как -1.

    memset(g, -1, sizeof g);

  

    // Изначально у нас просто состояние 0

    int states = 1;

  

    // Создаем значения для функции goto, т.е. заполняем g [] []

    // Это то же самое, что создание Trie для arr []

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

    {

        const string &word = arr[i];

        int currentState = 0;

  

        // Вставляем все символы текущего слова в arr []

        for (int j = 0; j < word.size(); ++j)

        {

            int ch = word[j] - 'a';

  

            // Выделить новый узел (создать новое состояние), если

            // узел для ch не существует.

            if (g[currentState][ch] == -1)

                g[currentState][ch] = states++;

  

            currentState = g[currentState][ch];

        }

  

        // Добавить текущее слово в выходную функцию

        out[currentState] |= (1 << i);

    }

  

    // Для всех символов, которые не имеют ребра из

    // корень (или состояние 0) в Trie, добавление края перехода к состоянию

    // 0 сам

    for (int ch = 0; ch < MAXC; ++ch)

        if (g[0][ch] == -1)

            g[0][ch] = 0;

  

    // Теперь давайте построим функцию сбоя

  

    // Инициализировать значения в функции сбоя

    memset(f, -1, sizeof f);

  

    // Функция отказа вычисляется в первом порядке по ширине

    // используя очередь

    queue<int> q;

  

     // Перебираем все возможные входные данные

    for (int ch = 0; ch < MAXC; ++ch)

    {

        // Все узлы глубины 1 имеют значение функции отказа

        // как 0. Например, на приведенной выше диаграмме мы переходим к 0

        // из состояний 1 и 3.

        if (g[0][ch] != 0)

        {

            f[g[0][ch]] = 0;

            q.push(g[0][ch]);

        }

    }

  

    // Теперь очередь имеет состояния 1 и 3

    while (q.size())

    {

        // Удалить фронтальное состояние из очереди

        int state = q.front();

        q.pop();

  

        // Для удаленного состояния найти функцию сбоя для

        // все те символы, для которых функция goto

        // не определено.

        for (int ch = 0; ch <= MAXC; ++ch)

        {

            // Если функция goto определена для символа 'ch'

            // и «состояние»

            if (g[state][ch] != -1)

            {

                // Найти состояние ошибки удаленного состояния

                int failure = f[state];

  

                // Находим самый глубокий узел, помеченный правильным

                // суффикс строки от корня до текущего

                // государство.

                while (g[failure][ch] == -1)

                      failure = f[failure];

  

                failure = g[failure][ch];

                f[g[state][ch]] = failure;

  

                // Объединяем выходные значения

                out[g[state][ch]] |= out[failure];

  

                // Вставляем узел следующего уровня (Trie) в очередь

                q.push(g[state][ch]);

            }

        }

    }

  

    return states;

}

  
// Возвращает следующее состояние, на которое машина перейдет, используя goto
// и функции отказа.
// currentState - текущее состояние машины. Должно быть между
// 0 и количество состояний - 1 включительно.
// nextInput - следующий символ, который входит в машину.

int findNextState(int currentState, char nextInput)

{

    int answer = currentState;

    int ch = nextInput - 'a';

  

    // Если goto не определено, используйте функцию сбоя

    while (g[answer][ch] == -1)

        answer = f[answer];

  

    return g[answer][ch];

}

  
// Эта функция находит все вхождения всех слов массива
// в текст.

void searchWords(string arr[], int k, string text)

{

    // Шаблоны предварительной обработки.

    // Сборка машины с функциями goto, fail и output

    buildMatchingMachine(arr, k);

  

    // Инициализируем текущее состояние

    int currentState = 0;

  

    // Пройдемся по тексту через нуль-машину, чтобы найти

    // все вхождения слов в arr []

    for (int i = 0; i < text.size(); ++i)

    {

        currentState = findNextState(currentState, text[i]);

  

        // Если совпадение не найдено, перейти в следующее состояние

        if (out[currentState] == 0)

             continue;

  

        // Найдено совпадение, вывести все подходящие слова из arr []

        // используя функцию вывода.

        for (int j = 0; j < k; ++j)

        {

            if (out[currentState] & (1 << j))

            {

                cout << "Word " << arr[j] << " appears from "

                     << i - arr[j].size() + 1 << " to " << i << endl;

            }

        }

    }

}

  
// Программа драйвера для тестирования выше

int main()

{

    string arr[] = {"he", "she", "hers", "his"};

    string text = "ahishers";

    int k = sizeof(arr)/sizeof(arr[0]);

  

    searchWords(arr, k, text);

  

    return 0;

}

Выход:

Word his appears from 1 to 3
Word he appears from 4 to 5
Word she appears from 3 to 5
Word hers appears from 4 to 7

Источник:
http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf

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

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

Aho-Corasick Алгоритм поиска по шаблону

0.00 (0%) 0 votes