อัลกอริทึม Aho-Corasick สำหรับ Pattern Searching ใน C++

ในปัญหานี้ กำหนดให้มีสตริงนำเข้า (input string) และอาร์เรย์ arr[] ภารกิจคือหาตำแหน่งของคำทุกคำในอาร์เรย์ที่ปรากฏในสตริง โดยใช้ Aho-Corasick Algorithm for Pattern Searching

การค้นหาสตริงและรูปแบบ (pattern searching) สำคัญในการเขียนโปรแกรม อัลกอริทึม Aho-Corasick เป็น อัลกอริทึมที่ทรงพลังมาก ทำให้การค้นหาสตริงหลายรูปแบบพร้อมกันง่ายขึ้น เป็นประเภท Dictionary Matching Algorithm ใช้โครงสร้างข้อมูล Trie

โครงสร้างข้อมูล Trie

Trie เป็น Prefix Tree หรือ Digital Search Tree ที่แต่ละขอบ (edge) มีป้ายกำกับตัวอักษร (ขอบออกจากโหนดเดียวกันจะมีตัวอักษรต่างกัน)

ตัวอย่าง

Input: string = "bheythisghisanexample", arr[] = {"hey", "this", "is", "an", "example"}
Output: พบคำต่างๆ ที่ตำแหน่งเริ่มต้น 2, 5, 11, 13, 15

Time Complexity: O(N + L + Z) โดย N=ความยาวสตริง, L=ความยาวคีย์เวิร์ดรวม, Z=จำนวนครั้งที่เจอ

ขั้นตอนการสร้าง

1. สร้าง Trie โดยใช้ Queue
2. สร้าง Failure Links (Suffix Links) เป็นอาร์เรย์เก็บขอบที่ต้องติดตามเมื่อตัวอักษรปัจจุบันไม่มีขอบใน Trie
3. สร้าง Output Links เป็นอาร์เรย์เก็บคำที่จับคู่
4. สร้างฟังก์ชัน Traverse (FindNextState) ตรวจสอบทุกตัวอักษร

Failure Link และ Output Link

• Failure Link (Suffix Link): เมื่ออ่านตัวอักษรต่อไม่ได้ ให้ย้อนกลับตาม Suffix Link เพื่อรักษาบริบทมากที่สุด
• Output Link: ชี้ไปโหนดที่ตรงกับคำที่ยาวที่สุดในสถานะปัจจุบัน ทำให้เชื่อมคำที่จับคู่ได้ทั้งหมด

โค้ดตัวอย่าง

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
using namespace std;

const int MaxStates = 6 * 50 + 10;
const int MaxChars = 26;

int OccurenceOfWords[MaxStates];
int FF[MaxStates];
int GotoFunction[MaxStates][MaxChars];

int BuildMatchingMachine(const vector<string> &words, char lowestChar = 'a', char highestChar = 'z') {
    memset(OccurenceOfWords, 0, sizeof OccurenceOfWords);
    memset(FF, -1, sizeof FF);
    memset(GotoFunction, -1, sizeof GotoFunction);
    
    int states = 1;
    for (int i = 0; i < words.size(); ++i) {
        const string &keyword = words[i];
        int currentState = 0;
        for (int j = 0; j < keyword.size(); ++j) {
            int c = keyword[j] - lowestChar;
            if (GotoFunction[currentState][c] == -1)
                GotoFunction[currentState][c] = states++;
            currentState = GotoFunction[currentState][c];
        }
        OccurenceOfWords[currentState] |= (1 << i);
    }
    
    for (int c = 0; c < MaxChars; ++c)
        if (GotoFunction[0][c] == -1)
            GotoFunction[0][c] = 0;
    
    queue<int> q;
    for (int c = 0; c <= highestChar - lowestChar; ++c) {
        if (GotoFunction[0][c] != -1 && GotoFunction[0][c] != 0) {
            FF[GotoFunction[0][c]] = 0;
            q.push(GotoFunction[0][c]);
        }
    }
    
    while (q.size()) {
        int state = q.front(); q.pop();
        for (int c = 0; c <= highestChar - lowestChar; ++c) {
            if (GotoFunction[state][c] != -1) {
                int failure = FF[state];
                while (GotoFunction[failure][c] == -1)
                    failure = FF[failure];
                failure = GotoFunction[failure][c];
                FF[GotoFunction[state][c]] = failure;
                OccurenceOfWords[GotoFunction[state][c]] |= OccurenceOfWords[failure];
                q.push(GotoFunction[state][c]);
            }
        }
    }
    return states;
}

int FindNextState(int currentState, char nextInput, char lowestChar = 'a') {
    int answer = currentState;
    int c = nextInput - lowestChar;
    while (GotoFunction[answer][c] == -1)
        answer = FF[answer];
    return GotoFunction[answer][c];
}

vector<int> FindWordCount(string str, vector<string> keywords, char lowestChar = 'a', char highestChar = 'z') {
    BuildMatchingMachine(keywords, lowestChar, highestChar);
    int currentState = 0;
    vector<int> retVal;
    for (int i = 0; i < str.size(); ++i) {
        currentState = FindNextState(currentState, str[i], lowestChar);
        if (OccurenceOfWords[currentState] == 0) continue;
        for (int j = 0; j < keywords.size(); ++j) {
            if (OccurenceOfWords[currentState] & (1 << j))
                retVal.insert(retVal.begin(), i - keywords[j].size() + 1);
        }
    }
    return retVal;
}

int main() {
    vector<string> keywords;
    keywords.push_back("All");
    keywords.push_back("she");
    keywords.push_back("is");
    string str = "Allisheall";
    cout << "The occurrences of all words in the string '" << str << "' are \n";
    vector<int> states = FindWordCount(str, keywords);
    for (int i = 0; i < keywords.size(); i++) {
        cout << "Word " << keywords.at(i) << "' starts at " << states.at(i)+1 << "' ";
        cout << "And ends at " << states.at(i)+keywords.at(i).size()+1 << endl;
    }
}

ผลลัพธ์

The occurrences of all words in the string ' Allisheall ' are
Word All starts at 5 And ends at 8
Word she starts at 4 And ends at 7
Word is starts at 1 And ends at 3