Thuật toán Aho-Corasick (Tìm kiếm đa mẫu)

Aho-Corasick tìm tất cả occurrence của tập từ khóa cho trước. Là thuật toán dictionary-matching. Dùng cấu trúc cây (trie) từ các từ khóa, chuyển thành automation để tìm kiếm tuyến tính.

Ba giai đoạn: Go-to (xây trie), Failure (chuyển tiếp lùi để tìm suffix), Output (tìm từ khóa kết thúc tại state).

Độ phức tạp: O(N + L + Z), N=độ dài text, L=tổng độ dài từ khóa, Z=số match.

Input và Output

Input: 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

Thuật toán

buildTree(patternList, size) - Xây trie + failure links + output links

Begin
  khởi tạo output=0, fail=-1, goto=-1
  state := 1
  for pattern i in patternList do
    word := patternList[i], present := 0
    for char ch in word do
      if goto[present,ch] = -1 then goto[present,ch] := state++
      present := goto[present,ch]
    done
    output[present] |= (1 << i)
  done
  for all chars ch do
    if goto[0,ch] ≠ 0 then fail[goto[0,ch]] := 0, push goto[0,ch] to queue
  done
  while queue not empty do
    state := pop queue
    for all chars ch do
      if goto[state,ch] ≠ -1 then
        failure := fail[state]
        while goto[failure,ch] = -1 do failure := fail[failure] done
        fail[goto[state,ch]] := failure
        output[goto[state,ch]] |= output[failure]
        push goto[state,ch] to queue
      done
    done
  done
  return state
End

getNextState(currentState, nextChar)

Begin
  answer := currentState, ch := nextChar
  while goto[answer,ch] = -1 do answer := fail[answer] done
  return goto[answer,ch]
End

patternSearch(patternList, size, text)

Begin
  gọi buildTree
  presentState := 0
  for i := 0 to text.length-1 do
    presentState := getNextState(presentState, text[i])
    if output[presentState] = 0 then continue
    for j := 0 to size-1 do
      if pattern j found via output then in location i - len(pattern) + 1
    done
  done
End

Ví dụ (C++)

#include <iostream>
#include <queue>
#include <string>
#define MAXS 500
#define MAXC 26
using namespace std;

int output[MAXS], fail[MAXS], gotoMat[MAXS][MAXC];

int buildTree(string patterns[], int size) {
    // khởi tạo
    for(int i=0;i
Kết quả
Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22
Ứng dụng: Antivirus (signature matching), intrusion detection, text search engines, bioinformatics (DNA pattern matching).