把自动机用作 Key-Value 存储

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

这篇文档只关心 有穷状态自动机 ,不讲具体的算法,对自动机只讲一些基本概念。主要描述 怎样使用自动机工具创建 KV 数据库,怎样使用自动机 API 访问 KV 数据库……

也有其他一些开源软件实现了本软件的部分功能,但总体上,不论是从功能还是性能(运行速度,内存用量)上考虑,到目前为止,我能找到的其它所有同类开源软件都完全无法与本软件竞争,如果你知道更好的软件,请不吝告诉我(rockeet at 163.com)!

自动机的基本概念

关于自动机的形式化定义,可以参考 wikipedia:

  1. 自动机
  2. 有穷状态自动机 (FSA)
  3. 确定性的有穷自动机 (DFA):这是本文的重点
  4. 非确定性的有穷自动机 (NFA):很多 DFA 的构造需要 NFA 作为媒介

DFA 等同与等价

  1. DFA 的等同:如果两个DFA 的状态转移图同构,那么这两个 DFA 等同
  2. DFA 的等价:如果两个DFA 接受的语言集相同,那么这两个 DFA 等价(等价的不一定等同,等同的一定等价)

DFA 最小化

  1. 对于任何一个 DFA,存在一个唯一的与该 DFA 等价的 MinDFA,该 MinDFA 的状态数是与原 DFA 等价的所有 DFA 中状态数最小的
  2. 最小化的 DFA 需要的内存更小
  3. 各种优化的 DFA 最小化算法是本软件的核心竞争力之一

将 DFA 用做字典

什么是字典

字典,有时候也叫关联数组,可以认为就是一个 map<string, Value>,这是最简单直接的表达,在 C++ 标准库中,map是用 RBTree 实现的,当然,也可以用 hash_map(或称为 unordered_map)。这些字典在标准库中都有,不是特别追求cpu和内存效率的话,可以直接拿来时使用。

但是,要知道,对于一般应用,将字典文件(假定是文本文件)加载到 map/hash_map 之后,内存占用量要比字典文件大两三倍。当数据源很大时,是不可接受的,虽然在现在这年代,几G可能都算不上很大,但是,如果再乘以3,可能就是十几二十G了,姑且不论数据加载产生的载入延迟(可能得几十分钟甚至一两个小时)。

用 DFA 存储字典,在很多专门的领域中是一个标准做法,例如很多分词库都用 DoubleArray Trie DFA 存储词库,语音识别软件一般也用 DFA 来存储语音。

无环DFA (ADFA, Acyclic DFA)

用做字典的 DFA 是无环DFA (ADFA, Acyclic DFA),ADFA 的状态转移图是 DAG(有向无环图)。Trie 是一种最简单的 ADFA,同时也是(所有ADFA等价类中)最大的 ADFA。DoubleArray Trie 虽然广为人知,但相比 MinADFA,内存消耗要大得多。

ADFA 可接受的语言是有限集合,从乔姆斯基语言分类的角度,是4型语言(广义的NFA和DFA是3型语言)。当然,有限,只是有限而已,但这个集合可能非常大,一个很小的ADFA也能表达非常大的字符串集合,用正则表达式举例: [a-z]{9} ,这个正则表达式对应的DFA包含10个状态,除终止状态外,其他每个状态都有26个转移(图的边),这个语言集合的大小是 269 = 5,429,503,678,976:从 aaaaaaaaa 一直到 zzzzzzzzz。想象一下,用 HashMap 或者 TreeMap,或者 DoubleArray Trie 来表达该集合的话,将是多么恐怖!

编译 (目前 febird 自动机库已闭源, 并改名为 nark)

map 与 set

传统上,ADFA 只能用作 set<Key> ,也就是字符串的集合。但是,本软件可以把 ADFA 用作 map<Key, Value>,通过两种方式可以达到这个目标:

  • map1: 扩展 ADFA(从而 DFA 的尺寸会大一点),查找 key 时,同时计算出一个整数 index,该 index 取值范围是 [0, n),n 是 map.size()。从而,应用程序可以在外部存储一个大小为 n 的数组,用该 index 去数组直接访问 value。
    • 本软件中有一个 utility 类用来简化这个流程
    • 本质上,这种方法无法动态插入 (key,val);但可以追加 (key,val),追加的意思是说,前一个加入的 key,按字典序必须小于后一个加入的 key
  • map2: 将 Value 编码成 string 形式,然后再生成一个新的 string kv = key + '\t' + value,将 kv 加入 ADFA,在这种情况下,同一个 key 可以有多个 value,相当于 std::multimap<string, Value>,这种方法的妙处在于,如果多个key对应的value相同,这些value就被自动机压缩成一份了!
    • 这种方法可以动态插入、删除 (key,val),不过,要支持动态插入、删除功能,需要大约4~5倍的额外内存
    • 更进一步,这种方法可以扩展到允许 key 是一个正则表达式!(目前 febird 已经完美支持正则表达式

内存用量/查询性能

本软件实现了两种 DFA,一种为运行速度优化,另一种为内存用量优化,前者一般比后者快4~6倍,后者一般比前者节省内存30~40%,具体使用哪一种,由使用者做权衡决策。

不同的数据,DFA有不同的压缩率。 对于典型的应用,为内存优化的DFA,压缩率一般在3倍到20之间,相比RBTree/HashMap的膨胀3倍,内存节省就有9倍到60倍!同时仍然可以保持极高的查询速度(keylen=16字节,QPS 在 40万到60万之间),为速度优化的版本,QPS 有 250万。下面是几个性能数据(map指map1,为了对齐,在一些数字前面补了0):

size(bytes) gzip DFA(small+slow) DFA(big+fast) KeyLen QPS(big+fast) DFA Build time
File1(Query) 226,433,393 96,293,588 map:101,125,415
set:073,122,182
170,139,298 016.7 24,000,000 47’seconds
File2(URL) 485,968,345 25,094,568 map:13,990,737
set:10,850,052
035,548,376 109.2 00,900,000 16’seconds

URL文件的冗余比较大,虽然文件尺寸大一倍多,但最终的dfa文件却要小得多,创建dfa用的时间也少得多!dfa文件的加载速度非常快,相当于整个文件读取,如果文件已在缓冲区,则相当于memcpy (使用 -m 选项,加载时会 mmap,就连这个 memcpy 也省了)。

警告: 如果key中包含有随机串,例如 guid、md5 等,会大大增加自动机的内存用量!不要自作聪明把自然的串转化成 md5 等 hash 串再插入自动机!

自动机实用程序

本软件包含几个程序,用来从文本文件生成自动机,生成的自动机可以用C++接口访问,这样,就将自动机的存储与业务逻辑完全分离。另外,还有一个 adfa_unzip,用来将各种自动机当做压缩文件进行解压。adfa_build 有最多的自动机类型选项,其他创建程序一般只有 -O 和 -o。

  • adfa_build  Options  [ input_text_file ]
    输入文件的格式一般是: key \t value, \t 是 key, value 的分隔符,\t 也可以是其它字符,只要该分隔符不在 key 中出现即可,value 中则可以包含分隔符。该程序本质上不管每行的的内容是什么,只是忠实地将每行文本加入自动机。分隔符的作用体现在后面将要提到的 api: DFA_Interface::match_key 中。

    选项 参数 注解与说明
    -o(小写) 输出文件:为尺寸优化的自动机 匹配速度较慢,尺寸较小,所以是小写o,以后这种自动机可能会使用 -U 指定的那种
    -O(大写) 输出文件:为速度优化的自动机 匹配速度很快,尺寸较大,所以是大写O
    -S(大写) 输出一种小又快的自动机(Small Fast) 尺寸与 -o 的相当,速度与 -O 的相当
    这是我2014年4月新发明的一种DFA表示方法
    -U(大写) 尺寸最小的一种自动机(Ultra Small) 一般比 -S 的要小 30~40%,但是慢 6 倍左右
    这是我2014年6月新发明的一种DFA表示方法,使用Rank-Select数据结构
    -s(小写) 无参数 告诉创建程序,输入是按字典序排好的,创建程序因此会使用更高效的算法,会大幅提高创建速度并减小创建过程中的内存用量,对创建出来的自动机无任何影响(与不带 -s 的完全相同)
    -q 无参数 静默模式,不打印进度信息

    如果命令行上未指定 input_text_file , 使用 stdin。
    文件格式一般是每行用 Key  \t  Value 表示的一条数据,可以有 Key 相同的多条数据,(Key, Value) 完全相同的行会被去重。

  • kvbin_build  options [ input_key_val_binary_data ]
    • 这个功能是最近(r1303)新加的, 因为 adfa_build 不能用于二进制数据
      • 之前版本的 DFA 有局限性,其 match_key 接口至少需要从 byte 的值域范围 [0,256) 中去掉一个做为 (key, val) 的分隔符,因此,不能用作二进制 key 的存储(虽然通过约定编码方式也可以去除这个限制,但这不是根本解决之道)
      • 最近我对自动机库做了一个大的改进(r1303),去除了这个限制,具体的原因不是表面看上去那么简单,以后会另外开篇说明。
    • options 参数同 adfa_build
    • 输入文件也使用 -i 参数或 stdin ,但数据格式不同,input_key_val_binary_data 的格式是非常简单的流数据:
      uint32 key_len uint32 val_len bytes key_data bytes val_data
    • kvbin_build.exe 不停地从输入文件中读这样的 (key,val) 数据,同时 onfly 创建自动机,直到文件末尾
  • dawg_build  options  [ input_text_file ]

生成扩展的 DFA,可以计算 key 的 index 号(字典序号),对应 map 的第一种实现方式(map1),使用方法同 adfa_build,输入文件的每行是一个 Key。 理论上讲,dawg不需要 kvbin_build 那种自动机的新能力就可以完美支持二进制数据作为key。

  • adfa_unzip [ dfa_binary_file ]

解压 dfa_binary_file,按字典序将创建自动计时的输入文件 input_text_file 的每行写到标准输出 stdout ,可以接受基本 dfa(由 adfa_build.exe 生成的)文件 和扩展dfa(由 dawg_build.exe 生成的)文件

  • on_suffix_of  P1 P2 … [ < dfa_binary_file ]

打印所有前缀为 Pn 的行 (adfa_build.exe 或 dawg_build.exe 输入文本的行) 的后缀

  • on_key_value  text1 text2 …  [ < dfa_binary_file ]

打印匹配所有 textn 的前缀的 Key (adfa_build.exe 或 dawg_build.exe 输入文本的行) 的 value, 用于测试 map 实现方法2 (Key Value 之间加分隔符)

自动机的 C++接口

本软件使用了 C++11 中的新特性,所以必须使用支持 C++11 的编译器,目前测试过的编译器有 gcc4.7 和 clang3.1。不过为了兼容,我提供了C++98 的接口,一旦编译出了静态库/动态库,C++11 就不再是必需的了。

头文件 febird/automata/dfa_interface.hpp 中主要包含以下 class:

DFA_Interface

这个类是最主要的 DFA 接口,对于应用程序,总是从 DFA_Interface::load_from(file) 加载一个自动机(adfa_build.exe 或 dawg_build.exe 或 regex_build.exe 生成的自动机文件),然后调用各种查找方法/成员函数。

  • size_t for_each_suffix(prefix, on_suffix[, tr])
    • 该方法接受一个字符串prefix,如果prefix是自动机中某些字符串的前缀,则通过 on_suffix(nth,suffix) 回调,告诉应用程序,前缀是prefix的那些字符串的后缀(去除prefix之后的剩余部分),nth 是后缀集合中字符串的字典序。 tr 是一个可选参数,用来转换字符,例如全部转小写,将 ::tolower 传作 tr 即可
    • 例如:对字符串集合 {com,comp,comparable,comparation,compare,compile,compiler,computer}, prefix=com 能匹配所有字符串(其中nth=0的后缀是空串),prefix=comp能匹配除com之外的所有其它字符串,此时nth=0的也是空串,而 compare 的后缀 are 对应的 nth=1
    • 返回值是后缀集合的尺寸,一般情况下没什么用处,可以忽略
  • size_t match_key(delim,str,on_match[, tr])
    • 该方法用于实现 map2,delim 是 key,val 之间的分隔符(如 ‘\t’ ),key中不可包含delimstr 是扫描的文本,如果在扫描过程中,发现 str 的长度为 Kn 的前缀 P 匹配某个 key,就将该 key 对应的所有 value 通过 on_match(Kn,idx, value) 回调告诉调用方, idx是同一个key对应的value集合中当前value的字典序。
    • 如果自动机是用 kvbin_build.exe 创建出来的,delim 参数可以省略,或者将 256 作为 delim 传入
    • 返回值是最长的 部分匹配 的长度,一般情况下没什么用处,可以忽略

DAWG_Interface

这个类用来实现 map1,DAWG 的全称是 Directed Acyclic Word Graph,可以在 ADFA 的基础上,在匹配的同时,计算一个字符串在 ADFA 中的字典序号(如果存在的话),同时,也可以从字典序号计算出相应的字符串,时间复杂度都是O(strlen(word))。

  • size_t index(string word)
    • 返回 word 的字典序,如果不存在,返回 size_t(-1)
  • string nth_word(size_t nth)
    • 从字典序 nth 计算对应的 word,如果 nth 在 [0, n) 之内,一定能得到相应的 word,如果 nth 不在 [0, n) 之内,会抛出异常
  • size_t match_dawg(string, on_match[, tr])
    • 依次对 string 的所有前缀计算 index,并通过 on_match(prelen,nth) 回调返回计算结果,prelen是匹配的前缀长度,该函数也有可选的 tr 参数
    • 返回值是最长的 部分匹配 的长度,一般情况下没什么用处,可以忽略
  • size_t match_dawg_l(string, size_t*len, size_t*nth[, tr])
    • 相当于 match_dawg 的特化版,只返回最长的那个匹配
    • 返回值是最长的 部分匹配 的长度,一般情况下没什么用处,可以忽略

API使用方法的示例程序

febird-xxx 系列开源软件改名 为 nark-xxx,自动机虽然仍不开源,但示例程序开源:https://github.com/rockeet/nark-fsa-intro/tree/master/samples

当 Value 是复杂数据结构时 (nark-fsa 已经实现了另外一种压缩算法,就不再需要本节描述的技巧了)

假定有这样一个需求:每个 key 对应的 value 是个结构体,结构体中又包含多个字符串的数组/集合,例如:

原本的文本文件可能是这样:

把它变成这样:

然后使用 adfa_build.exe 创建相应的 DFA 文件,在程序中用 load_from 加载,就可以用 match_key 来搜索了,并且还是前缀搜索,不象 HashMap 那样只能精确搜索(使用一定技巧 TreeMap 也可以前缀搜索,不过要慢一些)。在 match_key 的 on_match 回调中,从 value 中分别拿出字段名和字段内容,然后就可以做想做的事情了。

说明:

  • 因为公共前缀可以压缩,公共后缀也可以压缩,中间部分也可以压缩,但压缩中间部分要求的条件比较苛刻,所以还是尽量把最可能相同的部分作为前缀或后缀
    • 对于 vec1 字段,将 字段名:下标 放在 前面 ,是为了让每个 vector 的元素都相邻
    • 对于 vec2 字段,将 字段名:下标 放在 后面 ,是为了尽可能压缩相同部分,减少内存用量
    • set 字段不需要下标,只需要列举所有元素即可
  • 如果 key 比较长, vector/set 字段的元素是一些简单数据(如数字的字符串形式),但元素数目很多,将 key 重复很多次可能会导致adfa_build.exe 创建 DFA 太慢。但其实该库中有相应的算法来快速创建这样的自动机,tool 中有一个 multi_col_db_build.exe 可以创建比较简单的 复杂Value ,对于具体的应用,可能需要专门写相应的创建程序。

超级功能

以拼音输入法为例

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

作者:
该日志由 csdn-whinah 于2013年08月15日发表在自动机分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 把自动机用作 Key-Value 存储
标签: ,
【上一篇】
【下一篇】

您可能感兴趣的文章:

5 个回复

  1. suannai0314说道:

    您的文章已被推荐到CSDN首页,感谢您的分享。

  2. Atry说道:

    麻烦请问博主这些知识是怎么学到的?有没有关于DFA理论的书可以推荐一下?

  3. Atry说道:

    更进一步,这种方法可以扩展到允许 key 是一个正则表达式!(目前 febird 已经完美支持正则表达式)
    如果支持正则表达式,肯定就会有环,就不能算是ADFA了吧?

  4. […] 我之前有一篇文章介绍 把自动机用作 Key-Value 存储 ,使用里面的方法,具体到该问题,就是: 用 string kv = X1*X2*X3*…*Xn + ‘t’ + 汉字词条 来逐个插入,动态 MinADFA 算法可以保证内存用量不会组合爆炸,但是,除了内存,还有时间,如此逐个展开,时间复杂度也是指数的! […]

发表评论

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