Aho Corasick自动机结合DoubleArrayTrie极速多模式匹配

Aho Corasick 自动机结合 DoubleArrayTrie 极速多模式匹配

摘要

本文使用Double Array Trie实现了一个性能极高的Aho Corasick自动机，应用于分词可以取得1400万字每秒，约合27MB/s的分词速度。其中词典为150万词，构建耗时1801 ms。以前就在构想将AC自动机与双数组Trie树结合起来（注：后来发现这就是1989年Aoe, J. I.提出双数组的初衷），考虑到持久化比