更新记录

我们已使用 terark.com 进行商业化运营

2014-12-29 ~ 2015-01-21

  1. 增加 NestLoudsTrie
  2. 增加 NestPatriciaTrie,基于NestLoudsTrie
  3. 使用 NestLoudsTrie 优化 LoudsDFA
  4. 新增了 tool/fsa/rptrie_build, 用于创建 NestPatriciaTrie
  5. 完善了各种 DFA 创建工具的 help/usage 信息

对于“自然”的数据集,NestPatriciaTrie 在很多时候比 LoudsDFA 压缩率更高一点,查询速度也不慢。并且,NestPatriciaTrie 也实现了 DFA_Interface 接口。NestPatriciaTrie还有一个附加功能:可以把字符串映射到一个整数ID,不过,对基于LoudsNestPatriciaTrie,这个ID不是字典序号,而是 (字符串长度 + 字符串内容) 序号,只有当集合中的所有字符串都等长时,才和字典序等价。

对于有组合性质的数据集,LoudsDFA 压缩率比NestPatriciaTrie要高得多,同时,LoudsDFA 也可以使用NestLoudsTrie 进一步压缩,首页上的拼音纠错演示程序使用NestLoudsTrie 优化之后,其 DFA 数据库尺寸从 362M 降到293M,减小了 20%该 DFA 就对应一个高度组合重复的数据集。

2014-12-24

  1. 优化 Base AC 自动机匹配代码,性能提高了大约 30%,2000 个 pattern 匹配速度达到 720MB 每秒(cpu: i7-4790)。
  2. 实现了 FullDFA 和 AC_FullDFA,无 nil 转移,内存用量很大(Base AC 的 10 倍以上);虽然理论上 AC_FullDFA 对每个字符的最坏匹配时间都是O(1),但综合性能(167MB 每秒)还是比 Base AC 要慢很多

2014-12-11

  1. Windows版的 regex_build: 使用 https://github.com/google/re2,再做了一些修改,最终在 Visual C++ 2013 中编译通过。
  2. 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 中的一些模块开源,不过自动机在可预期的将来仍不会开源。开源的模块包括:

  1. https://github.com/rockeet/nark-bone
  2. https://github.com/rockeet/nark-serialization
  3. https://github.com/rockeet/nark-rpc
  4. https://github.com/rockeet/nark-hashmap
  5. https://github.com/rockeet/nark-cstl
  6. 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

我们已使用 terark.com 进行商业化运营

发表评论

您必须 登录 后才能发表评论。