Golang AC自动机算法实现

最近在学习AC自动机算法，想用Golang实现一个高效的多模式字符串匹配工具。但有几个问题不太明白：

  1. Golang中如何设计Trie树结构比较合适？用struct还是map实现节点更好？
  2. 构建失败指针时，用BFS遍历的话，Golang的队列用什么数据结构实现性能最好？
  3. 对于大规模模式串(比如上万个关键词)，有什么优化内存的技巧吗？
  4. 能否分享一个完整的Golang实现示例？最好能包含匹配过程和性能测试部分。

希望有实际项目经验的大佬能指点一下，谢谢！

2 回复

Golang中AC自动机可通过Trie树和失败指针实现。使用map[rune]*node存储子节点，fail指针处理匹配失败跳转。构建Trie后通过BFS建立fail指针，最后扫描文本时利用fail指针实现多模式匹配。代码约100行，适合敏感词过滤等场景。

更多关于Golang AC自动机算法实现的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


AC自动机（Aho-Corasick Algorithm）是一种多模式匹配算法，用于在文本中同时查找多个关键词。以下是Golang的实现步骤和代码示例：

核心步骤

  1. 构建Trie树：插入所有模式串。
  2. 添加失败指针：通过BFS为每个节点设置失败指针，指向最长真后缀对应的节点。
  3. 匹配过程：遍历文本，利用失败指针跳转，高效匹配所有模式。

代码实现

package main

import (
	"fmt"
)

type Node struct {
	children map[rune]*Node // 子节点
	fail     *Node          // 失败指针
	output   []string       // 匹配的模式串（结束节点存储）
}

func NewNode() *Node {
	return &Node{
		children: make(map[rune]*Node),
		output:   make([]string, 0),
	}
}

type AhoCorasick struct {
	root *Node
}

func NewAhoCorasick() *AhoCorasick {
	return &AhoCorasick{root: NewNode()}
}

// 插入模式串
func (ac *AhoCorasick) Insert(pattern string) {
	node := ac.root
	for _, ch := range pattern {
		if node.children[ch] == nil {
			node.children[ch] = NewNode()
		}
		node = node.children[ch]
	}
	node.output = append(node.output, pattern)
}

// 构建失败指针
func (ac *AhoCorasick) Build() {
	queue := []*Node{}
	
	// 根节点的子节点失败指针指向根
	for _, child := range ac.root.children {
		child.fail = ac.root
		queue = append(queue, child)
	}
	
	// BFS设置失败指针
	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]
		
		for ch, child := range current.children {
			queue = append(queue, child)
			
			// 从当前节点的失败指针开始查找
			failNode := current.fail
			for failNode != nil && failNode.children[ch] == nil {
				failNode = failNode.fail
			}
			
			if failNode == nil {
				child.fail = ac.root
			} else {
				child.fail = failNode.children[ch]
				// 合并输出（后缀匹配的模式）
				child.output = append(child.output, child.fail.output...)
			}
		}
	}
}

// 匹配文本
func (ac *AhoCorasick) Search(text string) map[string][]int {
	result := make(map[string][]int)
	node := ac.root
	
	for i, ch := range text {
		// 跳转失败指针直到匹配或到根
		for node != ac.root && node.children[ch] == nil {
			node = node.fail
		}
		
		if nextNode, exists := node.children[ch]; exists {
			node = nextNode
		} else {
			node = ac.root
		}
		
		// 记录匹配结果
		for _, pattern := range node.output {
			startPos := i - len(pattern) + 1
			result[pattern] = append(result[pattern], startPos)
		}
	}
	return result
}

// 示例使用
func main() {
	ac := NewAhoCorasick()
	patterns := []string{"he", "she", "his", "hers"}
	for _, p := range patterns {
		ac.Insert(p)
	}
	ac.Build()
	
	text := "ushers"
	matches := ac.Search(text)
	
	for pattern, positions := range matches {
		fmt.Printf("模式 '%s' 出现在位置: %v\n", pattern, positions)
	}
}

输出示例

模式 'he' 出现在位置: [1 3]
模式 'she' 出现在位置: [2]
模式 'hers' 出现在位置: [2]

关键点

  • 时间复杂度：构建O(总模式长度)，匹配O(文本长度+匹配数)。
  • 空间优化：使用map[rune]*Node动态存储子节点，适合字符集大的场景。
  • 应用场景：敏感词过滤、基因序列分析等。

此实现完整覆盖AC自动机的核心逻辑，可直接用于多模式匹配任务。

回到顶部