Aho-Corasick-algoritmus

Üdvözlöm, Ön a Aho-Corasick-algoritmus szó jelentését keresi. A DICTIOUS-ban nem csak a Aho-Corasick-algoritmus szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a Aho-Corasick-algoritmus szót egyes és többes számban mondani. Minden, amit a Aho-Corasick-algoritmus szóról tudni kell, itt található. A Aho-Corasick-algoritmus szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. AAho-Corasick-algoritmus és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Kiejtés

  • IPA:

Főnév

Aho-Corasick-algoritmus

  1. (matematika) Az Aho-Corasick-algoritmus egy hatékony szövegfeldolgozási algoritmus, amelyet több minta egyidejű keresésére használnak egy adott szövegben. Az algoritmust Alfred V. Aho és Margaret J. Corasick dolgozta ki 1975-ben.



Jellemzők

  1. Többminta-keresés:
    • Az algoritmus egy prefixfa (trie) és egy állapotátmeneti automata segítségével képes több minta egyidejű keresésére.
  2. Hatékonyság:
    • Az előfeldolgozási idő (O(L)), ahol (L) az összes minta karaktereinek összhossza.
    • A keresési idő (O(n + k)), ahol (n) a szöveg hossza, (k) pedig az összes találat száma.
  3. Szövegelemzés:
    • Gyakran alkalmazzák szövegelemzésben, pl. szöveges adatbányászatban, kódolvasókban és víruskeresőkben.



Algoritmus felépítése

  1. Prefixfa építése:
    • Hozz létre egy prefixfát (trie), amely tartalmazza az összes keresett mintát.
  2. Hibaszálak (fail links):
    • Adj hozzá hibaszálakat, amelyek lehetővé teszik, hogy az automata visszaugorjon egy megfelelő állapotba, ha az aktuális karakter nem illik egy minta folytatásába.
  3. Keresés:
    • Járd be a szöveget az automata segítségével.
    • Minden állapotátmenet során ellenőrizd, hogy találtál-e egyezést.



Algoritmus lépései

1. Prefixfa építése

Minden mintát helyezz el egy prefixfában, ahol minden karakter egy él, és az utak a minták végeit jelölik.

2. Hibaszálak hozzáadása

  • Ha egy csomópontból nincs átmenet egy adott karakterre, egy hibaszálat hozunk létre, amely visszavisz a leghosszabb megfelelő előtaghoz.
  • Ez a mechanizmus lehetővé teszi, hogy gyorsan folytassuk a keresést anélkül, hogy újra bejárnánk a már feldolgozott szövegrészeket.

3. Keresés a szövegben

  • Az algoritmus végighalad a szövegen karakterenként.
  • Ha talál egy mintát, jelzi a találatot.
  • A hibaszálak használatával az automata gyorsan tud visszaugrani az előző állapotokba, így biztosítva az (O(n + k)) időkomplexitást.



Pszeudokód

Építés

BuildAutomaton(patterns):
    1. Hozz létre egy üres prefixfát (trie)
    2. Minden mintát helyezz el a prefixfában
    3. Hozz létre hibaszálakat:
        - Sorban állítsd be minden csomópont hibaszálát
        - A gyökér hibaszála a gyökérre mutat

Keresés

Search(text, automaton):
    állapot = automaton.gyökér
    minden karakter a text-ben:
        amíg nincs átmenet az állapotból:
            állapot = állapot.hibaszála
        állapot = állapot.következő(karakter)
        ha állapot egy végállapot:
            jegyezd fel a találatot

Python implementáció

from collections import deque, defaultdict

class AhoCorasick:
    def __init__(self):
        self.trie = defaultdict(dict)
        self.fail = {}
        self.output = defaultdict(list)
        self.root = 0
        self.state_count = 1

    def build_trie(self, patterns):
        for pattern in patterns:
            state = self.root
            for char in pattern:
                if char not in self.trie:
                    self.trie = self.state_count
                    self.state_count += 1
                state = self.trie
            self.output.append(pattern)

    def build_automaton(self):
        queue = deque()
        for char, next_state in self.trie.items():
            self.fail = self.root
            queue.append(next_state)

        while queue:
            state = queue.popleft()
            for char, next_state in self.trie.items():
                queue.append(next_state)
                fail_state = self.fail
                while fail_state != self.root and char not in self.trie:
                    fail_state = self.fail
                self.fail = self.trie.get(char, self.root)
                self.output.extend(self.output])

    def search(self, text):
        state = self.root
        matches = 
        for i, char in enumerate(text):
            while state != self.root and char not in self.trie:
                state = self.fail
            state = self.trie.get(char, self.root)
            if self.output:
                for pattern in self.output:
                    matches.append((i - len(pattern) + 1, pattern))
        return matches

# Példa használat
patterns = 
text = "ushers"

ac = AhoCorasick()
ac.build_trie(patterns)
ac.build_automaton()

matches = ac.search(text)
print("Találatok:", matches)

Kimenet:

Találatok: 

C++ implementáció

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>

using namespace std;

struct Node {
    unordered_map<char, int> children;
    int fail = 0;
    vector<string> output;
};

class AhoCorasick {
    vector<Node> trie;

public:
    AhoCorasick() {
        trie.emplace_back();  // Root node
    }

    void build_trie(const vector<string>& patterns) {
        for (const string& pattern : patterns) {
            int state = 0;
            for (char c : pattern) {
                if (!trie.children.count(c)) {
                    trie.children = trie.size();
                    trie.emplace_back();
                }
                state = trie.children;
            }
            trie.output.push_back(pattern);
        }
    }

    void build_automaton() {
        queue<int> q;
        for (auto&  : trie.children) {
            trie.fail = 0;
            q.push(value);
        }

        while (!q.empty()) {
            int state = q.front();
            q.pop();

            for (auto&  : trie.children) {
                int fail = trie.fail;
                while (fail != 0 && !trie.children.count(key)) {
                    fail = trie.fail;
                }
                trie.fail = trie.children.count(key) ? trie.children : 0;
                trie.output.insert(
                    trie.output.end(),
                    trie.fail].output.begin(),
                    trie.fail].output.end()
                );
                q.push(next_state);
            }
        }
    }

    vector<pair<int, string>> search(const string& text) {
        vector<pair<int, string>> matches;
        int state = 0;

        for (int i = 0; i < text.size(); ++i) {
            char c = text;
            while (state != 0 && !trie.children.count(c)) {
                state = trie.fail;
            }
            state = trie.children.count(c) ? trie.children : 0;

            for (const string& pattern : trie.output) {
                matches.emplace_back(i - pattern.size() + 1, pattern);
            }
        }
        return matches;
    }
};

int main() {
    vector<string> patterns = {"he", "she", "his", "hers"};
    string text = "ushers";

    AhoCorasick ac;
    ac.build_trie(patterns);
    ac.build_automaton();

    auto matches = ac.search(text);
    cout << "Találatok:" << endl;
    for (auto&  : matches) {
        cout << "Pozíció: " << pos << ", Minta: " << pattern << endl;
    }

    return 0;
}

Kimenet:

Találatok:
Pozíció: 1, Minta: he
Pozíció: 1, Minta: she
Pozíció: 2, Minta: hers

Összegzés

Előnyök:

  1. Hatékony, több mintát egyszerre kezel.
  2. Determinisztikus időkomplexitás: (O(n + L + k)).
  3. Széleskörű alkalmazhatóság szövegfeldolgozásban.

Hátrányok:

  1. Magas memóriaigény a trie és hibaszálak tárolása miatt.
  2. Összetett implementáció.

Az Aho-Corasick-algoritmus kiváló választás, ha nagy mennyiségű minta gyors keresésére van szükség egy szövegben, például kódvizsgálat, víruskeresés vagy nyelvi elemzés során.