模式匹配技术总结（AC自动机）

转载自：经典算法—Aho-Corasick automaton

Aho–Corasick automaton，简称AC自动机，著名的多模匹配算法，由Alfred V. Aho和Margaret J.Corasick于1975年在贝尔实验室发明，主要用于多模式串匹配问题，即给几个关键词（模式串），再给一篇文章，判断关键词是否在文章中出现，或出现的次数。

Aho-Corasick算法，通过将模式串预处理为确定有限状态自动机，扫描文本一遍就能结束。其复杂度为O(n)，即与模式串的数量和长度无关。

单模匹配

在介绍AC自动机这种多模匹配算法前，先回顾下单模匹配问题，即给定一个文本串和一个模式串，求解模式串在文本串中的匹配情况。

1.1 朴素匹配

最直接的想法是暴力(Brute Force)匹配，即将文本串的第一个字符与模式串的第一个字符进行匹配，若相等则继续比较文本串的第二个字符与模式串的第二个字符。若不等，则比较目标串的第二个字符与模式串的第一个字符，依次比较下去，直到得到最后的匹配结果。

相关代码如下：

# 每次匹配失败时
# 文本串T的指针回退到开始匹配位置的下一个位置
# 模式串P的指针回退到初始位置，然后重新开始匹配
def bfMatch(T,P):
    tLen,pLen = len(T),len(P)
    indexs = []
    for i in range(tLen - pLen + 1):
        for j in range(pLen):
            if T[i+j] == P[j]:
                if j == pLen - 1:
                    indexs.append(i)
                continue
            break
    return indexs

T='ushershe' 
P='he' 
print(bfMatch(T,P))

ps: 上述匹配过程存在重复匹配，KMP算法优化了上述匹配过程。在匹配失败时，文本串的指针不需要回退。

1.2 KMP算法

与朴素匹配不同，KMP算法在匹配到某个字符失败时，文本串的匹配指针不会回退，模式串则根据部分匹配表(也叫next数组) 向右滑动一定距离后继续与上次在文本串中不匹配的位置进行匹配，若仍不匹配，则继续根据部分匹配表向右滑动模式串，重复上述不匹配–滑动的过程，当匹配指针指到模式串的初始位置依然不匹配，则模式串向右滑动一位，文本串的匹配指针向前移动一位；若匹配，则继续匹配其他位置的字符。当匹配指针连续匹配的字符数与模式串的长度相等，则匹配完成。形象图解可参考字符串匹配的KMP算法。

相应代码为：

# 部分匹配表是针对模式串构建的
def kmpMatch(T,P):
    tLen,pLen = len(T),len(P)
    Next = partialMatchTable(P)
    q = 0 # 模式串P的下标
    indexs = []
    for i in range(tLen):
        while q > 0 and P[q] != T[i]:
            q = Next[q-1]
        if P[q] == T[i]:
            q += 1
        if q == pLen:
            indexs.append(i-pLen+1)
            q=0
    return indexs

部分匹配表中的数值是指某个子串的前缀和后缀的最长共有元素的长度。 其有两种构建方式。一种是手动法，详见字符串匹配的KMP算法。相关代码如下：

# 手动法求部分匹配表
def partialMatchTable(p): # 也叫next数组
    prefix,suffix = set(),set()
    pLen = len(p)
    Next = [0]
    for i in range(1,pLen):
        prefix.add(p[:i]) 
        suffix = {p[j:i+1] for j in range(1,i+1)}
        common_len = len((prefix & suffix or {''}).pop())
#         print(p[:i+1],prefix,suffix,common_len)
        Next.append(common_len) 
    return Next

p='ababaca'
partialMatchTable(p)

另一种是程序法，模式串针对自己的前后缀的匹配。详见KMP算法：线性时间O(n)字符串匹配算法中的部分匹配表部分。相关代码如下：

# 由模式串生成的部分匹配表，其存储的是前缀尾部 的位置。有前缀尾部 = next(后缀尾部)，
# 当后缀之后q不匹配时，通过查询部分匹配表，确定前缀尾部的位置k,然后将前缀滑动过来与后缀对齐，继续后续匹配工作
# 程序法计算部分匹配表 
def partialMatchTable(p):
    pLen = len(p)
    Next = [0]
    k = 0 # 模式串nP的下标
    for q in range(1,pLen): # 文本串nT的下标
        while k > 0 and p[k] != p[q]:
            k = Next[k-1]
        if p[k] == p[q]:
            k += 1
        Next.append(k)
    return Next

p='ababaca'
partialMatchTable(p)

多模匹配

给定多个模式串和一个文本串，求解多模串在文本串中存在的情况(包括是否存在、存在几次、存在于哪些位置等)。

2.1 Trie

Trie又叫前缀树或字典树，是一种多叉树结构。Trie这个术语来源于retrieval(检索)，其是一种用于快速检索的数据结构。其核心思想是利用字符串的公共前缀最大限度地减少不必要的字符串比较，提高查询(检索)效率，缺点是内存消耗大。

Trie树的基本性质：

• 根节点不包含字符，除根节点外的每一个子节点都包含一个字符
• 从根节点到某一个节点，路径上经过的字符连起来为该节点对应的字符串
• 每个节点的所有子节点包含的字符互不相同

应用场景

• 前缀匹配(自动补全)：返回所有前缀相同的字符串
• 词频统计：将每个节点是否构成单词的标志位改成构成单词的数量
• 字典序排序：将所有待排序集合逐个加入到Trie中，然后按照先序遍历输出所有值
• 分词
• 检索

代码示例

class Trie(object):
    """自定义Trie树对象，用来保存知识库
    """

    def __init__(self, value_key=-1):
        self.data = {}
        self.value_key = str(value_key)

    def __setitem__(self, key, value):
        """传入一对(key, value)到前缀树中
        """
        data = self.data
        for k in key:
            k = str(k)
            if k not in data:
                data[k] = {}
            data = data[k]
        data[self.value_key] = value

    def __getitem__(self, key):
        """获取key对应的value
        """
        data = self.data
        for k in key:
            k = str(k)
            data = data[k]
        return data[self.value_key]

    def next_ones(self, prefix):
        """获取prefix后一位的容许集
        """
        data = self.data
        for k in prefix:
            k = str(k)
            data = data[k]
        return [k for k in data if k != self.value_key]

    def keys(self, prefix=None, data=None):
        """获取以prefix开头的所有key
        """
        data = data or self.data
        prefix = prefix or []
        for k in prefix:
            k = str(k)
            if k not in data:
                return []
            data = data[k]
        results = []
        for k in data:
            if k == self.value_key:
                results.append([])
            else:
                results.extend([[k] + j for j in self.keys(None, data[k])])
        return [prefix + i for i in results]

# # 测试前缀树
# KG = Trie()
# # key = [872, 1962, 102, 872, 738, 1962]
# KG[[872, 1962]] = "首都"
# KG[[872, 1962, 78]] = "capital"
# KG[[872, 1962, 44]] = "capital2"
# KG[[23, 82, 62]] = "冲冲冲"
# # KG.save('data/KG.json')
# print(KG[[872, 1962]])  # get 首都
# print(KG.next_ones([872, 1962]))    # ['78', '44']
# print(KG.keys([872]))   # [[872, '1962'], [872, '1962', '78'], [872, '1962', '44']]
# KG = Trie()
# KG.load("data/KG.json")
# print(KG.keys([872])) 
# exit()

2.2 AC自动机

简单地讲，AC自动机就是字典树+kmp算法+失配指针。在Trie树上通过KMP来实现多模串的匹配。其中Trie树负责状态转移，KMP负责减少重复匹配。

AC自动机的实现
在多模式环境中，AC自动是使用前缀树来存放所有模式串的前缀，然后通过失配指针来处理失配的情况。分为三个步骤：构建前缀树（生成goto表），添加失配指针（生成fail表），模式匹配（构造output表）。以经典的ushers为例，模式串是“he、she、his、hers”，文本为“ushers”。构建的自动机如下图所示：

其中实线部分是一颗Trie树，虚线部分为各节点的fail路径。

匹配过程：

1. 按字符转移成功，但不是模式串的结尾。即成功转移到另一个状态，对应success表/goto表；
2. 按字符转移成功，是模式串的结尾。即命中一个模式串，对应emits/output；
3. 按字符转移失败，此时跳转到一个特定的节点，对应failure。从根节点到这个特定的节点的路径恰好是失败前的文本的一部分，类似KMP算法中利用部分匹配表来加速模式串的滑动从而减少重复匹配

上述匹配过程只需扫描一遍文本串，其时间复杂度为O(n)，与模式串的数量和长度无关。

以上图为例进行演示。自动机从根节点0出发，

1. 首先尝试按success表转移（图中实线）。按照文本的指示转移，也就是接收一个u。此时success表中并没有相应路线，转移失败。
2. 失败了则按照failure表回去（图中虚线）。按照文本指示，这次接收一个s，转移到状态3。
3. 成功了继续按success表转移，直到失败跳转步骤2，或者遇到output表中标明的“可输出状态”（图中红色状态）。此时输出匹配到的模式串，然后将此状态视作普通的状态继续转移。

算法高效之处在于，当自动机接受了“ushe”之后，再接受一个r会导致无法按照success表转移，此时自动机会聪明地按照failure表转移到2号状态，并经过几次转移后输出“hers”。来到2号状态的路不止一条，从根节点一路往下，“h→e”也可以到达。而这个“he”恰好是“ushe”的结尾，状态机就仿佛是压根就没失败过（没有接受r），也没有接受过中间的字符“us”，直接就从初始状态按照“he”的路径走过来一样（到达同一节点，状态完全相同）。

AC自动机的构建虽然与Trie树的构建类似，但其fail路径(本质是一种回溯，避免重复匹配)是AC自动机中特有的。goto表、output 表、failure 表的具体构建逻辑可参考《Aho-Corasick算法的Java实现与分析-hankcs》

基于AC自动机的开源工具

包括：pyahocorasick、Acora、esmre等

• pyahocorasick是个python模块，由两种数据结构实现：trie和Aho-Corasick自动机，根据一组关键词进行匹配，返回关键词出现的位置，底层用C实现，python包装。使用经验表明，pyahocorasick存在两个问题：
  • 一个是关键词匹配不完整，如果目标关键词里面有宝马和马，那么用python的ahocorasick库只会得到宝马，而不会得到马，问题是处在马这个字节是在宝马的链条里面的。
  • 另一个是内存泄漏问题，这个问题在esmre中得到了解决。
• acora是python的“fgrep”，是一个基于Aho-Corasick以及NFA-to-DFA自动机的方式快速的多关键字文本搜索引擎。
• esmre同样使用的AhoCorasick自动机的方式，做了一些细微的修改，也是用C实现，python包装。与pyhrocorasick相比，esmre库不存在内存异常泄露等问题。
• Flashtext是一个高效的字符搜索和替换算法，基于Trie字典数据结构和AhoCorasick 的算法时间复杂度不依赖于搜索或替换的字符的数量。与AhoCorasick算法不同，Flashtext算法不匹配子字符串，只匹配最长字符（完整的单词），首先匹配最长字符串。
  • 比如，输入一个单词 {Apple}，算法就不会匹配 “I like Pineapple” 中的 apple，输入单词集合 {Machine， Learning，Machine Learning}和文档“I like Machine Learning”，算法只会去匹配 “Machine Learning” 。

参考

• 字符串匹配的KMP算法
• KMP算法：线性时间O(n)字符串匹配算法
• 算法学习之Aho-Corasick
• 深入理解Aho-Corasick自动机算法
• Aho-Corasick算法的Java实现与分析
• Aho-Corasick automaton（AC自动机）解析及其在算法竞赛中的典型应用举例
• NLP模式高效匹配技术总结：模式匹配常见落地场景、AC自动机原理及高效开源工具总结