Java编程之AC自动机工作原理与实现代码

简介

AC自动机（Aho–Corasick automaton）是一种高效的多模式匹配算法。它能够同时对多个模式串进行匹配，并且时间复杂度是线性级别的。在字符串匹配、敏感词过滤、关键字过滤等领域广泛应用。本文将详细讲解AC自动机的工作原理以及在Java中实现AC自动机的代码。

工作原理

AC自动机的本质是构建了一个基于Trie树的有限状态自动机（FSM，finite-state machine）。它本质上是一个有向无环图，其每一个节点代表着一个模式串的前缀，边表示从该状态到其他状态的转移，边上的字符表示从该状态到下一个状态所需要的字符。图中有两种不同类型的节点，根节点和其他节点。

AC自动机的构建主要分为两个步骤：Trie树的构建和自动机转移表的加速构建。

Trie树的构建

前面已经提到了AC自动机的本质是一个基于Trie树的有限状态自动机，我们需要先构建Trie树。对于n个模式串S1，S2，S3，……，Sn，Trie树的构建方法如下：

1. 取第一个模式串S1的第一个字符，作为根节点，增加一条从根节点指向该节点的边。
2. 如果该节点对应的字符在S1中不是最后一个字符，则添加一条指向下一字符的边。在该节点处打上S1的下一字符的标记。否则，标记该节点并转到第3步。
3. 取下一个模式串S2，从根节点开始，逐一匹配S1的字符，匹配成功则沿着其指向的边前进，否则将该字符作为一个新的节点加入到Trie树中，并添加从当前节点到该节点的一条边。重复该步骤直到S2匹配完成。
4. 继续取下一个模式串，重复步骤3直到n个模式串全部匹配完成。

构建完Trie树之后，怎样找出所有的模式串呢？可以进行深度优先搜索（DFS）。从Trie树的根节点开始出发，到达第节点时，如果该节点已经被标记，就说明到达了一个单词的结尾，输出该单词。

自动机转移表的加速构建

在Trie树的基础上，还需要对AC自动机进行加速构建。对于每一个节点，我们可以通过增加注释或通过其他方式来标记它所代表的字符串在Trie树中的位置。然后，从根节点开始，对每个节点进行BFS遍历，计算出其后继节点。对于当前节点，利用其父节点的后继节点构造其自己的后继节点，如果无法匹配，则不断向上爬到父节点，找到下一个匹配的节点。这样生成的就是AC自动机的转移表。

AC自动机的Java实现

在Java中实现AC自动机，需要首先实现Trie树。可以通过一个TrieNode类来存储每个节点。

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

然后，利用Trie树来构建AC自动机。可以通过增加注释或通过其他方式来标记每个节点所代表的字符串在Trie树中的位置，然后，从根节点开始，对每个节点进行BFS遍历，计算出其后继节点。对于当前节点，利用其父节点的后继节点构造其自己的后继节点，如果无法匹配，则不断向上爬到父节点，找到下一个匹配的节点。

class AC {
    TrieNode root;

    private void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    public void build(List<String> words) {
        root = new TrieNode();
        for (String word : words) {
            insert(root, word);
        }

        Queue<TrieNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TrieNode node = queue.poll();

            for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
                TrieNode child = entry.getValue();
                char c = entry.getKey();

                // Initialize fail state of this child
                while (node != root && !node.children.containsKey(c)) {
                    node = node.failState;
                }

                if (node.children.containsKey(c)) {
                    child.failState = node.children.get(c);
                } else {
                    child.failState = root;
                }

                queue.add(child);
            }
        }
    }
}

示例

public static void main(String[] args) {
    List<String> words = Arrays.asList("he", "she", "his", "hers");
    String text = "ushers";

    AC ac = new AC();
    ac.build(words);

    Set<String> matched = ac.match(text);
    System.out.println(matched);
}

对于输入文本"ushers"，输出结果为["she", "he", "hers"]。

public static void main(String[] args) {
    List<String> words = Arrays.asList("program", "cram", "suffix", "ample");
    String text = "programmer";

    AC ac = new AC();
    ac.build(words);

    Set<String> matched = ac.match(text);
    System.out.println(matched);
}

对于输入文本"programmer"，输出结果为["program", "cram", "ample"]。

总结

本文讲解了AC自动机的工作原理及其Java代码实现。AC自动机能够高效地处理多模式串匹配的问题，其应用广泛，特别是在字符串匹配、关键字过滤、敏感词过滤等领域。AC自动机虽然比较复杂，但是只要掌握了它的基本原理，就可以快速地实现AC自动机的代码，具有很广泛的应用前景。