《有穷自动机的原理及应用》由会员分享，可在线阅读，更多相关《有穷自动机的原理及应用（43页珍藏版）》请在金锄头文库上搜索。
1、有穷自动机的原理及应用雷鹏2014-07-15大纲基本概念DFA最小化：概念DFA最小化：算法AC自动机（多模匹配）DFA的实现API与工具箱DFA与NFA转移目标是一个状态集合，可能包含多个状态DFA到NFA的转化ADFAAcyclicDFA无环自动机无环自动机只能表达有限的字符串集合Trie:最简单，最大的ADFAMinADFA:最小化的无环自动机内存需求小，极端情况下压缩率是指数的随着集合的增大，MinADFA可能反而更小后缀自动机:后缀树的泛化典型应用RegularExpression正则表达式LexicalAnalyzing词法分析PatternMatching模式匹配精确匹配，前缀
2、匹配多模匹配(AC自动机)，多正则匹配DictionaryCompressing词表压缩自动机最小化，字典序计算DFA的最小化：等价&同构DFA等价DFA表达的语言相同等价的DFA状态数可能不同状态数最小的那个DFA称为最小的DFA更小的DFA需要的内存更小DFA同构状态数相等，表达的语言相同对状态编号做一置换后，完全等同规格化的DFA：状态编号为从初始状态执行深度优先遍历的序号063的二进制串未最小化的Tree形状的DFA(Trie)最小化的DAG形状的DFA(DAWG)未最小化的Tree形状的DFA(Trie)最小化的DAG形状的DFA(DAWG)062的二进制串相当于将n个状态压缩到O(
3、log(n)个状态极端的例子：字符串“1” “99999”未最小化的Tree形状的DFA(Trie)最小化的DAG形状的DFA(DAWG)intint_tintmax_tint8_tint16_tint32_tint64_tuintuint_tuintmax_tuint8_tuint16_tuint32_tuint64_tDFA的最小化算法Hopcroft算法原理MyhillNerode等价对任意输入，同一分区(子集)中两个状态p,q的行为相同，则p,q是MyhillNerode等价的行为相同即：对任意w，(p,w)与(q,w)要么都是都是终止状态，要么都不是都不是终止状态PartitionR
4、efinement可直译为分区分区细化化PartitionRefinement是Hopcroft算法的一个关键操作，该操作使用一个函数将集合的当前切分中的每个分区进行再切分，直到不能继续切分Hopcroft算法伪代码P:=F,QF;/表示集合减法，Q表示所有状态的集合，F表示终止状态集合W:=F, Q F;/此伪代码来源于维基百科，但维基百科此行有误 / Q F 也必须加入W(WaitingSet)/其它一些论文中将W初始化为min(F,QF),也不对while(Wisnotempty)dochooseandremoveasetAfromWforeachcindoletXbethesetofs
5、tatesforwhichatransitiononcleadstoastateinAforeachsetYinPforwhichXYisnonemptydoreplaceYinPbythetwosetsXYandYXifYisinWreplaceYinWbythesametwosetselseaddmin(XY,YX)toWYXHopcroft算法实现逆自动机一般DFA的逆是一个NFA，结构比较复杂Trie的逆是一棵倒长的树，结构非常简单用smallmap收集反向转移双向链表（插入、删除均为O(1)）用数组下标做链接集合的一个切分切分可用一个排列(permutation)表达切分切分是指将一
6、个集合切分切分成多个互不相交的子集WaitingSet可以任意次序进出栈式的WaitingSet可使算法运行得更快ADFA最小化的基本原理ADFA最小化算法状态等价的计算：StateRegister按右语言等价的定义，实现一个mapTargetSet是StateID标识的状态的转移：pair(Char,Target)的有序集合Online算法插入新字符串（可能需要复制路径），得到新状态，用新状态的属性作为Key查找map，如果找到，则用找到的状态替换新状态替换时，使用深度优先，后序遍历（从深往浅）Offline算法原DFA到新(最小化的)DFA的状态映射计算等价状态时使用映射后的状态比Hopc
7、roft算法快得多（时空复杂度：O(n)）ADFA最小化算法：泛化Online算法用于非ADFA时如果原DFA已是最小化增加/删除一个串之后，仍然是最小化的即使增加/删除的串会通过(paththrough)有环的子结构Offline算法用于非ADFA时无法将有环的子结构最小化无环的子结构仍然可以被最小化按graph-post-order-walk顺序ADFAOnline最小化：字典序的输入1.一旦执行最小化，前面的自动机状态不会再变（深度优先，后序）2.找出（当前串与上一个串的）公共前缀CommonPrefix3.从上一个串尾至CommonPrefixLen执行状态合并（按StateRegis
8、ter）4.每次加入一个串，整个DFA是不完全不完全最小化的，完成时需要执行一次最终的最小化ADFA的最小化：任意顺序的输入汇合状态（ConfluenceState）：有多个前驱状态的状态需要克隆从汇合状态开始的路径加入当前串之后，在当前串的路径上从后往前执行最小化每加入一个串，整个自动机是完全完全最小化的速度稍慢，内存用量稍大（比顺序输入）DAWG:ADFA+字典序号我们大多数情况下需要一个Map普通的ADFA只能表示SetDAWG(DirectedAcyclicWordGraph)可以从ADFA中得到一个串在该ADFA中的字典序可以从字典序反推(还原)出ADFA中的一个串将map中的Val
9、ue保存一个数组中DAWG的实现(两种方案)A:在每个状态上保存该状态的右语言集合的尺寸B:在每个状态转移(图的边)上保存转移字符小于自己的转移字符的其它目标状态的右语言尺寸之和u这种方案对应的算法更快，直观上看需要更多的内存，但实际上，每个状态的第一个转移对应的这个数字总为0，可以省去，再加上对于很多自动机，状态的平均转移数小于2，从而，需要的内存就更少（只有当平均转移数大于2时，这种方案才比 方案方案A A 需要更多的内存）！DFAMap的另一种实现(key,val)用特殊字符delim分隔例如：keytvaluedelim不可出现在key中，但可以在value中对用户更加友好，适用性更广
10、更进一步：key可以是可以是正正则表达式表达式！delim0,256),key不能是任意二进制串扩展=0,257)，令delim=256key就可以是任意二进制串对多多正则表达式匹配尤其有用路径压缩将直线形的状态序列压缩成一个状态序列中每个状态只有一个后续状态除序列起始起始状态，其它状态都不是汇合合状态除序列末尾末尾状态，其它状态都不是终止止状态路径压缩一般可以将状态数压缩到原来的30%甚至更少路径压缩的DFA串匹配速度更快在压缩的路径上是精确的串比较无状态转移，对CPUCache更友好路径压缩的适用范围与DAWG完美兼容可以应用到任意形状的DFA上包括有有环的DFA在MinDFA上应用路径压
11、缩可进一步减小状态数路径压缩后的DFA不再是严格意义上的DFA无法（很难）进行修改操作通用的DFA算法不再适用AC（Aho-Corasick）自动机AC自动机与TrieAC自动机是基于Trie的每个状态中有附加数据一个faillink模式串集合的一个子集因为一个模式串可能是另一个模式串的后缀AC自动机可以用DoubleArray实现AC自动机最坏情况时间复杂度是最优的扩展的AC自动机DFA的实现最简单的实现(需附带一个位图保存终止状态标志)typedefunsignedintstate_id_t;typedefunsignedcharchar_t;typedefstate_id_tautoma
12、ta_t256;缺点：空间消耗太大，仅适用于Demo级应用非常小的DFA状态转移非常密集的DFA实际应用中往往有包含数亿，甚至数十亿状态的自动机，需要使用更紧凑的实现正则表达式的DFA一般比较小，也比较密，用这种简单实现是可行的。GoogleRE2中的DFA就是用了这种实现紧凑的实现工程实践DoubleArrayTrie启发式填充方法（一般可以填充到99.9%以上）Offline填充：BFS/DFS遍历时填充，不需重定位Online填充：无空位时需要重定位BitmapByteCharSetDFAmin/maxchar+指针（整数表示的相对偏移）仅一个转移时，指针直接指向目标状态有多个转移时，指
13、针指向内存池中的Bitmap+数组使用硬件popcnt和ctzSuccinctReprsentation基于Rank-Select数据结构比基于指针的数据结构小30%以上一般情况下压缩率比bzip2更大匹配、查找速度慢6倍左右只能表达TrieTreeEdge用Rank-SelectNon-TreeEdge用指针表达MemoryMapping所有DFA的内存表示都是一个或多个数组，很适合MemoryMapping极大提高加载性能第一次加载时，减少一次memcpy已被缓存时，连memcpy都省了使用共享mmap，多进程时仅占一份内存DFA创建工具构造生态系统应用程序dfa=DFA_Interfac
14、e:load_from(“dfafile”);原始输入DFA二进制文件创建dfa的工具集：adfa_build,dawg_build,regex_build,kvbin_build,ac_build.,也可以是针对特殊场景的定制build工具可以可以 MapReduce 并行建并行建库任意使用DFA的应用程序dot文件dot画图工具svgpdfpngkeyonly:strset/dawgkeyt val:mapregex t data/regex_id基本build工具adfa_buildsetdelimmapstring,setnestedmapstring,mapstring,mapdaw
15、g_buildmapkvbin_build(delim=256)mapByteArray,setnestedmapac_build(创建AC自动机)复杂build工具regex_build多正则匹配(MultiRegularExpressionMatching)匹配时间：O(strlen(Input)+matched_regex)与正则表达式总个数无关可以同时获取OnePass正则的submatchdfa_union计算多个DFA的并集pinyin_build解决多音字问题的拼音查找API接口：DFA_Interface隐藏了DFA所有的实现细节DFA_Interface:load_from(
16、filename)可以加载所有种类的DFAregex正则表达式的DFAadfa有穷字符串集合的DFAdawgdfaacdfa(包括但不限于DoubleArray的实现)多个dfa的并集(filename包含多个用;,分隔的文件名)#includeAPI接口：dawg&acDFA_Interface*dfa=DFA_Interface:load_from(“somefile”);/useasnormaldfa/.constDAWG_Interface*dawg=dfa-get_dawg();if(NULL!=dawg)/useasdawgconstAC_Scan_Interface*ac=dfa
17、-get_ac();if(NULL!=ac)/useasAho-CorasickDFA更复杂的应用：直接调用创建接口同义词表相当于:mapAnchor映射表相当于:map不同url的AnchorSet交集可能不空一种扩展的全匹配ADFAonflybuild+NFA/DFA转化+DFAMinimize按拼音查找汉字短语(pinyin_build)解决多音字问题：P1*P2*Pn需要需要C+11更进一步:语法压缩SLCF直线上下文无关语法StraightLineContextFreegrammar最佳压缩率:n-O(log(log(n)ADFA压缩率:n-O(log(n)计算最小SLCF语法是NP问题使用贪心近似算法主页:(不开源)实现语言:C+11操作系统&编译器Linux:gcc-4.7+,icc-14.0,clang-3.4/3.5Windows:VisualStudio2013+,Cygwin-32/64其他环境下未测试应用开发编译、运行均不需要C+11，C+98即可谢谢！
