Golang 实现高性能的 Aho-Corasick 多模式匹配算法

先给个定论：如果在生产环境里搞AC自动机，直接上双数组Trie实现，别碰那种用map[rune]*Node的版本。原因很直白——10万级别的词典，map版本构建卡你2秒开外不说，内存一路飙升，GC频繁到让人抓狂。这可不是配置能解决的问题，是数据结构本身的天花板。

为什么Build()会卡住甚至panic

AC自动机对词典的“脾气”极其敏感，Build阶段动不动崩溃或者慢得离谱，90%的情况都是因为输入没做预处理清洗。

具体来说，下面这几类情况是重灾区：

• 空字符串、"\x00"这类玩意儿，还有TrimSpace之后等于空串的条目，直接往里塞就会触发panic
• 单个模式词太长，比如超过256字节，会导致节点爆炸。这在中文场景里尤其常见——谁知道哪个日志里会夹着一串“身份证号XXXXXXXX……”这样的脏数据
• 大小写不同但语义重复的词，比如"password"和"Password"同时存在，会让fail指针链变得冗余甚至断裂
• 没有排序。按长度升序加字典序排列，能显著提升前缀复用率。比如说"user"和"username"，排序之后才能共享前4个节点

所以，在调用ac.Build()之前，必须做一轮清洗。下面是一个可用的示例：

words := []string{"密码", "Password", "  ", "\x00", "username", "user"}
cleaned := make([]string, 0, len(words))
seen := map[string]struct{}{}
for _, w := range words {
    w = strings.TrimSpace(w)
    if w == "" || len(w) > 256 {
        continue
    }
    if _, ok := seen[strings.ToLower(w)]; !ok {
        seen[strings.ToLower(w)] = struct{}{}
        cleaned = append(cleaned, w)
    }
}
sort.Slice(cleaned, func(i, j int) bool {
    if len(cleaned[i]) != len(cleaned[j]) {
        return len(cleaned[i]) < len(cleaned[j])
    }
    return strings.ToLower(cleaned[i]) < strings.ToLower(cleaned[j])
})

GBK/Big5文本匹配失效的根本原因

Go的字符串天然是UTF-8的，可现实世界里，日志、数据库导出、老系统的接口，随手一翻就是GBK编码。你要是直接把[]byte或者string丢给FindAllString()，后果就是rune切分错位——匹配位置偏移、漏词、甚至返回负索引，谁都救不了。

错误的做法是：每次匹配前用golang.org/x/text/encoding转码一下。这么做在高并发场景下会变成性能瓶颈，还引入一堆额外的内存分配，得不偿失。

正确的路径只有两条：

• 在数据源头就解码成UTF-8的[]byte。比如读文件时，直接用golang.org/x/text/encoding/simplifiedchinese.GB18030.NewDecoder().Bytes()处理
• 改用基于byte的双数组Trie实现，比如github.com/grepner/go-ahocorasick的优化分支，这样能直接绕过rune这个抽象层

记好了：FindAllStringIndex()不是万能入口，它只适配UTF-8。混编码的文本，必须先归一化。

并发匹配时State复用的陷阱

自动机结构本身是只读的，这一点没问题。但匹配过程中用的游标状态——当前节点指针、已匹配长度、路径深度——这些必须做到每个查询独立。如果你复用一个没清零的*Matcher实例，结果污染几乎是必然的。

一个典型的错误写法：

var matcher *ahocorasick.Matcher
func handle(text string) {
    // 错误：复用同一实例，无重置逻辑
    matches := matcher.FindAllString(text)
}

安全的做法有两种，选一个合适的就行：

• 每次调用都新建一个干净实例，轻量，推荐：ac := ahocorasick.New(...); ac.Build(dict); ac.FindAllString(text)
• 如果追求极致性能，可以用sync.Pool管理游标对象。但别忘了，在Put()之前必须显式把全部字段清零——current = root、matchedLen = 0等——不能指望GC帮你擦屁股

另外提一句：github.com/BobuSumisu/ahocorasick这个库默认不支持热更新。词典变了就得重建整个自动机。这一点在规则频繁下发的敏感词系统里，经常被人忽略，结果吃了大亏。

真正考验功力的，不是怎么把AC自动机写出来，而是让10万条词典在200毫秒内建完、每秒扛住5000次并发查询、同时还不因为一条GBK日志就把整条流水线搞崩。双数组结构、源头编码归一、词典预清洗，这三样东西，一个都不能少。