DFA的实现

在工业界,DFA的有效实现一直是一个问题,龙书中提到了一种使用四个数组的通用DFA实现,在汉字分词算法中经常用到double array作为Trie的一种实现。四数组的是通用DFA的实现,双数组的仅能用于实现Trie。并且它们的创建速度慢,难以理解,内存占用也比较多,状态id的值域范围稀疏。

我的实现

我实现了一种很紧凑的DFA,这在某种程度上源于popcount带来的灵感。当然,我的这种实现也是有局限性的:仅用于字母表为byte的情形,虽然这在绝大多数情况下已经足够,但是作为确定性PushDown Automata的基础DFA时可能就不够了。

关于popcount有很多有趣的故事,大家可以在网上搜一下。我在DFA实现中,popcount是结合位图使用的:

states[s].targets是个数组,它只需要包含实际存在的那些转移。这看上去不错,但是,在现实中,绝大多数DFA的状态只有很少数的转移,甚至有很多DFA,超过80%的状态仅有一个转移,这样做还是太浪费了!所以,在我的实现中:

l  minch,maxch

表示所有转移标号(label)的范围,因为一般情况下,不光转移的数目很小,而且转移标号的范围也很小,从而bitmap可以更小,而不是总需要256bit(32byte)。

在其它的State实现中,甚至maxch都不需要,只需要一个能表示bitmap尺寸的更小的数(可以用bitfield)。

l  spos

在一般情况下,spos是指向MemPool的一个偏移,这个偏移处保存bitmap+transtions,bitmap的位数是(maxch-minch+1)对齐到32(相当于4字节),transition的个数等于popcnt(bitmap)。因为每个transition至少4个字节。bitmap最少也4个字节,所以spos是按4个字节对齐的,因而,可以把它乘以4,这样可以有更大的寻址空间。

当minch==maxch时,仅有一个转移,转移标号就是这个minch,因为仅有一个转移,spos就直接表示目标状态。

spos存储MemPool的偏移,而不是绝对地址,有以下原因:

1.  节省内存

a)  避免多个小块内存

b)  64位环境下指针是8字节

c)  State可以压缩的更小(压缩的State,4个字节可以表达256K个状态)

2.  内存访问的局部性更好,对CPU Cache 更友好

3.  便于序列化

序列化时,除了MetaData,只需要把State数组和MemPool整个写出去

4.  拷贝更快

甚至连拷贝构造函数都不需要实现:默认的拷贝构造就足够用并且非常快

抽象

C++真是一种强大语言,通过仔细的设计和编码,我们可以达到性能与抽象的完美结合!除了C++,谁还能把一个萝卜两头切了?

Template

 

l  State是模板化的

除了前面的State32,可以使用任何实现了StateConcept 的类。比如我就实现了PackedState,从而有State4B,State5B,State6B,State7B,分别占用4,5,6,7,8个byte,其中7的state_id可以达到2T。

并且,在实现Aho-Corasick算法时,State还加上了额外的成员:output_set和fail_link,当然,因为State是一个数组,state_id是数组下标,可以把这些额外数据存到平行的数组中去,但是,和State放在一起可以提高内存访问的局部性,对CPU Cache更友好。

l  Transition是模板化的

在 DAWG 中,每个Transition 附带一个数字。

Functional Programming

那么复杂的实现,如果难用怎么办?C++从stl开始,就鼓励generic programming,而generic programming中很核心的一点就是functional programming,stl中functor无所不在。

在简化编程接口上,我也不遗余力,在这里仅举一个最有代表性的函数:

template<class OP>

void for_each_move(state_id_t curr, OP op)const;

就这一个接口,几乎可以实现所有需要对整个DFA进行遍历的功能:

1.  write_dot_file

2.  path_zip

3.  for_each_word

……

ctz (count trailing zero)

for_each_move这个函数的实现也很有意思,一个简单的实现如下所示:

上面这个实现简洁明了,并且似乎没什么可优化的。但是,前面说过,绝大部分状态只有很少的转移,甚至有很多状态只有一个转移!为什么我们要浪费那么多cpu呢?我们又怎么才可以把那些浪费的cpu给找回来?

幸好,几乎所有现代cpu都有这么一条硬件指令: ctz (count trailingzero),就是计算一个机器字的末尾(右端)有多少个0!于是,上面的代码可以修改如下:

 

这样循环次数就只是真实的转移个数,而不是256上面假定ctz指令的机器字是256bit,但这可能不是实际情况(intel最新的avx指令集已经有直接计算256bit的ctz了!),在真实代码中是分开对各个机器字计算的。

有这么几点需要注意:

1.  当bm全为0时,ctz的结果是unspecified,所以我们要确保调用hardware_ctz时bm不全为0。

2.  代码中的移位语句是:

bm<<= ctz;

bm<<= 1;

两条语句,为什么不

bm <<= ctz+1

一条语句呢?

当ctz==wordbits-1时,

bm<<= ctz+1;

就是bm<<= wordbits;

这样的移位结果按C/C++标准是unspecified,intel处理器中是bm的结果不变。我当初在栽到过这个坑里!

 

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

您可能感兴趣的文章:

2 个回复

  1. beyond_boy说道:

    啥叫“字母表为byte的情形”?扯淡把

  2. whinah说道:

    连这句话都理解不了,你还是赶紧改行吧

发表评论

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