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"))
}