AC自动机实现

tianqy · · 627 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。
1.简介<br> &nbsp;&nbsp;&nbsp;&nbsp;在工程实践中,AC自动机是一种常见的解决字符串匹配的处理方式,广告投放中最常见的应用场景就是敏感词过滤;AC自动机的实现会涉及到BFS宽度优先搜索和trie树两个概念,关于这块内容本节不再细述,不甚了解的同学可以网上搜下资料,本部分只讲下AC自动机的实现衍变。<br> AC自动机是在trie树基础上发展起来的,解决trie树只能处理前缀匹配的问题,对于AC自动机的应用场景而言,trie树存在的问题是在字符匹配失败时,不能进行跳转、继续匹配,为此,AC自动机引入了fail指针概念,用于匹配后的跳转,而fail指针的作用就是实现了trie数中节点的关联,由于fail指针是实现AC自动机的关键,下面围绕fail指针看下:<br> &nbsp;&nbsp;&nbsp;&nbsp;1)fail指针特性<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1)fail指针节点的字符一定与跳转后的节点的字符一样;<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2)fail指针节点往前的字符串包含跳转后的节点往前的字符串;<br> &nbsp;&nbsp;&nbsp;&nbsp;2)fail指针实现<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1)对于根节点而言,它的fail指针为nil,而它的每个子节点的fail指针都指向根节点;<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2)对于其他节点而言,它的fail指针取决于它的父节点——当对某个child节点求fail指针时,首先找到它的father节点的fail指针指向的节点Node,如果Node节点下有child节点相同的子节点,则child节点的fail指针就指向这个子节点,如果不同,则继续查找Node节点的fail指针所指向的节点Node_Next,如果找不到,child节点的fail指针就指向root节点;<br> &nbsp;&nbsp;&nbsp;&nbsp;简单讲,就是通过横向指向的方式支持模糊匹配处理、解决之前不匹配导致中断的问题;另外,由上可知,设置fail指针的节点比指向节点的层级要往下低一些,所以可以通过逐层遍历的方式,为每个节点设置fail指针,而对树的逐层遍历,可以通过BFS实现。<br> 2.实现<br> &nbsp;&nbsp;&nbsp;&nbsp;关于AC自动机实现,有几点要注意下:<br> &nbsp;&nbsp;&nbsp;&nbsp;1)空间占用大<br> &nbsp;&nbsp;&nbsp;&nbsp;了解trie树的同学都知道每个节点都包含一定数量的子节点,如果子节点数量比较多,随着树的层次越大、对应的空间占用也会很大;<br> &nbsp;&nbsp;&nbsp;&nbsp;2)字符取值多样性<br> &nbsp;&nbsp;&nbsp;&nbsp;子节点的数量一般是取决于字符取值范围,如果参与匹配的字符都是ASCII字符,则取值就比较有限,但如果涉及到中文,那么子节点数量就会变得非常多;<br> &nbsp;&nbsp;&nbsp;&nbsp;为了支持中文匹配同时减少子节点数,本部分是按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")) } ```

有疑问加站长微信联系

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

627 次点击  
加入收藏 微博
2 回复  |  直到 2020-10-14 10:32:37
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传