Aho–Corasick 算法

共计 1368 个字符，预计需要花费 4 分钟才能阅读完成。

1. Aho–Corasick 算法简介

Aho–Corasick（简称 AC 自动机 ）是一个多模式匹配算法，由 Alfred V. Aho 和 Margaret J. Corasick 在 1975 年提出。
它的主要作用是： 在一段文本中同时搜索多个关键词 ，并且时间复杂度接近 O(文本长度)，几乎与单次搜索一样快。

核心思想：

1. Trie 树 ：把所有敏感词组织成一棵前缀树；
2. 失败指针 （类似 KMP 的回退机制）：当匹配失败时，自动跳转到下一个可能的匹配位置；
3. 状态机遍历 ：扫描文本时，只需要逐字符走状态机，就能一次性检测出所有关键词。

因此，哪怕有 几十万敏感词 ，AC 自动机也能在一遍扫描文本时完成检测，非常高效。

2. pyahocorasick 库

pyahocorasick 是 Python 的 AC 自动机实现，C 扩展写的，性能很高。
官网：PyPI - pyahocorasick

安装：

pip install pyahocorasick

常用 API：

• ahocorasick.Automaton()：创建一个自动机对象；
• add_word(word, value)：向自动机中加入关键词；
• make_automaton()：构建自动机（必须调用）；
• iter(text)：在文本中迭代匹配结果，返回 (end_index, value)。

3. 示例

import ahocorasick
import pandas as pd

class SensitiveWordDetector:
    def __init__(self, filepath: str):
        """ 初始化，读取 xlsx 并构建 AC 自动机 """
        words = self._load_sensitive_words(filepath)
        self.automaton = self._build_automaton(words)

    def _load_sensitive_words(self, filepath):
        # 读取第一列，去掉空值
        df = pd.read_excel(filepath, usecols=[0], header=None)
        return df[0].dropna().astype(str).tolist()

    def _build_automaton(self, words):
        A = ahocorasick.Automaton()
        for idx, word in enumerate(words):
            A.add_word(word, word)  # 直接存敏感词本身
        A.make_automaton()
        return A

    def check(self, text: str):
        """ 检测文本中是否包含敏感词，返回 (bool, str|None)"""
        for end, word in self.automaton.iter(text):
            return True, word   # 找到一个就返回
        return False, None

# ================== 使用示例 ==================
if __name__ == "__main__":
    detector = SensitiveWordDetector(" 敏感词.xlsx")

    text = "XXX"
    has_sensitive, word = detector.check(text)
    if has_sensitive:
        print(" 检测到敏感词:", word)
    else:
        print(" 未检测到敏感词 ")