自动机的一些算法和应用

几个月前实现了一个自动相关的算法,在一个比较乐观的测试中,将一个2.3G的url集合压缩到了27M,同时,key查找的时间复杂度是O(strlen(key))。当然,还有其它一些自动机相关的算法的优化实现,比如Aho-Corasick多模匹配。

 

自动机的实现,这里说的自动机,指确定性的有穷状态自动机(DFA: Deterministic Finite Automata)。关于非确定性的有穷状态自动机(NFA:Non-deterministic Finite Automata),不会做过多介绍。NFA和DFA本质上是等价的,也就是说,它们的表达能力(能识别的语言的集合)是相同的。

“语言”这个词,在自动机理论中,往简单了说,就是(任意长度的)字符串集合。

NFA

定义:精确定义可参考维基百科

往简单了说,就是一个:map<state,map<char,set<state>>>,这里state是个整数,是state的标识(当然也可以是其他类型,只要能用作一个唯一标识)。

或者说是一个函数:delta(state,char)à{state}, {state}表示状态的集合

一般的NFA有个扩展,相当于在字符集中加了一个空字符,表示不需要读取输入,就可以自由地转化到其它状态。

正则表达可以很方便地翻译成NFA,然后再进行相关的操作(如直接匹配字符串,或者转化到DFA后再匹配,等等)。

DFA

定义:精确定义可参考维基百科

往简单了说,就是一个:map<state,map<char,state>>,这里state是个整数,是state的标识。

或者说是一个函数:delta(state,char)àstate

可以看到,DFA和NFA的唯一不同就在于它的转移函数的返回值是一个state,而不是多个state,并且DFA没有空转移。

NFA转化DFA

NFA既然和DFA等价,那么,它们之间就存在对应关系,DFA到NFA的转化是自明的:没有空转移,把返回的单个state编程仅包含一个state的集合,就是一个形式上的NFA。但是,NFA到DFA的转化就不是那么简单了,实际上,在计算理论中,它属于ExpSpace问题,是一类比NP问题更难的问题。

往简单了说,因为NFA的转移函数的返回值是个state集合,如果NFA的state数目为n,那么这个state集合的集合,就是整数[0,n)的幂集,这个幂集的元素数目是  ,不错,在最坏情况下,包含n个状态的NFA对应的DFA有 个状态。

具体的转化算法,叫做“子集构造法”。

DFA最小化

不同(去除同构)的DFA,其能识别的语言可能相同,既然如此,当我们得到一个DFA时,我们就希望找到一个最小的DFA,它能识别的语言和这个DFA相同。最小的DFA,是指状态数最小。最典型的两个例子:

l  从NFA用子集构造法转化来的DFA,一般不是最小的

Trie,是一个DFA,但它一般也不是最小的

Hopcroft DFA 最小化算法

这个算法是已知的最快的通用DFA最小化算法,不幸的是,几乎没有任何教科书讲到这一点,绝大部分教科书,不过是简单提了一下。甚至Hopcroft自己的那本形式语言与自动机,也不过只用两三页,描述了一个几乎是最差的算法。这个算法是Hopcroft发明的,我很奇怪他为什么不在自己的书里详细讲解。

这个算法的核心有两点:

分区细化(Partition Refinement)

n  也许叫做子集细化更合适

n  可能知道并查集(Union Find Set)的人更多,并查集是不断合并集合,而Partition Refinement正好相反,是不断地切分集合

l  Unspecified add/remove sequence queue

n  实现Hopcroft还需要一个队列,不过这个队列不必是先进先出的,它的元素可以以任意顺序进出,包括先进后出(stack)

n  在实践中,先进后出(stack)的策略可以让整个算法运行得更快

n  这个队列在Hopcroft算法中叫做WaitingSet

Hopcroft算法的简单介绍可以参考维基百科

所谓Partition,就是构成一个集合的多个互不相交的子集,在Hopcroft算法中,集合就是State的集合。

我的Hopcroft算法实现上有一些优化:

第一点:

Partition的数据结构,操作最频繁的是:

1.        创建Partition

2.        从一个Partition把元素移动到另一个Partition

能高效这两个操作的数据结构,只有双向链表,增加、删除结点的时间复杂度都是O(1):每个Partition需要一个链表头,链表元素个数,再把所有元素用双链表链起来。

我看过的所有Paper都是这样的实现:物理的链表。但是我仔细思考了一下:所有Partition都是互不相交的!

定理:给定数组int P[N],如果P中的数字是[0,n)的一个排列,那么如果将P[i]看成数组下标的链接,那么P中包含了多个逻辑环状链表,并且这些逻辑环状链表互不相交。

于是,我就可以用数组: struct{int next, prev;} 来表达这个Partition。

第二点:

for each c
in
do

|Σ|一般比较大,比如对于计算机的标准字符集字节来说,|Σ|=256,而每个state的(反向)转移一般很小,这样就浪费了很多计算。所以,我一次性将一个partition中的所有反向转移都收集起来,按转移的char分类,再逐个执行Partition Refinement。

有穷字符串集合的DFA

前面说说通用DFA,是因为存在一些特殊的DFA,有特殊的专用算法,有些情况下比Hopcroft算法更快,占用内存更小。有穷字符串集合的DFA就是这样一种特殊情况。

最简单的有穷字符串集合的DFA就是一个Trie,但Trie不是能表达该有穷字符串集合的最小DFA。

能表达一个有穷字符串集合的最小DFA叫做:DAWG(DirectedAcyclic Word Graph),也叫MinADFA(Minimal
AcyclicDFA)。

要创建一个DAWG,一般的方法是先从字符串集合创建一个Trie,然后再Trie上应用Hopcroft算法,得到MinADFA。但是在实践中,这样的方法内存占用量太大,有人发明了针对这种情况的更好的算法:每加入一个Word,即执行动态在线(dynamic onfly)最小化,一般情况下这种算法比先建Trie再用Hopcroft要稍慢,少数情况下要快一点,但几乎在任何情况下,这种方法占的内存都要小得多。

仅作为字符串集合

如果我们仅仅需要一个字符串集合(相当于set<string>),那问题非常简单,使用动态在线最小化是最好的选择。

这里我只实现了两种操作(不支持delete):

bool exists(string):是否接收/存在一个字符串

bool insert(string):插入一个字符串,如果已存在,返回false,否则true

工程实践中有人使用bloomfilter来判断字符串的存在性,这种方法在网络爬虫中应用得比较多。但bloom filter是不确定性的,它有可能把实际上不在集合中的判断为在。

现在,有了动态dawg,bloom filter可以退役了。

作为key,value映射表

要作为key,value映射表,事情就变得有些复杂了,如果只是Trie,我们可以把value(或者value的指针)存放在state中,但是当Trie变成了DAWG,同一个state,可能经由不同的路径到达,一个路径,就是一个字符串,多个不同的路径,就是多个字符串,多个字符串,那不成多对一了吗?我们要的是一对一!

别着急,我们有的是办法:在每个State上额外保存一个整数,表示从这个State有多少条不同的路径能到达终止状态。然后,在匹配字符串时,我们可以用这些信息算出一个唯一的确定的整数来标识这个字符串。更妙的,算出来的这个标识正好是这个字符串在该DAWG表达的字符串集合的字典序的序号!还有更更妙的呢:这个映射是双向映射,不光可以从字符串找到它的字典序号,还可以从它的字典序号反推出这个字符串本身!

于是,我们只需要一个额外的value数组就OK了,从key找value时,算出该key的字典序,然后直接到value数组中去访问!

一切似乎很完美……

忽然,问题又来了,如果我们新插入了一个(key,value),而这个新key的字典序号有可能要小于已存的其它key,这样,我们岂不是要在value数组的中部插入新value?这时间复杂度是不能忍受的!

总有办法的,几年前我曾有一篇文章:,并且我也在线索红黑树上实现了这个算法,实际上《算法导论》中也讲到过这个问题。

优化

上面提到的方法是在state中增加一个整数,这种方法在匹配字符串的过程中到达一个state时,需要累加该state的转移的目标state中保存的那个整数,这样,最坏情况下,整个的时间复杂度是O(|Σ|*strlen(key)),这个|Σ|因子可以被优化掉!

将数字保存在转移中,这个数字表示label char小于该转移的label char的所有state到终止状态的路径总数。这样,只要看到这个转移,直接加这个数就可以了。这样做还有一个优点:实际应用中,大部分state只有一个转移,而任意state第一个转移上对应的那个数总是0,这个0可以省掉;在单一转移的情况下,省掉0实现起来比较简单直接,所以我就这么实现了;而在一个state有多个转移的时候,省掉0会把代码弄得很复杂,我就没这么做。

然而,这样也有缺点:在作为map时,无法动态插入,只能预先建好,然后仅做查找。当然,value的值是可以修改的。

应用于非MinADFA的ADFA

从字符串计算标号这件事,并非只能应用在DAWG/MinADFA上,它可以应用在任何ADFA上。决定是否用它只是一个做与不做的问题,而不是能与不能的问题。

比如,在Aho-Corasick算法中,就可以这样做,但这样做可能不是很值,我们可以选择不这样做。

DFA的实现

作者:
该日志由 csdn-whinah 于2012年08月31日发表在自动机分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 自动机的一些算法和应用
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

4 个回复

  1. lanxuezaipiao说道:

    请问这个DFA最小化的算法实现了吗?我现在也在做这个,有些想法,希望能与大神交流,能留下联系方式不

  2. 能不能给我DFA最小化的源代码看下下??

发表评论

您必须 登录 后才能发表评论。