AC自动机实现

1.简介

在工程实践中，AC自动机是一种常见的解决字符串匹配的处理方式，最常见的应用场景就是广告投放中的敏感词过滤；AC自动机的实现会涉及到BFS宽度优先搜索和trie树两个概念，关于这块内容本节不再细述，不甚了解的同学可以网上搜下资料，本部分只讲下AC自动机的实现衍变。

AC自动机是在trie树基础上发展起来的，解决trie树只能处理前缀匹配的问题，对于AC自动机的应用场景而言，trie树存在的问题是在字符匹配失败时，不能进行跳转、继续匹配，为此，AC自动机引入了fail指针概念，用于匹配后的跳转，而fail指针的作用就是实现了trie数中节点的关联，由于fail指针是实现AC自动机的关键，下面围绕fail指针看下：

1）fail指针特性：

1）fail指针节点的字符一定与跳转后的节点的字符一样；

2）fail指针节点往前的字符串包含跳转后的节点往前的字符串；

2）fail指针实现

1）对于根节点而言，它的fail指针为nil，而它的每个子节点的fail指针都指向根节点；														

2）对于其他节点而言，它的fail指针取决于它的父节点——当对某个child节点求fail指针时，首先找到它的father节点的fail指针指向的节点Node，如果Node节点下有child节点相同的子节点，则child节点的fail指针就指向这个子节点，如果不同，则继续查找Node节点的fail指针所指向的节点Node_Next，如果找不到，child节点的fail指针就指向root节点；

  简单讲，就是通过横向指向的方式支持模糊匹配处理、解决之前不匹配导致中断的问题；另外，由上可知，设置fail指针的节点比指向节点的层级要往下低一些，所以可以通过逐层遍历的方式，为每个节点设置fail指针，而对树的逐层遍历，可以通过BFS实现。

2.实现

关于AC自动机实现，有几点要注意下：

  1）空间占用大
  了解trie树的同学都知道每个节点都包含一定数量的子节点，如果子节点数量比较多，随着树的层次越大、对应的空间占用也会很大；

  2）字符取值多样性
  子节点的数量一般是取决于字符取值范围，如果参与匹配的字符都是ASCII字符，则取值就比较有限，但如果涉及到中文，那么子节点数量就会变得非常多；

  为了支持中文匹配同时减少子节点数，本部分是按4bit存储子节点的，即每个节点的子节点数都是16，由此带来的交叉匹配问题，后面是通过计数判断的方式确保是按照字符匹配的，下面看下实现样例：

const childNodeCount = 16

// AC自动机节点结构定义
type AcAutoNode struct {
	endCount int			// 结束模式串个数
	prefixCount int			// 前缀模式串个数
	failNode *AcAutoNode	// fail指针节点
	childNode [childNodeCount]*AcAutoNode	// 子节点
}

// AC自动机初始化
var GAcAuto *AcAutoNode
func init(){
	GAcAuto = new(AcAutoNode)
}

func BuildTree(s []string) {
	// 遍历模式串列表
	for uli := 0; uli < len(s); uli++ {
		node := GAcAuto
		// 遍历模式串字符
		for _, runeCh := range s[uli] {
			// 分高低位判断
			runeStr := string(runeCh)
			for ulj := 0; ulj < len(runeStr); ulj++ {
				indexHigh := runeStr[ulj] / childNodeCount
				if node.childNode[indexHigh] == nil {
					node.childNode[indexHigh] = &AcAutoNode{}
				}
				node = node.childNode[indexHigh]

				indexLow := runeStr[ulj] % childNodeCount
				if node.childNode[indexLow] == nil {
					node.childNode[indexLow] = &AcAutoNode{}
				}
				node = node.childNode[indexLow]
			}
			node.prefixCount++
		}

		node.endCount++
	}
}

func SetNodeFailPoint() {
	GAcAuto.failNode = nil

	nodeList := list.New()
	nodeList.PushBack(GAcAuto)

	// 逐层遍历trie树节点，为节点设置fail指针
	for {
		length := nodeList.Len()
		if length <= 0 {
			break
		}

		for uli := 0; uli < length; uli++ {
			ele := nodeList.Front()
			node, ok := ele.Value.(*AcAutoNode)
			if ok {
				if node == GAcAuto {
					// 根节点的子节点的fail指针都指向根节点
					for ulj := 0; ulj < childNodeCount; ulj++ {
						if node.childNode[ulj] != nil {
							node.childNode[ulj].failNode = GAcAuto
						}
					}
				} else {
					// 其他节点的子节点的fail指针就看它父节点fail指针指向的节点的子节点情况
					for ulj := 0; ulj < childNodeCount; ulj++ {
						// 遍历所有非空的子节点，为其设置fail指针
						if node.childNode[ulj] != nil {
							// fail指针设置原则是：
							// 1）查看father->failNode下有没有和自己一样的子节点，有则fail指针取该子节点
							// 2）否则，沿father->failNode->failNode继续查询下，如果一直没有，fail指针就取根节点
							nextNode := node.failNode
							for {
								if nextNode == nil {
									node.childNode[ulj].failNode = GAcAuto
									break
								} else {
									if nextNode.childNode[ulj] != nil {
										node.childNode[ulj].failNode = nextNode.childNode[ulj]
										break
									} else {
										nextNode = nextNode.failNode
									}
								}
							}
						}
					}
				}
			}

			nodeList.Remove(ele)
		}
	}
}

func AcAutoMatch(input string) bool {
	node := GAcAuto
	for _, runeCh := range input {
		count := 0
		runeStr := string(runeCh)
		for uli := 0; uli < len(runeStr); uli ++ {
			for ulj := 0; ulj < 2; ulj++ {
				index := runeStr[uli] / childNodeCount
				if ulj != 0 {
					index = runeStr[uli] % childNodeCount
				}

			Match:
				if node != nil && node.childNode[index] != nil {
					// 找到即退出，没有结束继续查找
					count++
					if node.childNode[index].endCount > 0 && count == 2 * len(runeStr) {
						return true
					}  else {
						node = node.childNode[index]
					}
				} else {
					if node == nil {
						// 当前字符一直查不到，则换下个字符，故重置node，取值根节点
						node = GAcAuto
					} else {
						// 当前节点没有目标字符，则去下个节点看下，即查看fail指针
						node = node.failNode
						goto Match
					}
				}
			}
		}
	}

	return false
}

func main() {
	// 建树
	BuildTree([]string{"ba", "real", "中国"})

	// 设置fail指针
	SetNodeFailPoint()

	// 查找
	fmt.Println(AcAutoMatch("ea"))
	fmt.Println(AcAutoMatch("real"))
	fmt.Println(AcAutoMatch("eal中国"))
	fmt.Println(AcAutoMatch("reaL"))
}