DFA的兑现

DFA的实现
DFA的实现

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

我的实现

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

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

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的结果不变。我当初在栽到过这个坑里！

 

查看更多 下一篇