自动机的威力

 

本文只关系到 有穷状态自动机 ,本文也不讲具体的算法,只讲一些基本概念,以及用本软件的自动机 能做什么怎么用

也有其他一些开源软件实现了本软件的部分功能,但总体上,不论是从功能还是性能(运行速度,内存用量)上考虑,到目前为止,我能找到的其它所有同类开源软件都完全无法与本软件竞争!欢迎大家一起交流!

自动机是什么

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

  • 自动机是一个可以自己运行的机器或机器人
  • 有穷状态自动机 (FSA)
    • 有限状态机(FSM)或有限状态自动机、或只是一个状态机,是用于设计计算机程序和时序逻辑电路的数学计算模型。
  • 确定性的有穷自动机 (DFA)
    • 这是本文的重点
  • 非确定性的有穷自动机 (NFA)
    • 很多 DFA 的构造需要 NFA 作为媒介
  • DFA 的最小化

    • DFA 的等同
      • 如果两个dfa的状态转移图同构,那么这两个 DFA 等同
    • DFA 的等价
      • 如果两个 DFA 能接受的语言集合相同,那么这两个 DFA 等价
      • 等价的 DFA 不一定等同
    • 最小化的 DFA
      • 对于任何一个 DFA,存在唯一一个与该 DFA 等价的 MinDFA,该 MinDFA 的状态数是与原 DFA 等价的所有 DFA 中状态数最小的
      • 最小化的 DFA 需要的内存更小
      • 各种优化的 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型语言(General的NFA和DFA是3型语言)。当然,有限,只是有限而已,但这个集合可能非常大,一个很小的ADFA也能表达非常大的字符串集合,用正则表达式举例: [a-z]{9} ,这个正则表达式对应的DFA包含10个状态,除终止状态外,其他每个状态都有26个转移(图的边),这个语言集合的大小是 269 = 5,429,503,678,976:从 aaaaaaaaa 一直到 zzzzzzzzz。想象一下,用 HashMap 或者 TreeMap,或者 DoubleArray Trie 来表达该集合的话,将是多么恐怖!

    编译

    目前,要编译 febird 中的自动机库,需要 C++11 编译器,推荐 gcc4.7 以上版本

    $ svn checkout http://febird.googlecode.com/svn/trunk/ febird-read-only
    $ cd febird-read-only
    $ make
    $
    $ cd tools/automata/
    $ make
    $ ll rls/*.exe # 后面会讲到详细用法
    -rwxrwxrwx 1 root root 27520456  8月 17 14:34 rls/adfa_build.exe*
    -rwxrwxrwx 1 root root 12265256  8月 17 14:34 rls/adfa_unzip.exe*
    -rwxrwxrwx 1 root root 16994384  8月 17 14:34 rls/dawg_build.exe*
    $
    $ cd netbeans-cygwin/automata/
    $ make
    $ ll rls/*/*.exe # 这两个 exe 用来测试自动机生成的 (key,val) 二进制数据文件
    -rwxrwxr-x 1 user user  9050159 2013-08-08 16:26 rls/forward_match/on_key_value.exe
    -rwxrwxr-x 1 user user  8994311 2013-08-08 16:26 rls/forward_match/on_suffix_of.exe

    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 是一个正则表达式!(目前还不支持)

    内存用量/查询性能

    本软件实现了两种 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

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

    自动机实用程序

    本软件包含几个程序,用来从文本文件生成自动机,生成的自动机可以用C++接口访问,这样,就将自动机的存储与业务逻辑完全分离。

    • adfa_build.exe options < input_text_file

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

    ||

    options arguments comments
    -o 输出文件:为 尺寸 优化的自动机 匹配速度较慢,尺寸较小,所以是小写o
    -O 输出文件:为 速度 优化的自动机 匹配速度很快,尺寸较大,所以是大写O
    -l 状态字节:为 尺寸 优化的自动机,可取值 4,5,6,7 自动机的每个状态占几个字节,越大的数字表示自动机能支持的最大状态数也越大,一般5就可以满足大多数需求了
    -b 状态字节:为 速度 优化的自动机,可取值 4,5,6,7
    -t 无参数 输出文本,仅用于测试
    -c 无参数 检查自动机正确性,仅用于测试
    • dawg_build.exe options < input_text_file

    生成扩展的 DFA,可以计算 key 的 index 号(字典序号),对应 map 的第一种实现方式(map1),使用方法同 adfa_build.exe ,输入文件的每行是一个 Key。

    • adfa_unzip.exe < dfa_binary_file

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

    • on_suffix_of.exe P1 P2 … < dfa_binary_file

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

    • on_key_value.exe 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 就不再是必需的了。

    #include <febird/automata/dfa_interface.hpp>

    automata/dfa_interface.hpp

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

    DFA_Interface

    这个类是最主要的 DFA 接口,对于应用程序,总是从 DFA_Interface::load_from(file) 加载一个自动机(adfa_build.exe 或 dawg_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的字典序。
      • 返回值是最长的 部分匹配 的长度,一般情况下没什么用处,可以忽略

    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 v_match_words(string, on_match[, tr])
      • 依次对 string 的所有前缀计算 index,并通过 on_match(prelen,nth) 回调返回计算结果,prelen是匹配的前缀长度,该函数也有可选的 tr 参数
      • 返回值是最长的 部分匹配 的长度,一般情况下没什么用处,可以忽略
    • size_t longest_prefix(string, size_t*len, size_t*nth[, tr])
      • 相当于 v_match_words 的特化版,只返回最长的那个 prefix
      • 返回值是最长的 部分匹配 的长度,一般情况下没什么用处,可以忽略

    API使用方法的示例程序

    对应于svn代码目录: febird-read-only/netbeans-cygwin/automata/samples

    超级功能

    以拼音输入法为例

    为了保证输入效率,我们需要有一个从 词条拼音词条汉字 的映射表,比如,拼音序列 ZiDongJi 对应的词条是 自动机自冻鸡 ;从而,逻辑上讲,这是一个 map<string,list<string> >

    假定我们有一个汉语词表,该词表的词条超过千万,每个词条可能是一句话(比如名言警句),并且,因为汉语中存在多音字,从而,包含多个多音字的词条都可能有很多种发音,这个数目在最坏情况下是指数级的,第一个字有 X1 个读音,第二个字有 X2 个读音,…,n 个字的词条就有 X1*X2*X3**Xn 种读音。另外,除了多音字,还有简拼,对于短词来说,简拼的重码率很高,不实用,但是对于长词/句,简拼的重码率就很低了。

    如果我们用 HashMap/std::unordered_map 或 TreeMap/std::map 保存这个注音词典,对于普通无多音字的词条,无任何问题。一旦有多音字, X1*X2*X3**Xn 可能是一个非常大的数字,几十,几百,几千,几千万都有可能,这完全是不可接受的!一个折衷的办法就是仅选择概率最大的拼音,但很可惜,有些情况下这个拼音可能是错的!

    用自动机解决该问题,最简单的方法就是用 string kv = X1*X2*X3**Xn + ‘\t’ + 汉字词条 来逐个插入,动态 MinADFA 算法可以保证内存用量不会组合爆炸,但是,除了内存,还有时间,如此逐个展开,时间复杂度也是指数的!

    这个问题我想了很久,终于有一天,想出了一个完美的解决办法:

    1. 在 MinADFA 中加入一个功能:在线性时间内,给一个唯一的前缀,追加一个 ADFA后缀
      • ADFA后缀 可以包含 X1*X2*X3**Xn 个 word,并且结构还可以任意复杂(最近我的研究发现,该后缀甚至不必是ADFA,可以包含环!)
      • 这个算法是整个问题的关键,余下的,就只是简单的技巧而已
    2. string kv = X1*X2*X3**Xn + ‘\t’ + 汉字词条 翻转
      • rev(X1*X2*X3**Xn) 构成一个 ADFA
      • rev(‘\t’+汉字词条) 是一个唯一前缀
    3. 将所有的词条做这样的处理,就构成一个 DFA({rev(拼音+’\t’+汉字)})
    4. 将该 DFA 翻转,得到 NFA(rev(DFA({rev(拼音+’\t’+汉字)})),再将该 NFA 转化成 DFA
    5. 查找时,使用 map2 的方法(DFA_Interface::match_key),因为组合爆炸,不能用 map1

    这个方法非常完美!虽然 NFA 转化 DFA 最差情况下是 NSpace(比NP还难) 的,但是在这里,可以证明,这个转化是线性的:O(n)。

     

    【本文转自: http://url.cn/HybFTp , 有删改增】

    自动机