DFA的实现
在工业界,DFA的有效实现一直是一个问题,龙书中提到了一种使用四个数组的通用DFA实现,在汉字分词算法中经常用到double array作为Trie的一种实现。四数组的是通用DFA的实现,双数组的仅能用于实现Trie。并且它们的创建速度慢,难以理解,内存占用也比较多,状态id的值域范围稀疏。
我的实现
我实现了一种很紧凑的DFA,这在某种程度上源于popcount带来的灵感。当然,我的这种实现也是有局限性的:仅用于字母表为byte的情形,虽然这在绝大多数情况下已经足够,但是作为确定性PushDown Automata的基础DFA时可能就不够了。
关于popcount有很多有趣的故事,大家可以在网上搜一下。我在DFA实现中,popcount是结合位图使用的:
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%的状态仅有一个转移,这样做还是太浪费了!所以,在我的实现中:
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
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这个函数的实现也很有意思,一个简单的实现如下所示:
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!于是,上面的代码可以修改如下:
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的结果不变。我当初在栽到过这个坑里!
啥叫“字母表为byte的情形”?扯淡把
连这句话都理解不了,你还是赶紧改行吧