这篇文档只关心 有穷状态自动机 ，不讲具体的算法，对自动机只讲一些基本概念。主要描述 怎样使用自动机工具创建 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个转移(图的边)，这个语言集合的大小是 26⁹ = 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  P₁ P₂ … [ < dfa_binary_file ]

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

• on_key_value  text₁ text₂ …  [ < dfa_binary_file ]

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

• pinyin_build

自动机的 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中不可包含delim，str 是扫描的文本，如果在扫描过程中，发现 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 ，对于具体的应用，可能需要专门写相应的创建程序。

超级功能

以拼音输入法为例