更新记录
2014-12-29 ~ 2015-01-21
- 增加 NestLoudsTrie
- 增加 NestPatriciaTrie，基于NestLoudsTrie
- 使用 NestLoudsTrie 优化 LoudsDFA
- 新增了 tool/fsa/rptrie_build, 用于创建 NestPatriciaTrie
- 完善了各种 DFA 创建工具的 help/usage 信息
对于“自然”的数据集，NestPatriciaTrie 在很多时候比 LoudsDFA 压缩率更高一点，查询速度也不慢。并且，NestPatriciaTrie 也实现了 DFA_Interface 接口。NestPatriciaTrie还有一个附加功能：可以把字符串映射到一个整数ID，不过，对基于Louds的NestPatriciaTrie，这个ID不是字典序号，而是 (字符串长度 + 字符串内容) 序号，只有当集合中的所有字符串都等长时，才和字典序等价。
对于有组合性质的数据集，LoudsDFA 压缩率比NestPatriciaTrie要高得多，同时，LoudsDFA 也可以使用NestLoudsTrie 进一步压缩，首页上的拼音纠错演示程序使用NestLoudsTrie 优化之后，其 DFA 数据库尺寸从 362M 降到293M，减小了 20%，该 DFA 就对应一个高度组合重复的数据集。
2014-12-24
- 优化 Base AC 自动机匹配代码，性能提高了大约 30%，2000 个 pattern 匹配速度达到 720MB 每秒(cpu: i7-4790)。
- 实现了 FullDFA 和 AC_FullDFA，无 nil 转移，内存用量很大(Base AC 的 10 倍以上)；虽然理论上 AC_FullDFA 对每个字符的最坏匹配时间都是O(1)，但综合性能(167MB 每秒)还是比 Base AC 要慢很多
2014-12-11
- Windows版的 regex_build: 使用 https://github.com/google/re2，再做了一些修改，最终在 Visual C++ 2013 中编译通过。
- VirtualMachineDFA.DirectMap：修改了一个bug。
2014-12-10
增加 DirectMap 优化，DirectMap 优化既减小尺寸，又提高速度，因为少了一层间接寻址。
在一个10万条正则表达式的测试集中(DFA 状态数: 3,819,033, 转移数: 239,801,234)，各种优化效果如下：
| DFA Type | Optimization | Size In Bytes | Bits Per Transition |
|---|---|---|---|
| DenseDFA | 420,755,776 | 14.03 | |
| VirtualMachineDFA | Not Optimized | 136,635,392 | 4.56 |
| IndexMap | 53,286,080 | 1.78 | |
| IndexMap + ShortPointer | 38,693,504 | 1.29 | |
| IndexMap + ShortPointer + DirectMap | 35,714,112 | 1.19 |
2014-12-09
VirtualMachineDFA/VirtualMachineDFA
优化：尽可能减小状态指针的宽度，删除了3条不常用的指令，新增了 4 条使用相对地址的 index_mapped 指令，为此增加了一个多趟全局优化，给State重新编址。
2014-12-04 ~ 2014-12-05
VirtualMachineDFA
重大优化：增加dest_index_mapped 和 loop_index_mapped 指令，引入全局同构的 lookup table，尺寸减小一倍以上。
2014-11-26 ~ 2014-12-02
陆续将 nark 中的一些模块开源，不过自动机在可预期的将来仍不会开源。开源的模块包括：
- https://github.com/rockeet/nark-bone
- https://github.com/rockeet/nark-serialization
- https://github.com/rockeet/nark-rpc
- https://github.com/rockeet/nark-hashmap
- https://github.com/rockeet/nark-cstl
- https://github.com/rockeet/nark-berkeley-db-util
2014-11-24 ~ 2014-11-26
重大重构：将 febird namespace 改名为 nark，这是一个很艰难的决定，febird 是我根据自己的名字“鹏”取的英文名字，Febrary Bird ，二月鸟，很形象。
但是改名为 nark 有更多的原因……
这次改动顺便将所有全局的C++类移动到 nark 名字空间。
2014-11-18
完成 rank_select_il
重构 LoudsDFA，增加 LoudsDFA_IL (使用 rank_select_il )
实测 LoudsDFA_IL 的搜索性能反而比原先的 LoudsDFA 略低(大约2%)，有待进一步观察优化……
2014-11-14
rank-select 数据结构
工作进行中：增加 rank_select_il，rank的索引与位图数据保存在一起，交错存放，rank-select时，提高CPU缓存命中率，但是 bit 访问速度会有所降低。
拼音纠错演示网页
增加简拼纠错，当输入的搜索词长度大于等于5时，可以选择是否开启简拼纠错：简拼与搜索词相同的也一并召回。
2014-11-04
regex_build (规则引擎建库程序)
增加 dfa-cluster 功能，该功能在创建动态匹配 DFA 时，使用一种启发式方法，预先对无状态冲突的正则表达式求并，从而提高匹配速度并减少内存用量。实测表明，匹配速度提高 1~3倍，动态内存用量(不包括DFA文件的mmap内存)减少一倍。
在多线程匹配中，每个线程使用一个动态DFA匹配器，并共享静态部分(regex_build 生成的 mmap 文件)，该功能在这种情况下有巨大的优势。
VirtualMachineDFA
修改了一个生成 VirtualMachineDFA 中的一个 bug
2014-10-30
修复了 rank select 算法针对 haswell(使用 bmi2 指令集) 优化实现的 bug
2014-10-26
VirtualMachineDFA
修改了多个 bug，VirtualMachineDFA 现在已经可用，在 regex_build 中使用 –o output-dfa-file, –o 是小写 o
经测试，utf8 字符集下，VirtualMachineDFA 的内存用量是 DenseDFA 的 35% 左右；latin1 下 (byte模式) ，内存用量是 DenseDFA 的 13% 左右。
匹配速度根据正则表达式和待匹配文本的不同，和 DenseDFA 相比，互有胜负，但都比 google re2 中的多正则匹配更快更省内存。VirtualMachineDFA 的综合性能高500~2000倍。
综合性能 = 1 / (内存用量*运行时间)，因为现在的CPU都是多核，那么：
- 如果坏算法的内存占用是好算法的 n倍，好算法就可以在相同的内存中并行运行n个实例
- 同时好算法的单线程速度又是坏算法的m倍
- 综合以上两点：好算法总的吞吐率就是坏算法的 m*n倍
2014-10-19
新增 ddfa_state，主要用来查看 regex_build 产生的 dfa文件（的统计信息），也可以用来查看其它 dfa build 程序生成的 dfa 文件。
2014-10-18
regex_maxmatch.cpp: add binary mode matching，可以读取二进制数据，用来测试匹配，数据格式：| record_len_int32 | record_data | ，regex_maxmatch 一直读取这样的多条数据记录，直到文件结束。
2014-09-23
regex_build (规则引擎建库程序)
增加非贪婪连接(NonGreedy Concat)操作符，在 DFA 上使用非贪婪匹配，详细内容，请参考 支持 并、交、差 的正则表达式引擎。
2014-09-18
新增 VirtualMachineDFA，采用虚拟机的思想，所以也可以把它叫做 Virtual Machine DFA，开始设计，慢慢来，可能需要很长一段时间才能完成。
2014-09-15
修复了 DenseDFA_V2 的一个bug
2014-09-14
删除了动态DFA匹配中遗留的的多线程代码，当时的测试表明，即使使用了 TBB 中的读写锁，在任何情况下，多线程都比单线程更慢，因为有太多的锁冲突。
2014-09-13
优化了动态DFA匹配中当 subset_size == 1 时的情况，此时直接转入静态 DFA 的状态空间，从而减少了内存用量，提高了匹配性能
2014-09-10
新增 DenseDFA_V2，这是 DenseDFA 的优化版，基本原理与DenseDFA相同，但是对 CPU Cache 更加友好，并且进行二进制匹配时更省内存，因为在内存对齐的情况下 Sigma=288，而此时DenseDFA.Sigma=320