DFA的实现

     作者: csdn-whinah 发表日期: 2012年09月05日 

http://nark.cc/p/?p=163

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

我的实现

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

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

C++

1 2 3 4 5 6 7 8

state_id_t state_move(state_id_ts, byte c) const {     bit256 bm = states[s].bitmap;     if (bit256.is1(c)) {         int index = popcnt(bm & 0...1); // 高位256-c个0，低位c个1         return states[s].targets[index];     }     return null_state; }

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

C++

1 2 3 4 5 6 7 8

class State32 { // sizeof(State32)==8     uint32_t spos; // spos*pool.align_size isthe offset to MemPool     char_t  minch;  // min char     char_t  maxch;  // max char, inclusive     unsigned term_bit : 1; // 是否终结状态     unsigned pzip_bit : 1; // 是否路径压缩    // more... };

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

C++

1 2	template<classState, class Transition = typename State::state_id_t> class Automata;

 

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这个函数的实现也很有意思，一个简单的实现如下所示：

C++

1 2 3 4 5 6 7 8 9

template<class OP> void for_each_move(state_id_t curr, OP op)const {    bit256 bm = states[curr];    int idx = 0;     for(unsigned ch = 0; ch < 256; ++ch) {        if (bm.is1(ch))            op(curr, states[curr].targets[idx++], ch);     } }

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

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

 

C++

1 2 3 4 5 6 7 8 9 10 11 12 13

template<class OP> void for_each_move(state_id_t curr, OP op)const {    bit256 bm = states[curr];    int idx = 0;     for(unsigned ch = 0; bm != 0;) {         int ctz = hardware_ctz(bm);        ch += ctz;        op(curr, states[curr].targets[idx++], ch);        ch += 1;        bm <<= ctz;        bm <<= 1;     } }

这样循环次数就只是真实的转移个数，而不是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的结果不变。我当初在栽到过这个坑里！