AC自动机AC自动机.pdf

字符串精确匹配问题 • 问题描述：对于模式串集合P={p1,...,pk}，在目标串T[m] 中找出现了哪 些模式串。 • 设n=|p1|+...+|pk| • 普通算法的时间复杂度是O(n+km) • AC 自动机算法是解决这种问题的一个经典方法，时间复杂度为 O(n+m+z)，其中z是T 中出现的模式串的数量。 • AC 自动机是基于keyword tree的，并对其进行一些补充。 • KMP算法所解决的问题与这个类似，区别是KMP解决的问题是在目标 串T 中找一个模式串p出现的位置。其实两个算法的精髓也一样：当匹 配失败时可以最大程度的利用之前已匹配成功的串以避免重复匹配。 Keyword tree  keyword tree又叫“单词树”、“字典树”、“trie树” • 对于模式串集合P={p1…pk}的keyword tree是具有以下特性的有根树： 1. 每条边的值都是一个字符 2. 从一个点出发的任意两条边的值都不同 3. 结点v 的值被定义为L(v)={从根结点到结点v 的路径上的所有边的值的 序列} 4. 对任意模式串pi，都能找到一个结点v使得L(v)==pi 5. 对任意的叶子结点v ，都能找到一个pi使得L(v)==pi Keyword tree • A keyword tree for P={he,she,his,hers} h e r s i root s s h e keyword tree：构建 对于模式串集合P={p1…pk}，构建keyword tree： 1. 从仅有的一个根结点开始 2. 依次插入模式串pi：从根结点出发，随着值为pi中当前字符的边一 直走下去， – 如果在pi中的字符结束之前，路径就终止了，那么为pi中剩余的所有字符创建新 的边和结点 – 在pi结束的时候，记录一下当前的结点为模式串pi的终止结点 • 构建的时间复杂度为O(|p1|+...+|pk|)=O(n) keyword tree：查找 • 在keyword tree中查找一个字符串p，也就是判断p是否出现在模 式串集合P中：从根结点出发，随着值为p中当前字符的边一直往下走。 – 如果在p结束时，当前的结点是一个被记录的终止结点，那么查找成功，p在模式 串集中 – 如果在p结束前，路径就终止了，则查找失败，p不在模式串集中。 • 查找时间复杂度为O(|p|)——一个高效的查找方法 • 一个普通的模式串匹配方法的时间复杂度将是O(nm)，模式串的数量 为n，平均长度为m。 • 下面将把keyword tree扩展为一个自动机（Automaton），它可 以在线性的时间内进行匹配。 AC 自动机 （Aho-Corasick Automaton ） keyword tree的每个结点就是一个状态，根结点是初始状态（状态0） 自动机的行为被定义为一下3个函数： 1. goto函数g(q,a)：返回从当前状态q走值为a的边后所到达的状态 – 如果从根结点出发没有值为a的边，那么g(0,a)=0，（就是说：当读入不匹配的 字符时，自动机保持在初始状态） – 如果从结点q出发有一条边值为a到达结点v，那么g(q,a)=v – 否则g(q,a)=Φ 2. fail函数f(q)：返回从状态q(q!=0)匹配错误时要转移到的状态 – 如果L(v)是L(q)的一个后缀，且是最长的后缀，则f(q)=v，（就是说：一个错