Aho Corasick自动机结合DoubleArrayTrie极速多模式匹配
本文使用Double Array Trie实现了一个性能极高的Aho Corasick自动机,应用于分词可以取得1400万字每秒,约合27MB/s的分词速度。其中词典为150万词,构建耗时1801 ms。以前就在构想将AC自动机与双数组Trie树结合起来(注:后来发现这就是1989年Aoe, J. I.提出双数组的初衷),考虑到持久化比较困难(goto和fail表是内存指针/引用),一直没下决心实现,今天终于成功了。
AC自动机能高速完成多模式匹配,然而具体实现聪明与否决定最终性能高低。大部分实现都是一个Map<Character, State>了事,无论是TreeMap的对数复杂度,还是HashMap的巨额空间复杂度与哈希函数的性能消耗,都会降低整体性能。
双数组Trie树能高速O(n)完成单串匹配,并且内存消耗可控,然而软肋在于多模式匹配,如果要匹配多个模式串,必须先实现前缀查询,然后频繁截取文本后缀才可多匹配,这样一份文本要回退扫描多遍,性能极低。
如果能用双数组Trie树表达AC自动机,就能集合两者的优点,得到一种近乎完美的数据结构。在我的Java实现中,我称其为AhoCorasickDoubleArrayTrie,支持泛型和持久化,自己非常喜爱。
惠施在梁国当宰相,庄子去看望他。有的人对惠施说:“庄子到梁国来,想取代你做宰相。”于是惠施非常害怕,在国都中搜捕(庄子)三天三夜。庄子前去见他,说:“南方有一种鸟,它的名字叫鹓雏,你知道它吗 ? 鹓雏鸟从南海起飞,飞到北海去,不是梧桐树不栖息,不是竹子的果实不吃,不是甜美的泉水不喝。在这时,一只猫头鹰得到一只腐臭的老鼠,鹓雏从它面前飞过,猫头鹰仰头看着鹓雏鸟,发出 ‘ 吓 ’ 的怒斥声。而你是以为我想要你梁国宰相的官位所以来恐吓我吗?”
——转自《庄子·秋水篇》,百度百科译文。
原理
预备知识的图解请参考:《Aho-Corasick算法的Java实现与分析》《双数组Trie树(DoubleArrayTrie)Java实现》,请不要在不懂任何一个原理的情况下继续阅读。
基本原理是为一颗双数组Trie树的每个状态(体现为下标)附上额外的信息。在《Aho-Corasick算法的Java实现与分析》我曾经提到过,AC自动机的基础(success表)就是Trie树,只不过比Trie树多了output表和fail表。那么AhoCorasickDoubleArrayTrie的构建原理就是为每个状态(base[i]和check[i])构建output[i][]和fail[i]。
构建
双数组Trie树的构建是一个先序dfs,AC自动机的构建是一个先序bfs。如果同时构建或者先构建AC自动机,那么AC自动机的每个状态将无法对应到双数组Trie树的状态;另一方面,同步构建会导致代码不可控。
所以我的实现中采取了三步构建法——
构建trie树
即将所有模式串构建为一颗字典树,同时将终止状态绑定外部value。在实现上可以先用TreeMap简单实现。
构建双数组Trie树
有了trie树,将其压缩到两个数组上非常简单。有一些实现已经做得非常不错了,比如前面介绍的《双数组Trie树(DoubleArrayTrie)Java实现》。
与单独构建双数组Trie树不同,在为一个trie树State创建base[i]的时候,让该State记住自己的i,这样就建立State和下标的映射。
构建AC自动机
在构建AC自动机时,每构建一个节点State的fail表,就利用上述映射下标State.id将fail[id]设为failState.id。对于output表,也是同理。
其实构建完全可以离线进行,并不要求苛刻的速度。
查询
精确单模式匹配
AhoCorasickDoubleArrayTrie本质上是一颗双数组Trie树,所以它也像双数组Trie树一样支持精确单模式匹配,具体过程依然与《双数组Trie树(DoubleArrayTrie)Java实现》相同。
前缀查询
同上
多模式匹配
在《Aho-Corasick算法的Java实现与分析》中,每次转移返回的都是一个State引用,但是这次将其改为返回id,利用下标id,既可以按照success表(双数组base和check)转移,转移失败时也可以按照fail[id]退回到合适的位置。
具体实现
本文代码已集成到HanLP中开源:http://www.hankcs.com/nlp/hanlp.html
另外,单独的AhoCorasickDoubleArrayTrie类库也已经开源:https://github.com/hankcs/AhoCorasickDoubleArrayTrie
接口
返回所有匹配到的模式串
- /**
- * 匹配母文本
- *
- * @param text 一些文本
- * @return 一个pair列表
- */
- public List<Hit<V>> parseText(String text)
其中Hit是一个表示命中结果的结构:
- /**
- * 一个命中结果
- *
- * @param <V>
- */
- public class Hit<V>
- {
- /**
- * 模式串在母文本中的起始位置
- */
- public final int begin;
- /**
- * 模式串在母文本中的终止位置
- */
- public final int end;
- /**
- * 模式串对应的值
- */
- public final V value;
- }
即时处理接口
很明显,返回一个巨大的List并不是个好主意,AhoCorasickDoubleArrayTrie提供即时处理的结构:
- /**
- * 处理文本
- *
- * @param text 文本
- * @param processor 处理器
- */
- public void parseText(String text, IHit<V> processor)
其中IHit<V>是一个轻便的接口:
- /**
- * 命中一个模式串的处理方法
- */
- public interface IHit<V>
- {
- /**
- * 命中一个模式串
- *
- * @param begin 模式串在母文本中的起始位置
- * @param end 模式串在母文本中的终止位置
- * @param value 模式串对应的值
- */
- void hit(int begin, int end, V value);
- }
调用方法
- TreeMap<String, String> map = new TreeMap<>();
- String[] keyArray = new String[]
- {
- "hers",
- "his",
- "she",
- "he"
- };
- for (String key : keyArray)
- {
- map.put(key, key);
- }
- AhoCorasickDoubleArrayTrie<String> act = new AhoCorasickDoubleArrayTrie<>();
- act.build(map);
- act.parseText("uhers", new AhoCorasickDoubleArrayTrie.IHit<String>()
- {
- @Override
- public void hit(int begin, int end, String value)
- {
- System.out.printf("[%d:%d]=%s\n", begin, end, value);
- }
- });
- // 或者System.out.println(act.parseText("uhers"));
输出
一些调试输出:
- output:
- 107 : [0]
- 118 : [1]
- 120 : [2]
- 123 : [3, 0]
- fail:
- 1 : 1
- 118 : 117
- 120 : 117
- 122 : 106
- 123 : 107
- DoubleArrayTrie:
- char = × h e × i s s × s × h e ×
- i = 0 106 107 108 111 117 118 119 120 121 122 123 124
- base = 1 5 108 -1 4 17 119 -2 121 -3 21 124 -4
- check= 0 1 5 108 5 1 2 119 4 121 17 21 124
分词
将AhoCorasickDoubleArrayTrie应用于分词简直是物尽其用,HanLP中的核心词典已经替换为由AhoCorasickDoubleArrayTrie提供支持:
- CoreDictionaryACDAT.trie.parseText(charArray, new AhoCorasickDoubleArrayTrie.IHit<CoreDictionary.Attribute>()
- {
- @Override
- public void hit(int begin, int end, CoreDictionary.Attribute value)
- {
- wordNetStorage.add(begin + 1, new Vertex(new String(charArray, begin, end - begin), value));
- }
- });
另外,HanLP中还实现了一个基于AhoCorasickDoubleArrayTrie的最长分词器:
- public void testACSegment() throws Exception
- {
- Segment segment = new AhoCorasickSegment();
- segment.enablePartOfSpeechTagging(true);
- System.out.println(segment.seg("江西鄱阳湖干枯,中国最大淡水湖变成大草原"));
- }
输出:
- [江西/ns, 鄱阳湖/ns, 干枯/vi, ,/nz, 中国/ns, 最大/gm, 淡水湖/n, 变成/v, 大草原/nz]
就是这个最长分词器,得到了前文逆天的分词速度!
- public static void main(String[] args)
- {
- String text = "江西鄱阳湖干枯,中国最大淡水湖变成大草原";
- System.out.println(SpeedTokenizer.segment(text));
- long start = System.currentTimeMillis();
- int pressure = 1000000;
- for (int i = 0; i < pressure; ++i)
- {
- SpeedTokenizer.segment(text);
- }
- double costTime = (System.currentTimeMillis() - start) / (double)1000;
- System.out.printf("分词速度:%.2f字每秒", text.length() * pressure / costTime);
- }
输出:
- [江西/null, 鄱阳湖/null, 干枯/null, ,/null, 中国/null, 最大/null, 淡水湖/null, 变成/null, 大草原/null]
- 分词速度:14164305.95字每秒
真实应用环境中,在132 ms内分完了整本《我的团长我的团》.txt,共774165字,速度是5864886.36 字/秒!
在后续试验中,我发现AC-DAT在中文上的表现不如DAT,于是又将HanLP的字符串算法改回了DAT。详见《DoubleArrayTrie和AhoCorasickDoubleArrayTrie的实用性对比》。
反馈
技术问题请在Github上发issue ,大家一起讨论,也方便集中管理。博客留言、微博私信、邮件不受理任何开源项目相关的问题,谢谢合作!
反馈问题的时候请一定附上版本号、触发代码、输入输出,否则无法处理。
References
Aoe, J. I. (1989). An efficient implementation of static string pattern matching machines. IEEE Transactions on Software Engineering, 15(8), 1010-1016.
https://github.com/hankcs/AhoCorasickDoubleArrayTrie
https://github.com/hiroshi-manabe/darts-clone-java
知识共享署名-非商业性使用-相同方式共享:码农场 » Aho Corasick自动机结合DoubleArrayTrie极速多模式匹配