Aho-Corasick 算法
用于模式匹配的 Aho-Corasick 算法
Aho-Corasick 算法是一种字典匹配算法，可以在线性时间内找到给定文本中所有模式集合的所有出现位置。该算法由 Alfred V. Aho 和 Margaret J. Corasick 于 1975 年开发，广泛应用于恶意软件检测、文本分析和自然语言处理等应用领域。
Aho-Corasick 算法的工作原理是什么？
Aho-Corasick 算法只需遍历文本一次即可搜索所有模式，并且不会进行任何不必要的回溯。它可以处理不同长度的多个关键字，并且可以轻松处理重叠匹配。
该算法借助 trie 数据结构来跟踪搜索到的模式。 trie 是一种基于树的数据结构，主要用于存储字符串。
让我们通过一个例子来理解 −
输入：
模式集 = {their, there, any, bye}
主字符串 = "isthereanyanswerokgoodbye"
输出：
单词 there 位置：2
单词 any 位置：7
单词 bye 位置：22
Aho-Corasick 算法包含以下步骤 −
- 预处理
- 搜索/匹配
预处理阶段
在预处理步骤中，我们根据关键词构建有限状态机（trie）。trie 为每个关键词的前缀创建一个节点，并为前缀的每个可能扩展创建一个以字符标记的边。trie 的根节点表示空前缀，最后一个节点标记为最终节点。
预处理步骤进一步分为三个子步骤 −
进入阶段 − 此阶段根据模式的特征定义状态之间的转换。它以二维数组的形式表示。
失败阶段 −它定义了不匹配发生时状态之间的转换。它表示为一个一维数组。
输出阶段 − 在此阶段，算法存储所有以给定状态结束的模式的索引。它也用一个一维数组表示。
搜索/匹配阶段
搜索步骤是通过从左到右扫描文本，并根据文本中的字符跟踪 trie 中的边和失败链接来完成的。每当我们到达最后一个节点时，我们就会报告文本中相应关键字的匹配。
示例
以下示例演示了 Aho-Corasick 算法在不同编程语言中的工作原理。
#include <stdio.h>
#include <string.h>
#define MAXS 500 // 所有模式的长度总和
#define MAXC 26 // 字母表中的 26 个字母
int output[MAXS];
int fail[MAXS];
int gotoMat[MAXS][MAXC];
int buildTree(char* array[], int size) {
for(int i = 0; i<MAXS; i++)
output[i] = 0; // 输出数组的所有元素都为 0
for(int i = 0; i<MAXS; i++)
fail[i] = -1; // 失败数组的所有元素都是-1
for(int i = 0; i<MAXS; i++)
for(int j = 0; j<MAXC; j++)
gotoMat[i][j] = -1; // goto矩阵的所有元素都是-1
// 初始状态
int state = 1;
// 对数组中的所有模式建立 trie
for (int i = 0; i < size; i++) {
char* word = array[i];
int presentState = 0;
// 添加模式
for (int j = 0; j < strlen(word); ++j) {
int ch = word[j] - 'a';
if (gotoMat[presentState][ch] == -1)
// 增加状态
gotoMat[presentState][ch] = state++;
presentState = gotoMat[presentState][ch];
}
// 在输出中添加当前单词
output[presentState] |= (1 << i);
}
// 如果 ch 没有直接连接到根节点
for (int ch = 0; ch < MAXC; ++ch)
if (gotoMat[0][ch] == -1)
gotoMat[0][ch] = 0;
// 节点发生故障时恢复到先前状态
for (int ch = 0; ch < MAXC; ++ch) {
if (gotoMat[0][ch] != 0) {
fail[gotoMat[0][ch]] = 0;
// 将下一级节点添加到队列
int q[MAXS], front = 0, rear = 0;
q[rear++] = gotoMat[0][ch];
while (front != rear) {
// 删除前节点
int state = q[front++];
for (int ch = 0; ch <= MAXC; ++ch) {
// 如果存在 goto 状态
if (gotoMat[state][ch] != -1) {
int failure = fail[state];
// 找到具有适当后缀的最深节点
while (gotoMat[failure][ch] == -1)
failure = fail[failure];
failure = gotoMat[failure][ch];
fail[gotoMat[state][ch]] = failure;
// 合并输出值
output[gotoMat[state][ch]] |= output[failure];
// 将下一级节点添加到队列
q[rear++] = gotoMat[state][ch];
}
}
}
}
}
return state;
}
int getNextState(int presentState, char nextChar) {
int answer = presentState;
int ch = nextChar - 'a'; //减去'a'的ascii
// 如果未找到 go to，则使用失败函数
while (gotoMat[answer][ch] == -1)
answer = fail[answer];
return gotoMat[answer][ch];
}
void patternSearch(char* arr[], int size, char* text) {
buildTree(arr, size); // 制作 trie 结构
int presentState = 0; // 使当前状态为 0
// 查找所有出现的模式
for (int i = 0; i < strlen(text); i++) {
presentState = getNextState(presentState, text[i]);
// 匹配找到并打印的单词
for (int j = 0; j < size; ++j) {
if (output[presentState] & (1 << j)) {
printf("Word %s location: %zu
", arr[j], i - strlen(arr[j]) + 1);
}
}
}
}
int main() {
char* arr[] = {"their", "there", "answer", "any", "bye"};
char* text = "isthereanyanswerokgoodbye";
int k = sizeof(arr)/sizeof(arr[0]);
patternSearch(arr, k, text);
return 0;
}
#include <iostream>
#include <queue>
#define MAXS 500 // 所有模式的长度总和
#define MAXC 26 // 字母表中的 26 个字母
using namespace std;
int output[MAXS];
int fail[MAXS];
int gotoMat[MAXS][MAXC];
int buildTree(string array[], int size) {
for(int i = 0; i<MAXS; i++)
output[i] = 0; // 输出数组的所有元素都为 0
for(int i = 0; i<MAXS; i++)
fail[i] = -1; // 失败数组的所有元素都是-1
for(int i = 0; i<MAXS; i++)
for(int j = 0; j<MAXC; j++)
gotoMat[i][j] = -1; // goto矩阵的所有元素都是-1
// 初始状态
int state = 1;
// 对数组中的所有模式建立 trie
for (int i = 0; i < size; i++) {
string word = array[i];
int presentState = 0;
// 添加模式
for (int j = 0; j < word.size(); ++j) {
int ch = word[j] - 'a';
if (gotoMat[presentState][ch] == -1)
// 增加状态
gotoMat[presentState][ch] = state++;
presentState = gotoMat[presentState][ch];
}
// 在输出中添加当前单词
output[presentState] |= (1 << i);
}
// 如果 ch 没有直接连接到根节点
for (int ch = 0; ch < MAXC; ++ch)
if (gotoMat[0][ch] == -1)
gotoMat[0][ch] = 0;
queue<int> q;
// 节点发生故障时恢复到先前状态
for (int ch = 0; ch < MAXC; ++ch) {
if (gotoMat[0][ch] != 0) {
fail[gotoMat[0][ch]] = 0;
q.push(gotoMat[0][ch]);
}
}
while (q.size()) {
// 删除前节点
int state = q.front();
q.pop();
for (int ch = 0; ch <= MAXC; ++ch) {
// 如果存在 goto 状态
if (gotoMat[state][ch] != -1) {
int failure = fail[state];
// 找到具有适当后缀的最深节点
while (gotoMat[failure][ch] == -1)
failure = fail[failure];
failure = gotoMat[failure][ch];
fail[gotoMat[state][ch]] = failure;
// 合并输出值
output[gotoMat[state][ch]] |= output[failure];
// 将下一级节点添加到队列
q.push(gotoMat[state][ch]);
}
}
}
return state;
}
int getNextState(int presentState, char nextChar) {
int answer = presentState;
int ch = nextChar - 'a'; //减去'a'的ascii
// 如果未找到 go to，则使用失败函数
while (gotoMat[answer][ch] == -1)
answer = fail[answer];
return gotoMat[answer][ch];
}
void patternSearch(string arr[], int size, string text) {
buildTree(arr, size); // 制作 trie 结构
int presentState = 0; // 使当前状态为 0
// 查找所有出现的模式
for (int i = 0; i < text.size(); i++) {
presentState = getNextState(presentState, text[i]);
// 匹配找到并打印的单词
for (int j = 0; j < size; ++j) {
if (output[presentState] & (1 << j)) {
cout << "Word " << arr[j] << " location: " << i - arr[j].size() + 1 << endl;
}
}
}
}
int main() {
string arr[] = {"their", "there", "answer", "any", "bye"};
string text = "isthereanyanswerokgoodbye";
int k = sizeof(arr)/sizeof(arr[0]);
patternSearch(arr, k, text);
return 0;
}
import java.util.*;
public class Main {
static final int MAXS = 500; // 所有模式的长度总和
static final int MAXC = 26; // 字母表中的 26 个字母
static int[] output = new int[MAXS];
static int[] fail = new int[MAXS];
static int[][] gotoMat = new int[MAXS][MAXC];
// method to construct trie
static int buildTree(String[] array, int size) {
for(int i = 0; i<MAXS; i++)
output[i] = 0; // 输出数组的所有元素都为 0
for(int i = 0; i<MAXS; i++)
fail[i] = -1; // 失败数组的所有元素都是-1
for(int i = 0; i<MAXS; i++)
for(int j = 0; j<MAXC; j++)
gotoMat[i][j] = -1; // goto矩阵的所有元素都是-1
// 初始状态
int state = 1;
// 对数组中的所有模式建立 trie
for (int i = 0; i < size; i++) {
String word = array[i];
int presentState = 0;
// 添加模式
for (int j = 0; j < word.length(); ++j) {
int ch = word.charAt(j) - 'a';
if (gotoMat[presentState][ch] == -1)
// 增加状态
gotoMat[presentState][ch] = state++;
presentState = gotoMat[presentState][ch];
}
// 在输出中添加当前单词
output[presentState] |= (1 << i);
}
// 如果 ch 没有直接连接到根节点
for (int ch = 0; ch < MAXC; ++ch)
if (gotoMat[0][ch] == -1)
gotoMat[0][ch] = 0;
Queue<Integer> q = new LinkedList<>();
// 节点发生故障时恢复到先前状态
for (int ch = 0; ch < MAXC; ++ch) {
if (gotoMat[0][ch] != 0) {
fail[gotoMat[0][ch]] = 0;
q.add(gotoMat[0][ch]);
}
}
while (!q.isEmpty()) {
// 删除前节点
state = q.poll();
for (int ch = 0; ch < MAXC; ++ch) {
// 如果存在 goto 状态
if (gotoMat[state][ch] != -1) {
int failure = fail[state];
// 找到具有适当后缀的最深节点
while (gotoMat[failure][ch] == -1)
failure = fail[failure];
failure = gotoMat[failure][ch];
fail[gotoMat[state][ch]] = failure;
// 合并输出值
output[gotoMat[state][ch]] |= output[failure];
// 将下一级节点添加到队列
q.add(gotoMat[state][ch]);
}
}
}
return state;
}
static int getNextState(int presentState, char nextChar) {
int answer = presentState;
int ch = nextChar - 'a'; //减去'a'的ascii
// 如果未找到 go to，则使用失败函数
while (gotoMat[answer][ch] == -1)
answer = fail[answer];
return gotoMat[answer][ch];
}
static void patternSearch(String[] arr, int size, String text) {
buildTree(arr, size); // 制作 trie 结构
int presentState = 0; // 使当前状态为 0
// 查找所有出现的模式
for (int i = 0; i < text.length(); i++) {
presentState = getNextState(presentState, text.charAt(i));
// 匹配找到并打印的单词
for (int j = 0; j < size; ++j) {
if ((output[presentState] & (1 << j)) != 0) {
System.out.println("Word " + arr[j] + " location: " + (i - arr[j].length() + 1));
}
}
}
}
public static void main(String[] args) {
String[] arr = {"their", "there", "answer", "any", "bye"};
String text = "isthereanyanswerokgoodbye";
int k = arr.length;
patternSearch(arr, k, text);
}
}
from collections import deque
MAXS = 500 # 所有模式的长度总和
MAXC = 26 # 字母表中的 26 个字母
output = [0]*MAXS
fail = [-1]*MAXS
gotoMat = [[-1]*MAXC for _ in range(MAXS)]
# 构造 trie 的函数
def buildTree(array):
global output, fail, gotoMat
size = len(array)
# 初始状态
state = 1
# 对数组中的所有模式建立 trie
for i in range(size):
word = array[i]
presentState = 0
# adding pattern
for j in range(len(word)):
ch = ord(word[j]) - ord('a')
if gotoMat[presentState][ch] == -1:
# increasing state
gotoMat[presentState][ch] = state
state += 1
presentState = gotoMat[presentState][ch]
# 在输出中添加当前单词
output[presentState] |= (1 << i)
# 如果 ch 没有直接连接到根节点
for ch in range(MAXC):
if gotoMat[0][ch] == -1:
gotoMat[0][ch] = 0
q = deque()
# 节点发生故障时恢复到先前状态
for ch in range(MAXC):
if gotoMat[0][ch] != 0:
fail[gotoMat[0][ch]] = 0
q.append(gotoMat[0][ch])
while q:
# 删除前节点
state = q.popleft()
for ch in range(MAXC):
# 如果存在 goto 状态
if gotoMat[state][ch] != -1:
failure = fail[state]
# 找到具有适当后缀的最深节点
while gotoMat[failure][ch] == -1:
failure = fail[failure]
failure = gotoMat[failure][ch]
fail[gotoMat[state][ch]] = failure
# 合并输出值
output[gotoMat[state][ch]] |= output[failure]
# 将下一级节点添加到队列
q.append(gotoMat[state][ch])
return state
def getNextState(presentState, nextChar):
answer = presentState
ch = ord(nextChar) - ord('a') #subtract ascii of 'a'
# 如果未找到 go to，则使用失败函数
while gotoMat[answer][ch] == -1:
answer = fail[answer]
return gotoMat[answer][ch]
def patternSearch(arr, text):
buildTree(arr) # 制作 trie 结构
presentState = 0 # 使当前状态为 0
size = len(arr)
# 查找所有出现的模式
for i in range(len(text)):
presentState = getNextState(presentState, text[i])
# 匹配找到并打印的单词
for j in range(size):
if (output[presentState] & (1 << j)) != 0:
print(f"Word {arr[j]} location: {i - len(arr[j]) + 1}")
def main():
arr = ["their", "there", "answer", "any", "bye"]
text = "isthereanyanswerokgoodbye"
patternSearch(arr, text)
if __name__ == "__main__":
main()
输出
Word there location: 2 Word any location: 7 Word answer location: 10 Word bye location: 22
