Aho-Corasick Algorithm (อัลกอริทึมอาโฮ-โคราซิค)

Aho-Corasick Algorithm เป็นอัลกอริทึม Multi-pattern String Matching ค้นหา หลาย Pattern พร้อมกัน ใน Text เดียวได้ในเวลา Linear ใช้โครงสร้าง Trie (Prefix Tree) พร้อม Failure Links และ Output Links

3 ขั้นตอนหลัก

1. Go-to (Trie Construction): สร้าง Trie จาก Patterns ทั้งหมด
2. Failure (Failure Links): สร้าง Link ชี้ไปสู่ Longest Proper Suffix ที่เป็น Prefix ของ Pattern ใด Pattern หนึ่ง (BFS)
3. Output: รวม Output ของ Failure Link เข้ามา (เพื่อหา Pattern ที่ซ้อนกัน)

ตัวอย่างข้อมูล

Patterns: {their, there, answer, any, bye}
Text:     isthereanyanswerokgoodbye

Output:
Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22

ความซับซ้อน (Complexity)

• Preprocessing: O(L) โดย L = ความยาวรวมของ Patterns ทั้งหมด
• Searching: O(N + Z) โดย N = Text length, Z = จำนวน Matches
• Total: O(N + L + Z) - Linear Time!
• Space: O(L·α) โดย α = Alphabet size

อัลกอริทึม (Pseudocode)

buildTree(patterns)
  create root node (state 0)
  for each pattern:
    insert into trie, create new states as needed
    mark output at final state

  // Build failure links (BFS)
  queue Q
  for each child of root:
    fail[child] = 0
    Q.push(child)

  while Q not empty:
    state = Q.pop()
    for each char ch:
      if goto[state][ch] exists:
        child = goto[state][ch]
        f = fail[state]
        while goto[f][ch] not exists: f = fail[f]
        fail[child] = goto[f][ch]
        output[child] |= output[fail[child]]
        Q.push(child)
      else:
        goto[state][ch] = goto[fail[state]][ch]  // Automaton transition

search(text)
  state = 0
  for i = 0 to text.length-1:
    state = goto[state][text[i]]
    for each pattern in output[state]:
      report pattern found at i - pattern.length + 1

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

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

const int MAXS = 500;  // Sum of pattern lengths
const int MAXC = 26;   // a-z

int out[MAXS];
int fail[MAXS];
int go[MAXS][MAXC];

int buildTree(vector<string> &patterns) {
    fill(out, out+MAXS, 0);
    fill(fail, fail+MAXS, -1);
    for (int i = 0; i < MAXS; i++)
        fill(go[i], go[i]+MAXC, -1);

    int states = 1;
    for (int i = 0; i < patterns.size(); i++) {
        string &word = patterns[i];
        int cur = 0;
        for (char ch : word) {
            int c = ch - 'a';
            if (go[cur][c] == -1) go[cur][c] = states++;
            cur = go[cur][c];
        }
        out[cur] |= (1 << i);
    }

    queue<int> q;
    for (int c = 0; c < MAXC; c++) {
        if (go[0][c] != -1) {
            fail[go[0][c]] = 0;
            q.push(go[0][c]);
        } else {
            go[0][c] = 0;
        }
    }

    while (!q.empty()) {
        int state = q.front(); q.pop();
        for (int c = 0; c < MAXC; c++) {
            if (go[state][c] != -1) {
                int f = fail[state];
                while (go[f][c] == -1) f = fail[f];
                fail[go[state][c]] = go[f][c];
                out[go[state][c]] |= out[fail[go[state][c]]];
                q.push(go[state][c]);
            } else {
                go[state][c] = go[fail[state]][c];
            }
        }
    }
    return states;
}

void search(vector<string> &patterns, string text) {
    buildTree(patterns);
    int state = 0;
    for (int i = 0; i < text.size(); i++) {
        state = go[state][text[i] - 'a'];
        if (out[state] == 0) continue;
        for (int j = 0; j < patterns.size(); j++) {
            if (out[state] & (1 << j)) {
                cout << "Word " << patterns[j] << " location: "
                     << i - patterns[j].size() + 1 << endl;
            }
        }
    }
}

int main() {
    vector<string> patterns = {"their", "there", "answer", "any", "bye"};
    string text = "isthereanyanswerokgoodbye";
    search(patterns, text);
}

การประยุกต์ใช้

• Antivirus: ค้นหา Signature หลายพันรูปแบบ
• Intrusion Detection Systems (IDS)
• Search Engines: Indexing, Query matching
• Bioinformatics: Multiple pattern matching ใน DNA
• Text Editors: Syntax highlighting, Multi-pattern search

ข้อได้เปรียบ

• ค้นหา Multiple Patterns ใน 1 Pass ของ Text
• เวลา Linear ไม่ขึ้นกับจำนวน Patterns
• หา Overlapping Patterns ได้