每日算法 — 使用java实现AC自动机：Trie树与失败指针的多模式串匹配

引言

在文本处理领域，单模式串匹配（如 KMP 算法）只能在一个文本中查找一个关键词。但实际应用中，往往需要同时查找成百上千个关键词——例如敏感词过滤、病毒特征码检测、日志关键词提取等场景。AC 自动机（Aho-Corasick Automaton）由 Alfred Aho 和 Margaret Corasick 于1975年提出，它通过构建 Trie 树并添加失败指针（Failure Link），实现了O(n + m + z) 的多模式串匹配复杂度，其中 n 是文本长度、m 是所有模式串总长度、z 是匹配次数。Linux 的 fgrep 命令、Snort 入侵检测系统、ClamAV 杀毒软件都采用了 AC 自动机。

本文将用 Java 从零实现一个完整的 AC 自动机，深入讲解 Trie 树构建、失败指针计算、输出链接优化与实际应用。

核心思想

AC 自动机是 Trie 树与 KMP 失败函数思想的结合：

1. Trie 树阶段：将所有模式串插入 Trie 树，共享公共前缀
2. 失败指针阶段：为每个节点计算失败指针，指向当前字符串的最长真后缀所对应的 Trie 节点（该后缀也是某个模式串的前缀）
3. 匹配阶段：在文本上自动机状态转移，每步 O(1)，遇到匹配则输出

失败指针的直观理解

假设模式串为 {“he”, “she”, “his”, “hers”}。当在文本 “ushers” 中匹配到 “she” 后，如果下一个字符不是 ‘r’，不必回到根节点重新开始，而是跳到 “he” 节点——因为 “she” 的最长真后缀 “he” 恰好是另一个模式串的前缀。

Java 实现

AC 自动机节点

import java.util.*;

public class AhoCorasickNode {
    // 子节点映射：字符 -> 子节点
    Map<Character, AhoCorasickNode> children;
    // 失败指针
    AhoCorasickNode fail;
    // 输出集合：以当前节点结尾的所有模式串（考虑后缀匹配）
    List<String> outputs;
    // 是否为一个模式串的结尾
    boolean isEnd;
    // 对应的模式串（仅 isEnd 为 true 时有效）
    String pattern;

    public AhoCorasickNode() {
        this.children = new HashMap<>();
        this.fail = null;
        this.outputs = new ArrayList<>();
        this.isEnd = false;
        this.pattern = null;
    }
}

AC 自动机核心类

import java.util.*;

public class AhoCorasick {
    private final AhoCorasickNode root;
    private boolean built; // 是否已构建失败指针

    public AhoCorasick() {
        this.root = new AhoCorasickNode();
        this.built = false;
    }

    /**
     * 添加模式串到 Trie 树
     * 时间复杂度：O(L)，L 为模式串长度
     */
    public void addPattern(String pattern) {
        if (pattern == null || pattern.isEmpty()) {
            return;
        }

        AhoCorasickNode node = root;
        for (char c : pattern.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new AhoCorasickNode());
        }
        node.isEnd = true;
        node.pattern = pattern;
    }

    /**
     * 构建失败指针
     * 使用 BFS 按层计算，确保处理某节点时其父节点的失败指针已计算
     * 时间复杂度：O(m)，m 为所有节点数
     */
    public void build() {
        if (built) return;

        Queue<AhoCorasickNode> queue = new LinkedList<>();

        // 第一层节点的失败指针指向根节点
        for (AhoCorasickNode child : root.children.values()) {
            child.fail = root;
            queue.offer(child);
        }

        // BFS 逐层构建失败指针
        while (!queue.isEmpty()) {
            AhoCorasickNode current = queue.poll();

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

                // 计算 child 的失败指针
                AhoCorasickNode failNode = current.fail;

                // 沿着失败指针链查找具有相同字符子节点的节点
                while (failNode != null && !failNode.children.containsKey(c)) {
                    failNode = failNode.fail;
                }

                if (failNode == null) {
                    child.fail = root;
                } else {
                    child.fail = failNode.children.get(c);
                }

                // 优化：将失败节点的输出合并到当前节点，避免匹配时回溯
                if (child.fail != null && !child.fail.outputs.isEmpty()) {
                    child.outputs.addAll(child.fail.outputs);
                }

                queue.offer(child);
            }

            // 将当前节点自身的模式串加入输出列表
            if (current.isEnd && current.pattern != null) {
                current.outputs.add(current.pattern);
            }
        }

        // 根节点的输出为空
        root.outputs.clear();
        built = true;
    }

    /**
     * 在文本中搜索所有模式串匹配
     * @param text 待搜索文本
     * @return 匹配结果列表，每个结果包含模式串和结束位置
     */
    public List<MatchResult> search(String text) {
        if (!built) {
            build();
        }

        List<MatchResult> results = new ArrayList<>();
        AhoCorasickNode current = root;

        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);

            // 状态转移：如果没有对应子节点，沿失败指针跳转
            while (current != root && !current.children.containsKey(c)) {
                current = current.fail;
            }

            if (current.children.containsKey(c)) {
                current = current.children.get(c);
            } else {
                current = root;
                continue;
            }

            // 输出当前节点的所有匹配
            for (String pattern : current.outputs) {
                results.add(new MatchResult(pattern, i - pattern.length() + 1, i));
            }
        }

        return results;
    }

    /**
     * 检查文本中是否包含任意模式串
     */
    public boolean containsAny(String text) {
        return !search(text).isEmpty();
    }

    /**
     * 将文本中的模式串替换为指定字符串
     */
    public String replace(String text, String replacement) {
        List<MatchResult> matches = search(text);
        if (matches.isEmpty()) return text;

        // 按位置排序并处理重叠匹配（优先最长匹配）
        matches.sort((a, b) -> {
            if (a.start != b.start) return a.start - b.start;
            return b.pattern.length() - a.pattern.length();
        });

        StringBuilder sb = new StringBuilder();
        int lastEnd = 0;
        Set<Integer> replacedPositions = new HashSet<>();

        for (MatchResult match : matches) {
            if (match.start < lastEnd) continue; // 跳过重叠匹配

            sb.append(text, lastEnd, match.start);
            sb.append(replacement);
            lastEnd = match.end + 1;
        }
        sb.append(text.substring(lastEnd));

        return sb.toString();
    }

    public static class MatchResult {
        public final String pattern;
        public final int start;
        public final int end;

        public MatchResult(String pattern, int start, int end) {
            this.pattern = pattern;
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return String.format("Pattern '%s' at [%d, %d]", pattern, start, end);
        }
    }
}

内存优化版：使用数组代替 HashMap

对于字符集较小（如 ASCII）的场景，可用数组替代 HashMap 以提升性能：

public class CompactAhoCorasickNode {
    // 假设使用 ASCII 字符集，也可用 Trie 压缩（双数组 Trie）
    CompactAhoCorasickNode[] children = new CompactAhoCorasickNode[128];
    CompactAhoCorasickNode fail;
    List<String> outputs = new ArrayList<>();
    boolean isEnd;

    public CompactAhoCorasickNode getChild(char c) {
        return children[c];
    }

    public void setChild(char c, CompactAhoCorasickNode node) {
        children[c] = node;
    }
}

测试与验证

public class AhoCorasickDemo {
    public static void main(String[] args) {
        AhoCorasick ac = new AhoCorasick();

        // 添加敏感词/模式串
        String[] patterns = {"he", "she", "his", "hers", "sher", "her"};
        for (String p : patterns) {
            ac.addPattern(p);
        }

        // 构建自动机
        ac.build();

        // 测试文本
        String text = "ushers";
        System.out.println("=== AC 自动机多模式匹配测试 ===\n");
        System.out.println("模式串: " + String.join(", ", patterns));
        System.out.println("文本: \"" + text + "\"\n");

        List<AhoCorasick.MatchResult> results = ac.search(text);
        System.out.println("匹配结果:");
        for (AhoCorasick.MatchResult r : results) {
            System.out.println("  " + r);
        }

        // 敏感词过滤测试
        System.out.println("\n=== 敏感词过滤测试 ===");
        AhoCorasick filter = new AhoCorasick();
        String[] sensitiveWords = {"暴力", "赌博", "色情", "诈骗"};
        for (String w : sensitiveWords) {
            filter.addPattern(w);
        }
        filter.build();

        String userInput = "这个网站涉及赌博和诈骗内容";
        System.out.println("用户输入: " + userInput);
        System.out.println("包含敏感词: " + filter.containsAny(userInput));
        System.out.println("过滤后: " + filter.replace(userInput, "***"));

        // 性能对比测试
        System.out.println("\n=== 性能对比：AC 自动机 vs 逐个 KMP ===");
        int patternCount = 1000;
        int textLength = 100000;

        AhoCorasick largeAc = new AhoCorasick();
        java.util.Random rand = new java.util.Random(42);
        String chars = "abcdefghijklmnopqrstuvwxyz";

        // 生成随机模式串
        for (int i = 0; i < patternCount; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 5; j++) {
                sb.append(chars.charAt(rand.nextInt(chars.length())));
            }
            largeAc.addPattern(sb.toString());
        }
        largeAc.build();

        // 生成随机文本
        StringBuilder textSb = new StringBuilder(textLength);
        for (int i = 0; i < textLength; i++) {
            textSb.append(chars.charAt(rand.nextInt(chars.length())));
        }
        String largeText = textSb.toString();

        long start = System.currentTimeMillis();
        largeAc.search(largeText);
        long acTime = System.currentTimeMillis() - start;

        System.out.println("模式串数量: " + patternCount);
        System.out.println("文本长度: " + textLength);
        System.out.println("AC 自动机耗时: " + acTime + " ms");
        System.out.println("理论逐个 KMP 耗时: ~" + (acTime * patternCount / 10) + " ms (估算)");
    }
}

复杂度分析

与单模式算法的对比

当模式串数量 k > 5 时，AC 自动机通常是最优选择。

实际应用场景

1. 敏感词过滤：微博、论坛等平台的实时内容审核系统
2. 入侵检测：Snort/Suricata 使用 AC 自动机匹配网络流量中的恶意特征
3. 病毒检测：ClamAV 使用 AC 自动机匹配病毒特征码
4. 搜索引擎：查询词扩展、拼写纠错中的词典匹配
5. 日志分析：从海量日志中实时提取关键词指标
6. DNA 序列分析：生物信息学中的多序列匹配

总结

AC 自动机将 Trie 树的前缀共享优势与 KMP 的最长公共前后缀思想完美融合，以线性时间完成了多模式串匹配这一看似需要平方时间的任务。理解 AC 自动机不仅能掌握一种高效的文本匹配工具，更能体会”预处理换查询”和”状态机思维”在算法设计中的强大威力。