放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理。另外,不要叫我楼主,谢谢。

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

目录

本文使用Double Array Trie实现了一个性能极高的Aho Corasick自动机,应用于分词可以取得1400万字每秒,约合27MB/s的分词速度。其中词典为150万词,构建耗时1801 ms。以前就在构想将AC自动机与双数组Trie树结合起来,考虑到持久化比较困难(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"));

输出

[1:3]=he
[1:5]=hers

一些调试输出:

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 字/秒!

转载须注明:码农场 » Aho Corasick自动机结合DoubleArrayTrie极速多模式匹配

分享到:更多 ()
  1. 刚才在看博主你推荐的这篇文章。突然想到博主,我留言的话,你可否看到我的邮箱,那个……你可以把你的邮箱给我吗?我想和你保持联系可以吗?

  2. Pingback: HanLP开源 | HundredLee's Blog

  3. 博主您好,可否提供一个对已有词典的动态调整的实现?比如在已有词典的基础上,插入某些词、删除某些词等。
    因为如果每次词典有变动,需要重新构建词典,所用的时间还是比较长的。非常期待~~~

  4. 博主,为什么AhoCorasickDoubleArrayTrie在build的时候耗时很长啊?我加载一个500k的词典用了5s。然后我移植的android上,加载这个词典竟然用了30s~50s,这是什么原因?

  5. 博主,最近在看你的AC自动机的源码,感觉学到了很多东西,非常感谢,其中有几个地方不太明白,想请教一下一下
    1.State类中的getLargestValueId为什么要选择最大的emits值呢。emit在构造fail表之前不都是只有一个值吗?
    public Integer getLargestValueId()
    {
    if (emits == null || emits.size() == 0) return null;
    return emits.iterator().next();
    }
    2.constructFailureStates 这个构造fail表的方法中 fail[1] = base[0]; 这句话何解呢 状态1的fail指针怎么指向base[0]去了

    如果有时间,忘不吝赐教

  6. 1、只是为了挑一个值而已,挑谁都可以,甚至统一返回1或随机数都没关系。在双数组trie树中,利用这个值作为输出value的下标,但是AC自动机中该功能由output表实现。之所以返回最大值,是为了兼容双数组trie树,使得这棵ACDAT可以当成DAT使用,参考com.hankcs.algorithm.AhoCorasickDoubleArrayTrie#get(java.lang.String)
    2、我不记得当初为什么要这么写,现在看来,这似乎没有用。没有任何状态的index可能成为1:
    int b = base[nodePos];
    int p;

    p = b + c + 1;

    所以最小是2。

  7. 哦哦 明白了,第一个那个最大值的叶节点在AC中是没用的,只是在DAT中凑数的对吧。还有第二个,我把那句代码注掉试试,非常感谢[给力][给力]

  8. Pingback: LDA入门与Java实现-大数据控

  9. Pingback: LDA入门与Java实现 – 移乐柠科技博客

  10. Pingback: 汉语言处理包 中文分词 词性标注 命名实体识别 依存句法分析 关键词提取 自动摘要 短语提取 拼音 简繁转换 | TONY码屋

  11. 新人开始学习NLP, 我准备用 DFA 替代 AC 做多模式匹配, 我JAVA代码不熟, 可能到时候还得仔细学习下你的代码. 用DFA是否有什么风险, 我现在知道的是 构造 DFA状态表非常缓慢, 我使用你的字典做测试, 构造 50万左右单词的状态表在 i7 3720 上用时大约7分钟(时间复杂度我大概估算了下为 O(N^2), 构造200万的表看来得两小时), 构造1万左右单词的状态表用时2秒左右, DFA 很适合用于嵌入式环境, 我测试时 ROM (.text) 占用大约 20字节/单词, 扫描时 RAM 只需要几个字节就可以了, 代码看起来比 AC 简单些, 同时可以添加以正则表达式描述的单词, 感觉如果基本字典几乎不改变的情况下, 用 DFA 也是蛮合适的, 但网上的资料好像很少.

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机