AhoCorasick Algorithm

AhoCorasick AC自动机

 2019/05/31 

简介

AhoCorasick 算法（简称 AC 自动机），解决多模式串的字符匹配问题，即给定若干个单词串，求在文本串中的出现位置。KMP 算法解决单模式串的字符匹配，所以 AC 自动机可认为是 KMP 算法的扩展。

预备知识

字典树（Trie）：树上任意节点到根的路径所构成的子串，记为，都是某个插入串的前缀。
KMP 算法：利用最长前后缀完成线性匹配。

核心思想

AhoCorasick 本质上与 KMP 算法是一样的，都是通过相同前后缀减少重复计算问题，只是数据结构不同。

对应于 KMP，AC 自动机需要构建最长公共前后缀（LCPS，Longese Common proper Prefix and Suffix），即对于树上任意节点，找出最大树深的节点，满足是的真后缀。因为字典树上的任意节点所表示的都是前缀，故起名最长公共前后缀。

通常将节点记为，表示串失配时的跳转节点，出于可读性的考虑，本文记为。

的构建过程：记节点的父节点为，与其连边的字符为。若存在的出边，则。否则继续找，直至找到或到达根节点（说明未找到）。

图 1. lcps(u) 的构建

检索过程

假设已知，且字典树节点与文本串匹配，即。继续匹配有两种情形：

，则匹配长度 +1。
，与 KMP 类似，在字典树中找出最大深度（即最长前缀）的节点，满足是的真后缀，同时。

令，判断是否能匹配，否则继续判断。

参考代码

const int N = 5e5 + 7; // sum(|Wi|)
const int E = 26; // character set size
struct AhoCorasick {
    int root = 0;
    int n, lcps[N], trans[N][E];
    int end[N]; // end[u] > 0 : S(u) = Wi
    int new_node() {
        memset(trans[n], 0, E * sizeof(int));    
        lcps[n] = root, end[n] = 0;
        return n++;
    }
    void init() {
        n = 0;
        root = new_node();
    }
    void insert(const char *str, int len) {
        int u = root; 
        for (int i = 0; i < len; ++i) {
            int c = str[i] - 'a';
            if (!trans[u][c])
                trans[u][c] = new_node();
            u = trans[u][c];
        }
        ++end[u];
    }
    void LCPS() {
        queue<int> Q({root});
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (int c = 0; c < E; ++c) {
                if (trans[u][c]) {
                    int v = lcps[u];    
                    while (v != root && !trans[v][c])
                        v = lcps[v];
                    lcps[trans[u][c]] = u == root ? 
                        root : trans[v][c]; 
                    Q.push(trans[u][c]);
                } else
                    trans[u][c] = trans[lcps[u]][c];
            }
        }
    }
};

原文作者：Mcginn

原文链接：http://mcginn7.github.io/2019/05/31/AhoCorasick-Algorithm/

发表日期：May 31st 2019, 10:23:33 am

更新日期：May 4th 2024, 6:28:25 pm

Next Post

B-Tree
Previous Post

Knuth-Morris-Pratt Algorithm

CATALOG

1. 简介
2. 预备知识
3. 核心思想
4. 检索过程
5. 参考代码