DoubleArrayTrie和AhoCorasickDoubleArrayTrie的实用性对比

前段时间开源了基于双数组Trie树的Aho Corasick自动机，当时认为在中文分词中，ACDAT应该能秒杀DAT。今天优化了DAT的多模式匹配后，竟然得出了意外的结果。

当初的DAT实现中，为了支持多模式匹配，我写了一个Searcher结构，里面储存了当前扫描的起点，并且用一个链表储存了从当前起点开始途经的所有词串。接着只要不断地将起点往后挪一个，就支持了多模式匹配。也就是这个“挪一个单位”的动作，让我认为DAT在多模式匹配上，复杂度更高（应该是O(n²)，n是母文本的长度）。要知道，理论上AC自动机是线性复杂度的。

试验

然而今天优化了DAT的Searcher，去掉了链表这个临时存储结构，进行了这么一个实验：

// 加载词典
TreeMap<String, String> map = new TreeMap<>();
for (Map.Entry<String, Item> entry : DictionaryMaker.load(HanLP.Config.CoreDictionaryPath).entrySet())
{
    map.put(entry.getKey(), entry.getKey());
}
// 加载母文本
String text = IOUtil.readTxt("《我的团长我的团》.txt");
final char charArray[] = text.toCharArray();
long start;
// 构建ACDAT
AhoCorasickDoubleArrayTrie<String> acdat = new AhoCorasickDoubleArrayTrie<>();
acdat.build(map);
// 构建DAT
DoubleArrayTrie<String> dat = new DoubleArrayTrie<>();
dat.build(map);
System.gc();

// ACDAT测速
start = System.currentTimeMillis();
acdat.parseText(charArray, new AhoCorasickDoubleArrayTrie.IHit<String>()
{
    @Override
    public void hit(int begin, int end, String value)
    {

    }
});
System.out.println("ACDAT: " + (System.currentTimeMillis() - start));

DoubleArrayTrie<String>.Searcher searcher = dat.getSearcher(charArray, 0);
System.gc();

// DAT测速
start = System.currentTimeMillis();
while (searcher.next())
{
}
System.out.println("DAT: " + (System.currentTimeMillis() - start));

// ACDAT和DAT等效性检测
final TreeSet<String>[] wordNet = new TreeSet[charArray.length];
acdat.parseText(charArray, new AhoCorasickDoubleArrayTrie.IHit<String>()
{
    @Override
    public void hit(int begin, int end, String value)
    {
        if (wordNet[begin] == null) wordNet[begin] = new TreeSet<>();
        wordNet[begin].add(new String(charArray, begin, end - begin));
    }
});
searcher = dat.getSearcher(charArray, 0);
while (searcher.next())
{
    String word = new String(charArray, searcher.begin, searcher.length);
    assertEquals(true, wordNet[searcher.begin].contains(word));
    wordNet[searcher.begin].remove(word);
}

for (TreeSet<String> treeSet : wordNet)
{
    if (treeSet == null) continue;
    assertEquals(0, treeSet.size());
}

首先初始化了一个中文词库，词典大小为85611个词条。然后以一部长度为1290573字的中文小说作为母文本，分别用这两个数据结构跑多模式匹配。最后将两者的结果作对比，检验是否不重不漏。

结果

输出结果是：

ACDAT: 88
DAT: 37

DAT竟然只花了一半的时间，37毫秒！

接着我将词典换成35万的大辞典，得到如下结果：

ACDAT: 104
DAT: 40

这下差距更大了！

原因

我认为这是由于汉语的特殊性造成的，在汉语中，几乎每一个字都可以当做一个词使用，几乎每一个长词都是由几个短词复合而成的。

语言上的现象是如何影响程序性能的呢？

在处理汉语母文本时，以母文本的每个字做起点，几乎都可以匹配到前缀相同的词语（很多时候该词语就是一个字）。既然每次几乎都可以成功转移状态，这就导致AC自动机的fail表派不上用场。AC自动机又要花常数时间在output表的循环上，长处用不上，短处拖后腿，英雄无用武之地啊！

另一方面，DAT每次挪位置几乎都能匹配到前缀串，它又没有output表的负担，于是常数复杂度低，实际效果要好。

结论

这导致中文分词天然适合DAT，从内存的角度来讲也是如此，DAT的内存占用也是ACDAT的一半。

但是这并不代表ACDAT一点用处都没有，假如某种语言跟中文是相反的情况：单个字母无法成词，又或者某种模式串的前缀相同的情况特别少，那么此时毫无疑问应该选择ACDAT。比如说，我们要将一段文本中的某些停用词替换为*号。文本可能很长，相对正常词语来讲，停用词非常少，那么这时候ACDAT的速度将比DAT快很多。

理论终究是理论，具体问题具体分析，一切以实践为准。

 知识共享署名-非商业性使用-相同方式共享：码农场 » DoubleArrayTrie和AhoCorasickDoubleArrayTrie的实用性对比