b超单上ac表示什么意思,b超单上ac表示什么

2022-07-06 13:50:05 焦点

　　KMP算法要理解AC自动机算法，首先要理解KMP算法。　　

　　这篇文章很好：　　

　　http://www . Ruan Yifeng . com/blog/2013/05/KnuthMorrisPratt _ algorithm . html 　　

　　结合这篇文章，我来阐述一下我的理解。　　

　　比如搜索如下，上面是原字符串，下面是搜索字符串。　　

　　要找出搜索字符串是否是从原字符串中出现的，已经发现ABCDAB全部匹配，但找到D时，不匹配。那么接下来正常的思路可能就是从原字符串的下一个字符，也就是第5个b开始重新匹配。　　

　　KMP的思路是充分利用之前已经比对过的信息，所以需要决定下一步原弦是否会后移几个位置。　　

　　核心是为搜索字符串建立一个部分匹配表：ABCDABD。　　

　　表格的结构是每个位置搜索时对应的部分匹配值，那么如何计算对应的部分匹配值呢？　　

　　例如，在搜索第7个位置D的ABCDABD时，部分匹配值为2，这是该子串从开头A到最后匹配位置b的最长前缀和后缀的公共长度。　　

　　因为前缀AB=后缀AB，所以部分匹配值为2。　　

　　比如ABCDXYABCD，那么部分匹配值就是4。　　

　　比如ABCD，那么部分匹配值为0。　　

　　那么，用于计算最后匹配的搜索串的每个位置(第一个不匹配位置)的向后比特数的公式是：　　

　　移动的位数=匹配字符数-对应的部分匹配值。　　

　　其实可以这样理解：　　

　　基于搜索字符串搜索D位置时，部分匹配值为2，即前缀AB=后缀AB，由于ABCDAB匹配原字符串中的ABCDAB，所以：　　

　　2AB=1AB，2AB=4AB，所以1AB=4AB，所以下一步可以直接移至下图：即后移4位(6-2)。前面的都不能匹配搜索字符串，没必要对比。　　

　　此时1AB=4AB，所以匹配可以直接从两者的下一个字符继续。　　

　　所以总结一下KMP算法的思路：　　

　　a、为搜索字符串建立部分匹配表，其实可以直接建立移动数字表。　　

　　b、开始搜索，一旦搜索到某个位置，如果不匹配，查表得到搜索字符串的下一个匹配位置。　　

　　AC自动机算法AC自动机实际上是在Trie字典树的基础上，增加了类似KMP算法的下一个数组。　　

　　它包含两个操作：　　

　　a、将所有模式串构建到Trie树中B、在Trie树上构建失效指针相当于KMP算法中的失效函数next array。假设现在有这个Trie树：有三个模式串。　　

　　现在要搜索的搜索字符串是efabcgh，目标是从这个搜索字符串中找到所有包含的模式字符串。很明显，头文件ef不匹配，所以从A开始，B也匹配，C也匹配，但是当你继续向下搜索到G，就找到了D！=g，那么接下来，从搜索字符串中A的下一个字符B开始，从Trie的根节点继续搜索可能是正常的。　　

　　AC自动机引入了一个失败指针，也就是这个时候，之前比较过的字符串也可以使用。通过失败指针，当匹配失败时，指向下一个比较位置。　　

　　肉眼看失败指针搜索方法：找到这个子串中匹配所有模式串前缀的最长后缀，从搜索串的开头到当前失败位置。比如efabcgh搜索G的一个字符串时，失败了，也就是在状态3下失败，abc匹配。然后，找到与模式字符串bcD的所有前缀相匹配的后缀abc最长的那个。abc的后缀是，很明显，bc和模式串bcd的前缀bc是一样的，而且是最长的一个，那么下一步就是从Trie树bcd中C的位置继续查找，然后节点3的失效指针就是。　　

　　指针的递归思想：以上是我们肉眼可以直接看到的失效指针。实际上，在代码中寻找失败的指针实际上是一个递归的过程。它是基于父节点的失效指针来寻找子节点的失效指针。例如，目前我们正在寻找3的失效指针。首先，3的父节点2的失效指针是，和上面一样，我们知道是5，所以这是递归中已知的第n-1步的结果。那么，如果父节点的失效指针5在输入C字符后能找到一个子节点(注意这里C和2到3之间的字符是一样的)，那么这个子节点就是失效指针3。如果字符不匹配，继续查找父节点。　　

2的失败指针5的失败指针。通过这种方式其实就是找到的搜索串的后缀和所有模式串的前缀的公共长度最长的节点。

所以总结下AC自动机的思路：具体的逻辑可参考下面的代码

a、构建Trie树b、构建失败指针c、开始查找：循环开始如果从Trie树中找到了匹配，那么Trie树去向子节点，并且搜索串后移如果没有找到匹配，并且此时在根节点，那么搜索串后移，此时会重新从根节点开始查找如果没有找到匹配，并且此时不在根节点，那么就去该节点的失败指针回到循环开始 AC自动机算法小实验：

#-*- coding:utf8 -*- import timeimport pdbimport sysfrom collections import defaultdict class Node: def __init__(self): self.patterns = <> self.children = {} #key是一个word，value是下一个Node self.fail_node = None class AC_Automation: def __init__(self, patterns): self.root = Node() #Trie树的根节点 self.fail_node = {} #存每个节点的失败指针 for pattern in patterns: self.add_pattern(pattern) self.build_fail() def add_pattern(self, pattern): curr_node = self.root for word in pattern: if word not in curr_node.children: child_node = Node() curr_node.children = child_node curr_node = curr_node.children curr_node.patterns.append(pattern) #BFS遍历求每个节点的失败指针 def build_fail(self): self.root.fail_node = self.root node_queue = <> #深度为1的节点的失败指针都是root for word in self.root.children: child = self.root.children child.fail_node = self.root node_queue.append(child) index = 0 while node_queue: print index index += 1 node = node_queue.pop(0) for word in node.children: child_node = node.children node_queue.append(child_node) #子孩子入队 # 递归式：fail(child) = goto(fail(father), ch) # 基于父节点的失败指针，递推子节点的失败指针。父节点到子节点之间的字符是ch，找到父节点的失败指针后，需要看该指针有没有子节点ch, 如果有，那子节点ch就是child的失败指针，否则，继续找father的失败指针 v = node.fail_node #先取父节点的失败指针 while v != self.root and word not in v.children: v = v.fail_node fail_node = v.children.get(word, self.root) child_node.fail_node = fail_node def search_pattern(self, text): curr_node = self.root patterns = <> index = 0 curr_node = self.root while index < len(text): print index word = text if word not in curr_node.children: if curr_node == self.root: index += 1 else: curr_node = curr_node.fail_node else: index += 1 curr_node = curr_node.children patterns.extend(curr_node.patterns) #可能字符串刚匹配完的时候，恰好找到了最后，比如一个分支是def,另外有一个分支ef, 那么匹配字符串def会匹配成功，此时应该继续跳失败节点才能把ef匹配成功 while curr_node != self.root: curr_node = curr_node.fail_node patterns.extend(curr_node.patterns) return patterns if __name__ == '__main__': patterns = <'abc', 'ab', 'def', 'acg', 'cd', 'bc', 'bcd', 'ef', 'de', 'efg', 'fg', 'ghk', 'gk', 'hk', 'a'> ac = AC_Automation(patterns) print ac.search_pattern('abcdefghk') #输出：<'a', 'ab', 'abc', 'bc', 'bcd', 'cd', 'de', 'def', 'ef', 'efg', 'fg', 'ghk', 'hk'>我们知道，AC自动机有一个很大的问题是，消耗的内存特别大，当我们要做的中文字符串的查找时，如何选择最小的字符单位，会直接影响查询速度和占用内存，比如：

建造Trie树的时间、构建失败指针的时间，占用的内存等下面是我做的测试：

我的模式串总共10w个，每个串都不长，平均差不多4个汉字

搜索串的长度为489个汉字

a、以utf8为最小单位，即树的每个节点是utf8的，所以一个汉字会被拆分成两个节点，得到的结果