放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

DoubleArrayTrie和AhoCorasickDoubleArrayTrie的实用性对比

目录

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

当初的DAT实现中,为了支持多模式匹配,我写了一个Searcher结构,里面储存了当前扫描的起点,并且用一个链表储存了从当前起点开始途经的所有词串。接着只要不断地将起点往后挪一个,就支持了多模式匹配。也就是这个“挪一个单位”的动作,让我认为DAT在多模式匹配上,复杂度更高(应该是O(n2),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的实用性对比

评论 9

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #5

    有个疑问哈,关于DAT 多模式匹配的复杂度。凭感觉应该是O(n*L),L是字典里最长词条的长度。每次挪一位,匹配到一个最长前缀(≤L),再挪循。 说的不对不要喷我哈。

    lcybo6年前 (2018-07-07)回复
  2. #4

    能看看你设计的DAT用于多模匹配的代码么

    北疆凌宫8年前 (2016-05-25)回复
  3. #3

    棒棒哒!

    陈洞天8年前 (2016-02-05)回复
  4. #2

    在使用的过程中发现一处bug,在二分法查找时有时会数组越界。 int index = binarySearch(pair, start[idA], start[idA + 1] – start[idA], idB);

    嘿嘿9年前 (2015-06-17)回复
    • 我从没遇到过,也没接到issue,请举个bad case

      hankcs9年前 (2015-06-28)回复
    • 目前CoreNatureDictionary.ngram.txt的缓存依赖于CoreNatureDictionary.txt的缓存,有可能你往CoreNatureDictionary.txt里面加了词条,ngram的缓存没更新。没关系,请clone最新代码,我已经做了自动校验处理。

      hankcs9年前 (2015-07-01)回复
      • 没看邮件,不好意思没有回复你,原因就像你说的那样,楼主棒棒哒!

        嘿嘿9年前 (2015-07-06)回复
  5. #1

    hankcs有指代消解的计划吗?

    itdev9年前 (2015-04-30)回复
    • 这个得看我今年学校申到了什么方向 [嘻嘻]

      hankcs9年前 (2015-04-30)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》