AC-Search

基于 AC自动机（Aho-Corasick） 的高性能多模式字符串匹配库，结合了字典树（Trie）和 KMP 失败指针思想，可在文本中高效查找多个模式串。

特性

• 泛型支持：模式可以是任意实现 Pattern 接口的结构体，支持携带用户标记、分类等元数据
• 多级归一化管道：预处理器（NFKD、多字符替换、strip）+ 字符映射（视觉混淆表、大小写）两阶段流水线，可组合使用
• 支持中文和多字节字符
• 零内存分配的快速检测方法
• 支持字节位置和 Unicode 字符位置两种返回格式
• 自动处理重叠模式匹配
• 线程安全（构建完成后）

安装

go get github.com/rushteam/ac-search

快速开始

简单字符串匹配

package main

import (
    "fmt"
    acsearch "github.com/rushteam/ac-search"
)

func main() {
    // 使用便捷方法创建字符串匹配器
    ac := acsearch.NewStringMatcher()

    // 添加词库
    ac.AddPatterns([]acsearch.StringPattern{"敏感词", "违禁内容", "不良信息"})

    text := "这段文本包含敏感词和不良信息"

    // 快速检查是否包含
    if ac.Contains(text) {
        fmt.Println("包含敏感词")
    }

    // 获取所有匹配及位置
    results := ac.SearchRune(text)
    for _, r := range results {
        fmt.Printf("找到: %s, 位置: [%d, %d)\n", r.Pattern.String(), r.Start, r.End)
    }
}

自定义结构体（带用户标记）

package main

import (
    "fmt"
    acsearch "github.com/rushteam/ac-search"
)

// 自定义敏感词结构体
type SensitiveWord struct {
    Text     string
    Category string // 分类：政治、色情、广告等
    Level    int    // 级别：1-低 2-中 3-高
    UserID   int64  // 添加该词的用户ID
}

// 实现 fmt.Stringer 接口
func (s SensitiveWord) String() string {
    return s.Text
}

func main() {
    // 创建泛型AC自动机
    ac := acsearch.New[SensitiveWord]()

    // 添加带元数据的敏感词
    ac.AddPatterns([]SensitiveWord{
        {Text: "敏感词", Category: "政治", Level: 3, UserID: 1001},
        {Text: "广告", Category: "营销", Level: 1, UserID: 1002},
    })

    text := "这段文本包含敏感词和广告"

    // 获取匹配结果，包含完整的结构体信息
    results := ac.SearchRune(text)
    for _, r := range results {
        fmt.Printf("词: %s, 分类: %s, 级别: %d, 添加者: %d\n",
            r.Pattern.Text, r.Pattern.Category, r.Pattern.Level, r.Pattern.UserID)
    }
}

项目结构

ac-search/
├── go.mod          # Go模块定义
├── ac.go           # AC自动机核心实现（泛型版本）
├── normalizer.go   # 内置归一化工具函数
├── ac_test.go      # 测试和基准测试
├── README.md       # 项目文档
└── example/
    └── main.go     # 使用示例

API 说明

Pattern 接口

直接使用标准库 fmt.Stringer，任何实现了 String() string 方法的类型都可作为模式：

type Pattern = fmt.Stringer

内置类型

// StringPattern 简单字符串模式
type StringPattern string

func (s StringPattern) String() string {
    return string(s)
}

创建和初始化

// 创建泛型AC自动机
ac := acsearch.New[YourPatternType]()

// 使用便捷方法创建字符串匹配器
ac := acsearch.NewStringMatcher()

// 添加单个模式
ac.AddPattern(pattern)

// 批量添加模式
ac.AddPatterns([]YourPatternType{...})

// 手动构建（可选，Search/Contains 会自动调用）
ac.Build()

// 清空重置
ac.Clear()

// 获取所有已添加的模式
patterns := ac.GetPatterns()

归一化选项

// WithNormalizer：字符级归一化，在构建和搜索时对每个字符应用
// 返回 0 表示跳过该字符（用于 strip 场景）
acsearch.WithNormalizer[T](fn func(rune) rune)

// WithPreprocessor：字符串级预处理，在归一化之前执行
// 适合 NFKD 分解、多字符替换、去除干扰符等场景
acsearch.WithPreprocessor[T](fn func(string) string)

内置归一化工具（normalizer.go）

// NormalizerVisualMap 视觉混淆映射表 + 自动转小写
// 覆盖：变音字母(ø→o、ä→a...)、西里尔同形字(о→o、р→p...)、
//       数字符号(0→o、1→i、@→a、$→s...)、全角字母
acsearch.NormalizerVisualMap() func(rune) rune

// NormalizerCaseInsensitive 仅转小写
acsearch.NormalizerCaseInsensitive() func(rune) rune

// PreprocessorNFKD NFKD 分解后去掉组合字符：á→a、ñ→n、résumé→resume
acsearch.PreprocessorNFKD() func(string) string

// PreprocessorMultiChar 多字符序列替换：\/→u、vv→w 等
// 注意：长模式放前面，避免被短模式提前截断
acsearch.PreprocessorMultiChar(replacements [][2]string) func(string) string

// PreprocessorStrip 过滤字符，只保留满足 keep 条件的字符
// 例如去掉 * - 空格等干扰符：PreprocessorStrip(unicode.IsLetter)
acsearch.PreprocessorStrip(keep func(rune) bool) func(string) string

// ChainPreprocessors 串联多个预处理器，按顺序依次执行
acsearch.ChainPreprocessors(fns ...func(string) string) func(string) string

核心方法

方法	返回值	说明	适用场景
Contains(text)	bool	快速检查是否包含任意模式	零内存分配，敏感词过滤最优选
ContainsAny(text)	(T, bool)	返回第一个匹配的模式	需要知道具体命中哪个模式
Search(text)	[]MatchResult[T]	返回所有匹配及字节位置	需要精确字节位置
SearchRune(text)	[]RuneMatchResult[T]	返回所有匹配及 Unicode 字符位置	中文场景，字符位置更直观
SearchFirst(text)	(MatchResult[T], bool)	只返回第一个匹配详情	只需第一个匹配即可
SearchCount(text)	map[string]int	统计每个词出现次数	词频统计

返回结构

// 字节位置结果
type MatchResult[T Pattern] struct {
    Pattern T   // 匹配到的模式（包含完整信息）
    Start   int // 起始字节位置
    End     int // 结束字节位置（不包含）
}

// Unicode字符位置结果
type RuneMatchResult[T Pattern] struct {
    Pattern T   // 匹配到的模式（包含完整信息）
    Start   int // 起始字符位置
    End     int // 结束字符位置（不包含）
}

使用示例

1. 敏感词检测（推荐使用 Contains）

ac := acsearch.NewStringMatcher()
ac.AddPatterns([]acsearch.StringPattern{"敏感词", "违禁内容"})

// 最快速的检测方式，零内存分配
if ac.Contains(userInput) {
    return errors.New("包含敏感内容")
}

2. 多用户词库

type UserKeyword struct {
    Keyword string
    UserID  int64
    Tag     string
}

func (u UserKeyword) String() string {
    return u.Keyword
}

ac := acsearch.New[UserKeyword]()

// 用户1的词库
ac.AddPattern(UserKeyword{Keyword: "苹果", UserID: 1, Tag: "水果"})

// 用户2的词库（同一个词，不同含义）
ac.AddPattern(UserKeyword{Keyword: "苹果", UserID: 2, Tag: "科技"})

results := ac.SearchRune("我买了一个苹果")
for _, r := range results {
    fmt.Printf("用户 %d 的词 %q 匹配\n", r.Pattern.UserID, r.Pattern.Keyword)
}
// 输出:
// 用户 1 的词 "苹果" 匹配
// 用户 2 的词 "苹果" 匹配

3. 敏感词过滤与替换

ac := acsearch.New[SensitiveWord]()
ac.AddPatterns([]SensitiveWord{
    {Text: "敏感", Category: "政治", Level: 3},
    {Text: "广告", Category: "营销", Level: 1},
})

text := "这是一段包含敏感内容和广告的文本"
runes := []rune(text)
results := ac.SearchRune(text)

// 从后往前替换，避免位置偏移
for i := len(results) - 1; i >= 0; i-- {
    r := results[i]
    var replacement string
    if r.Pattern.Level >= 3 {
        replacement = "***"
    } else {
        replacement = "**"
    }
    runes = append(runes[:r.Start], append([]rune(replacement), runes[r.End:]...)...)
}
fmt.Println(string(runes))
// 输出: 这是一段包含***内容和**的文本

4. 归一化管道（变体匹配 / 反混淆）

归一化分两个阶段，可以单独使用也可以组合：

阶段	选项	处理粒度	典型用途
预处理器	WithPreprocessor	字符串级	NFKD 分解、多字符替换（\/→u）、strip 干扰符
归一化函数	WithNormalizer	单字符级	视觉映射表、大小写、返回 0 跳过该字符

内置工具函数（normalizer.go）

// 视觉混淆映射表：ø→o、0→o、@→a、西里尔同形字、全角字母等，并自动转小写
NormalizerVisualMap() func(rune) rune

// 仅大小写不敏感
NormalizerCaseInsensitive() func(rune) rune

// NFKD 分解后去掉组合字符：á→a、ñ→n、résumé→resume
PreprocessorNFKD() func(string) string

// 多字符序列替换：\/→u、vv→w 等（长模式放前面避免被短模式截断）
PreprocessorMultiChar(replacements [][2]string) func(string) string

// 过滤字符：只保留满足 keep 条件的字符，可去掉 * - 空格等干扰符
PreprocessorStrip(keep func(rune) bool) func(string) string

// 串联多个预处理器，按顺序依次执行
ChainPreprocessors(fns ...func(string) string) func(string) string

示例

// 1. 视觉混淆（cølør → color，0 → o，@ → a，西里尔 о → o）
ac := acsearch.NewStringMatcher(
    acsearch.WithNormalizer[acsearch.StringPattern](acsearch.NormalizerVisualMap()),
)
ac.AddPattern("color")
ac.Contains("cølør")  // true
ac.Contains("c0l0r")  // true
ac.Contains("CОLОR") // true（含西里尔 О）

// 2. NFKD + 大小写（résumé → resume）
ac2 := acsearch.NewStringMatcher(
    acsearch.WithPreprocessor[acsearch.StringPattern](acsearch.PreprocessorNFKD()),
    acsearch.WithNormalizer[acsearch.StringPattern](acsearch.NormalizerCaseInsensitive()),
)
ac2.AddPattern("resume")
ac2.Contains("résumé") // true
ac2.Contains("RÉSUMÉ") // true

// 3. 去除插入符（F*u*c*k → fuck）
ac3 := acsearch.NewStringMatcher(
    acsearch.WithPreprocessor[acsearch.StringPattern](
        acsearch.PreprocessorStrip(unicode.IsLetter),
    ),
    acsearch.WithNormalizer[acsearch.StringPattern](acsearch.NormalizerCaseInsensitive()),
)
ac3.AddPattern("fuck")
ac3.Contains("F*u*c*k") // true
ac3.Contains("F u c k") // true

// 4. 多字符替换（\/ → u）
ac4 := acsearch.NewStringMatcher(
    acsearch.WithPreprocessor[acsearch.StringPattern](
        acsearch.PreprocessorMultiChar([][2]string{{"\/", "u"}, {"vv", "w"}}),
    ),
    acsearch.WithNormalizer[acsearch.StringPattern](acsearch.NormalizerCaseInsensitive()),
)
ac4.AddPattern("fuck")
ac4.Contains(`f\/ck`) // true

// 5. 串联所有手段（生产环境推荐写法）
preprocessor := acsearch.ChainPreprocessors(
    acsearch.PreprocessorMultiChar([][2]string{{"\/", "u"}, {"vv", "w"}}),
    acsearch.PreprocessorStrip(unicode.IsLetter),
    acsearch.PreprocessorNFKD(),
)
ac5 := acsearch.NewStringMatcher(
    acsearch.WithPreprocessor[acsearch.StringPattern](preprocessor),
    acsearch.WithNormalizer[acsearch.StringPattern](acsearch.NormalizerVisualMap()),
)

5. 按分类统计

results := ac.SearchRune(text)

categoryCount := make(map[string]int)
for _, r := range results {
    categoryCount[r.Pattern.Category]++
}
// categoryCount: {"政治": 1, "营销": 2}

算法原理

AC自动机 = 字典树(Trie) + KMP失败指针

字典树（Trie）

存储所有模式串，共享公共前缀，节省内存。

        root
       /    \
      h      s
      |      |
      e      h
     / \     |
    r   (he) e
    |       (she)
    s
    |
   (hers)

失败指针（Fail Pointer）

类似 KMP 的 next 数组，当匹配失败时快速跳转到最长 proper 后缀对应的前缀位置，避免重复扫描。

复杂度

操作	时间复杂度	说明
构建	O(m)	m = 所有模式串总长度
搜索	O(n + z)	n = 文本长度，z = 匹配数量
总体	O(n + m + z)	线性时间复杂度

性能基准

测试环境：Apple M5

BenchmarkACAutomaton_Build-10        8397    141488 ns/op   218867 B/op   3449 allocs/op
BenchmarkACAutomaton_Search-10    1343772       892 ns/op      800 B/op      5 allocs/op
BenchmarkACAutomaton_Contains-10  5883663       204 ns/op        0 B/op      0 allocs/op

• Contains 方法零内存分配，适合高频调用场景
• 1000个模式串的构建时间约 0.14ms
• 搜索性能约 500万次/秒

运行测试

# 运行所有测试
go test -v

# 运行基准测试
go test -bench=. -benchmem

# 运行示例
go run example/main.go

License

MIT License