目前的gold_hash_map 实现中,index和data是耦合在一起的。
今天在思考 onfly MinADFA 的进一步优化时,想到了一点:在MinADFA_onfly 中,equivalence_register是一个gold_hash_tab, 继续阅读
Trie的搜索复杂度是 O(length(strkey)),Hash表,计算Hash的复杂度也是O(length(strkey)),但是,仔细分析一下: 继续阅读
NFA既然和DFA等价,那么,它们之间就存在对应关系,DFA到NFA的转化是自明的:没有空转移,把返回的单个state编程仅包含一个state的集合,就是一个形式上的NFA。但是,NFA到DFA的转化就不是那么简单了,实际上,在计算理论中,它属于ExpSpace问题,是一类比NP问题更难的问题。
在工业界,DFA的有效实现一直是一个问题,龙书中提到了一种使用四个数组的通用DFA实现,在汉字分词算法中经常用到double array作为Trie的一种实现。四数组的是通用DFA的实现,双数组的仅能用于实现Trie。并且它们的创建速度慢,难以理解,内存占用也比较多,状态id的值域范围稀疏。