1.简介<br>
在工程实践中，AC自动机是一种常见的解决字符串匹配的处理方式，广告投放中最常见的应用场景就是敏感词过滤；AC自动机的实现会涉及到BFS宽度优先搜索和trie树两个概念，关于这块内容本节不再细述，不甚了解的同学可以网上搜下资料，本部分只讲下AC自动机的实现衍变。<br>
AC自动机是在trie树基础上发展起来的，解决trie树只能处理前缀匹配的问题，对于AC自动机的应用场景而言，trie树存在的问题是在字符匹配失败时，不能进行跳转、继续匹配，为此，AC自动机引入了fail指针概念，用于匹配后的跳转，而fail指针的作用就是实现了trie数中节点的关联，由于fail指针是实现AC自动机的关键，下面围绕fail指针看下：<br>
1）fail指针特性<br>
1）fail指针节点的字符一定与跳转后的节点的字符一样；<br>
2）fail指针节点往前的字符串包含跳转后的节点往前的字符串；<br>
2）fail指针实现<br>
1）对于根节点而言，它的fail指针为nil，而它的每个子节点的fail指针都指向根节点；<br>
2）对于其他节点而言，它的fail指针取决于它的父节点——当对某个child节点求fail指针时，首先找到它的father节点的fail指针指向的节点Node，如果Node节点下有child节点相同的子节点，则child节点的fail指针就指向这个子节点，如果不同，则继续查找Node节点的fail指针所指向的节点Node_Next，如果找不到，child节点的fail指针就指向root节点；<br>
简单讲，就是通过横向指向的方式支持模糊匹配处理、解决之前不匹配导致中断的问题；另外，由上可知，设置fail指针的节点比指向节点的层级要往下低一些，所以可以通过逐层遍历的方式，为每个节点设置fail指针，而对树的逐层遍历，可以通过BFS实现。<br>
2.实现<br>
关于AC自动机实现，有几点要注意下：<br>
1）空间占用大<br>
了解trie树的同学都知道每个节点都包含一定数量的子节点，如果子节点数量比较多，随着树的层次越大、对应的空间占用也会很大；<br>
2）字符取值多样性<br>
子节点的数量一般是取决于字符取值范围，如果参与匹配的字符都是ASCII字符，则取值就比较有限，但如果涉及到中文，那么子节点数量就会变得非常多；<br>
为了支持中文匹配同时减少子节点数，本部分是按4bit存储子节点的，即每个节点的子节点数都是16，由此带来的交叉匹配问题，后面是通过计数判断的方式确保是按照字符匹配的，下面看下实现样例：<br>
```
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"))
}
```
tianqy
越努力，越幸运！
在实际应用中，发现AC自动机实现有问题，在设置failNode时，是需要BFS遍历每层节点，为其子节点设置failNode的，但是，在实现中把这块忘了，只设置了前两层节点的failNode；对于failNode设置这块进行了更新，除了增加节点记录，还优化了记录方式，之前是使用list，现在换成slice，因为要一边遍历节点，一边要记录子节点，还要删除已遍历过的节点，使用slice主要是想整体删除；另外，在匹配方面也做了修改，加快查找速度，核心改动可以查看"// DONE"注释部分，为了方便查看，直接贴代码了：
```go
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 := make([]*AcAutoNode, 0, 10000)
nodeList = append(nodeList, GAcAuto)
// 逐层遍历trie树节点，为节点设置fail指针
for {
nodeListSize := len(nodeList)
if nodeListSize <= 0 {
break
}
for uli := 0; uli < nodeListSize; uli++ {
node := nodeList[uli]
if node == GAcAuto {
// 根节点的子节点的fail指针都指向根节点
for ulj := 0; ulj < childNodeCount; ulj++ {
if node.childNode[ulj] != nil {
node.childNode[ulj].failNode = GAcAuto
nodeList = append(nodeList, node.childNode[ulj]) // DONE
}
}
} else {
// 遍历父节点，依据父节点的failNode，为其每个子节点设置failNode
for ulj := 0; ulj < childNodeCount; ulj++ {
if node.childNode[ulj] != nil {
nodeList = append(nodeList, node.childNode[ulj]) // DONE
// 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 = nodeList[nodeListSize:]
}
}
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
goto runeChOver // DONE，快速退出当前字符、换下个字符
} else {
// 当前节点没有目标字符，则去下个节点看下，即查看fail指针
node = node.failNode
goto Match
}
}
}
}
runeChOver:
}
return false
}
var minGan = make([]string, 0, 10000)
func main() {
// 建树
BuildTree([]string{"ba", "real", "中国"})
// 设置fail指针
SetNodeFailPoint()
// 查找
fmt.Println(AcAutoMatch("ea"))
fmt.Println(AcAutoMatch("real"))
fmt.Println(AcAutoMatch("eal中国"))
fmt.Println(AcAutoMatch("reaL"))
}
```
#2
更多评论
今日阅读排行
一周阅读排行