放牧代码和思想
专注自然语言处理、机器学习算法

双数组Trie树(DoubleArrayTrie)Java实现

目录

双数组Trie树(DoubleArrayTrie)是一种空间复杂度低的Trie树,应用于字符区间大的语言(如中文、日文等)分词领域。

双数组Trie (Double-Array Trie)结构由日本人JUN-ICHI AOE于1989年提出的,是Trie结构的压缩形式,仅用两个线性数组来表示Trie树,该结构有效结合了数字搜索树(Digital Search Tree)检索时间高效的特点和链式表示的Trie空间结构紧凑的特点。双数组Trie的本质是一个确定有限状态自动机(DFA),每个节点代表自动机的一个状态,根据变量不同,进行状态转移,当到达结束状态或无法转移时,完成一次查询操作。在双数组所有键中包含的字符之间的联系都是通过简单的数学加法运算表示,不仅提高了检索速度,而且省去了链式结构中使用的大量指针,节省了存储空间。

——《基于双数组Trie树算法的字典改进和实现》

我看了几篇论文,发现中文里也就上面这篇质量最好,英文当属这篇双数组Trie的一种实现。不过我并不打算按论文的腔调摘抄理论,而是准备借助开源的 darts-java 写点代码分析与笔记,如果能帮到你,实属意外。

darts-java 是对 Taku Kudo 桑的 C++ 版 Double Array Trie 的 Java 移植,代码精简,只有一个Java文件,十分优美。

写一段测试代码

package com.hankcs;

import darts.DoubleArrayTrie;

import java.io.*;
import java.util.*;

/**
 * @author hankcs
 */
public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader reader = new BufferedReader(new FileReader("./data/small.dic"));
        String line;
        List<String> words = new ArrayList<String>();
        Set<Character> charset = new HashSet<Character>();
        while ((line = reader.readLine()) != null)
        {
            words.add(line);
            // 制作一份码表debug
            for (char c : line.toCharArray())
            {
                charset.add(c);
            }
        }
        reader.close();
        // 这个字典如果要加入新词必须按字典序,参考下面的代码
//        Collections.sort(words);
//        BufferedWriter writer = new BufferedWriter(new FileWriter("./data/sorted.dic", false));
//        for (String w : words)
//        {
//            writer.write(w);
//            writer.newLine();
//        }
        System.out.println("字典词条:" + words.size());

        {
            String infoCharsetValue = "";
            String infoCharsetCode = "";
            for (Character c : charset)
            {
                infoCharsetValue += c.charValue() + "    ";
                infoCharsetCode += (int)c.charValue() + " ";
            }
            infoCharsetValue += '\n';
            infoCharsetCode += '\n';
            System.out.print(infoCharsetValue);
            System.out.print(infoCharsetCode);
        }

        DoubleArrayTrie dat = new DoubleArrayTrie();
        System.out.println("是否错误: " + dat.build(words));
        System.out.println(dat);
        List<Integer> integerList = dat.commonPrefixSearch("一举成名天下知");
        for (int index : integerList)
        {
            System.out.println(words.get(index));
        }
    }
}

其中small.dic是一个微型的词典:

一举
一举一动
一举成名
一举成名天下知
万能
万能胶

输出:

字典词条:6
胶    名    动    知    下    成    举    一    能    天    万    
33014 21517 21160 30693 19979 25104 20030 19968 33021 22825 19975 
是否错误: 0
一举
一举成名
一举成名天下知

Trie树的构造与双数组的构造

双数组Trie树归根结底还是属于Trie树,所以免不了有一颗树的构造过程。不过这棵树并没有保存下来,而是边构造树边维护双数组,双数组的信息足以表示整棵树。比如对于上面的例子,首先建立一个空的root节点:

Node{code=0, depth=0, left=0, right=6}

其中code指的是字符的编码,在Java中是双字节,depth是深度,left及right表示这个节点在字典中的索引范围。

比如:

然后按照字典序插入所有的字串节点:

其中绿色节点为空字符,代表从根节点到此节点的路径上的所有节点构成一个词,整个的构建顺序是:

在darts-java中,使用了两个数组base和check来维护Trie树,它们的下标以及值都代表着一个确定的状态。base储存当前的状态以供状态转移使用,check验证字串是否由同一个状态转移而来并且当check为负的时候代表字串结束。(PS 双数组Tire树的具体实现有多种,有的实现将base为负作为状态的结束,大同小异。)

假定有字符串状态s,当前字符串状态为t,假定t加了一个字符c就等于状态tc,加了一个字符x等于状态tx,那么有

base[t] + c = base[tc]

base[t] + x = base[tx]

check[tc] = check[tx]

可见,在单词“一举一动”中,虽然有两个“一”,但它们的前一个状态不同,所以对应的状态分别为“”和“一举”,在base数组中的下标不一样。

在每个节点插入的过程中会修改这两个数组,具体说来:

1、初始化root节点base[0] = 1; check[0] = 0;

2、对于每一群兄弟节点,寻找一个begin值使得check[begin + a1…an]  == 0,也就是找到了n个空闲空间,a1…an是siblings中的n个节点对应的code。

        int pos = siblings.get(0).code;
        while (true)
        {
            pos++;
            begin = pos - siblings.get(0).code; // 当前位置离第一个兄弟节点的距离
            ……
        }

3、然后将这群兄弟节点的check设为check[begin + a1…an] = begin;很显然,叶子节点i的check[i]的值一定等于i,因为它是兄弟节点中的第一个,并且它的code为0。

check[begin + siblings.get(i).code] = begin;

4、接着对每个兄弟节点,如果它没有孩子,也就是上图除root外的绿色节点(叶子节点),令其base为负值;否则为该节点的子节点的插入位置(也就是begin值),同时插入子节点(迭代跳转到步骤2)。

            if (fetch(siblings.get(i), new_siblings) == 0)  // 无子节点,也就是叶子节点,代表一个词的终止且不为其他词的前缀
            {
                base[begin + siblings.get(i).code] = -siblings.get(i).left - 1;
                ……
            }
            else
            {
                int h = insert(new_siblings);   // dfs
                base[begin + siblings.get(i).code] = h;
            }

这里给出这个例子的base check值以及码表,下表中×代表空

码表:
   胶    名    动    知    下    成    举    一    能    天    万    
33014 21517 21160 30693 19979 25104 20030 19968 33021 22825 19975 

DoubleArrayTrie{
char =      ×    一    万     ×    举     ×    动     ×     下    名    ×    知      ×     ×    能    一    天    成    胶
i    =      0 19970 19977 20032 20033 21162 21164 21519 21520 21522 30695 30699 33023 33024 33028 40001 44345 45137 66038
base =      1     2     6    -1 20032    -2 21162    -3     5 21519    -4 30695    -5    -6 33023     3  1540     4 33024
check=      0     1     1 20032     2 21162     3 21519  1540     4 30695     5 33023 33024     6 20032 21519 20032 33023
size=66039, allocSize=2097152, key=[一举, 一举一动, 一举成名, 一举成名天下知, 万能, 万能胶], keySize=6, progress=6, nextCheckPos=33024, error_=0}

前缀查询

定义当前状态p = base[0] = 1。按照字符串char的顺序walk:

如果base[p] == check[base[p]] && base[base[p]] < 0则查到一个词;

然后状态转移,增加一个字符  p = base[char[i-1]] + char[i] + 1 。加1是为了与null节点区分开。

如果转移后base[char[i-1]] == check[base[char[i-1]] + char[i] + 1],那么下次p就从base[base[char[i-1]] + char[i] + 1]开始。

结合例子看可能更清楚:

字典词条:6
胶    名    动    知    下    成    举    一    能    天    万    
33014 21517 21160 30693 19979 25104 20030 19968 33021 22825 19975 
是否错误: 0
DoubleArrayTrie{
char =     ×    一    万    ×    举    ×    动    ×    下    名    ×    知    ×    ×    能    一    天    成    胶
i    =      0 19970 19977 20032 20033 21162 21164 21519 21520 21522 30695 30699 33023 33024 33028 40001 44345 45137 66038
base =      1     2     6    -1 20032    -2 21162    -3     5 21519    -4 30695    -5    -6 33023     3  1540     4 33024
check=      0     1     1 20032     2 21162     3 21519  1540     4 30695     5 33023 33024     6 20032 21519 20032 33023
size=66039, allocSize=2097152, key=null, keySize=6, progress=6, nextCheckPos=33024, error_=0}

i       =      0     0     1     1     2     2     3     3     4     4     5     5     6     6    循环退出
b       =      1     1     2     2 20032 20032     4     4 21519 21519  1540  1540     5     5    30695

p       =      1 19970     2 20033 20032 45137     4 21522 21519 44345  1540 21520     5 30699    30695
base[p] =      1     2     0 20032    -1     4     0 21519    -3  1540     0     5     0 30695    -4
check[p]=      0     1     0     2 20032 20032     0     4 21519 21519     0  1540     0     5    30695
一举
一举成名
一举成名天下知

稍微解释下

初始空 base[0] = 1, p = 1;

转移 p = base[0] + {char[一] = 19968} + 1 = 1 + 19968 + 1 = 19970,                检查base[19970]!=0说明有“一”这个字符。

 而  base[base[19970]] = base[2] = 0 说明没遇到词尾

转移 p = base[19970] + {char[举] = 20030} + 1 = 2 + 20030 + 1 = 20033,            检查base[20033]!=0说明有“举”这个字符。

 而  base[base[20033]] = base[20032] = -1 && base[20033] == check[20032] 说明遇到一个词尾,即查出“一举”

转移 p = base[20033] + {char[成] = 25104} + 1 = 20032 + 25104+ 1 = 45137,         检查base[45137]!=0说明有“成”这个字符。

……

基于双数组Trie树的Aho Corasick自动机

双数组Trie树能高速O(n)完成单串匹配,并且内存消耗可控,然而软肋在于多模式匹配,如果要匹配多个模式串,必须先实现前缀查询,然后频繁截取文本后缀才可多匹配,这样一份文本要回退扫描多遍,性能极低。

AC自动机能高速完成多模式匹配,然而具体实现聪明与否决定最终性能高低。大部分实现都是一个Map<Character, State>了事,无论是TreeMap的对数复杂度,还是HashMap的巨额空间复杂度与哈希函数的性能消耗,都会降低整体性能。

如果能用双数组Trie树表达AC自动机,就能集合两者的优点,得到一种近乎完美的数据结构。具体实现请参考《Aho Corasick自动机结合DoubleArrayTrie极速多模式匹配》。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 双数组Trie树(DoubleArrayTrie)Java实现

分享到:更多 ()

评论 52

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

    这里,我想指出一点,双数组的实现中全程没有用到check数组,也就是说不用check数组依然可以完成trie数构建。
    我觉得check数据计算应该是check[base + c] = s这样。而不是楼主写的check[base +c]=base 。用我提出的那种写法,可以根据子节点回溯到父节点的位置,而楼主这种实现,显然做不到。

    david1年前 (2016-07-13)回复
  2. #17

    你好,请教一个问题:在构造DoubleArrayTrie的时候,实际上先是把字典填充到TreeMap的。我想问的是,向TreeMap;里面灌词的时候,需要安全字典序的先后顺序进行PUT不?

    LMSS_872年前 (2016-04-22)回复
    • 你好,请教一个问题:在构造DoubleArrayTrie的时候,实际上先是把字典填充到TreeMap的。我想问的是,向TreeMap里面灌词的时候,需要按照字典序的先后顺序进行PUT不?

      LMSS_872年前 (2016-04-22)回复
      • 不需要

        hankcs2年前 (2016-04-22)回复
        • 哦,谢谢!

          飞星一念2年前 (2016-04-25)回复
  3. #16

    我仔细看了一下代码,发现博文中这句是不对的:“如果base[p] == check[p] && base[p] < 0 则查到一个词;” 所以,后面的解释,博主也写错了。

    源代码是这样的:

    for (int i = pos; i < len; i++) {
    p = b;
    n = base[p];

    if (b == check[p] && n < 0) {
    result.add(-n – 1);
    }

    p = b + (int) (keyChars[i]) + 1;
    if (b == check[p])
    b = base[p];
    else
    return result;
    }

    除第一轮循环外,在判断是否匹配成功时,b 的值 为前一次循环的 base[p],而不是当前循环的。

    另外,“一举成名天下知” 的匹配是在这个 for 循环退出之后进行的,博文的最后一张图中,在 i,b,p 变量那里,再加上下面这一列,可能会更清楚一些。

    i: 循环退出
    b:30695

    p:30695
    base[p]:-4
    check[p]:30695

    滑车2年前 (2015-11-29)回复
  4. #15

    “而 base[base[20033]] = base[20032] = -1 && base[20032] == check[20032] 说明遇到一个词尾”

    如果我没理解错的话,应该是 “base[base[20033]] = base[20032] = -1 && base[20033] == check[20032] 说明遇到一个词尾”吧~

    滑车2年前 (2015-11-28)回复
  5. #14

    代码有问题,commonPrefixSearch中最后的验证条件
    p = b;
    n = base ;

    if (b == check && n < 0) {
    result.add(-n – 1);
    }
    应该判断的是当前结束状态,也就是b的值,而不是n

    pz2年前 (2015-10-10)回复
  6. #13

    Segment seg = HanLP.newSegment().enableAllNamedEntityRecognize(true);List<Term> termList = seg.seg("奥巴马挑战荒野求生");
    单步跟踪到 if (config.organizationRecognize)
    {
    // 层叠隐马模型——生成输出作为下一级隐马输入
    vertexList = viterbi(wordNetOptimum);/////单步跟踪试一下
    //for(){}
    wordNetOptimum.clear();
    wordNetOptimum.addAll(vertexList);
    preSize = wordNetOptimum.size();
    OrganizationRecognition.Recognition(vertexList, wordNetOptimum, wordNetAll);
    }
    vertexList = viterbi(wordNetOptimum);wordNetOptimum在没进函数时是
    0:[ ]
    1:[奥巴马]
    2:[]
    3:[]
    4:[挑战]
    5:[]
    6:[荒野求生]
    7:[]
    8:[]
    9:[]
    10:[ ]
    从函数出来vertexList 就变成
    [ , 奥, 巴马, 挑战, 荒野, 求生, ]
    非常不能理解,为什么把奥巴马切开了,不是已经变为一个实体了吗?

    small bird2年前 (2015-09-19)回复
    • 我并没有复现你说的问题,在com/hankcs/hanlp/seg/Viterbi/ViterbiSegment.java第94行下断点,vertexList依然是[ , 奥巴马, 挑战, 荒野, 求生, ],Viterbi最短路并不会修改任何节点,它只是找一条最短路径而已。

      hankcs2年前 (2015-09-19)回复
      • 1、博主,你在用户词典中添加“荒野求生”,再识别一下,我这边确实是将“荒野求生”分开了,而且是在执行
        vertexList = viterbi(wordNetOptimum);时分开的。“奥巴马”没切开是因为你在二元词典中添加了“未##人@挑战 100”。
        2、我不是很清楚vertexList = viterbi(wordNetOptimum);这句话有什么用?我调试的时候发现形参wordNetOptimum已经是我想要的了,已经识别了人名、地名了。

        small bird2年前 (2015-09-19)回复
        • 好的,我已经复现了问题,并且找到了原因。等我吃完饭再解决它。

          hankcs2年前 (2015-09-19)回复
        • 1、现在正常了
          CustomDictionary.add("荒野求生");
          Segment seg = HanLP.newSegment().enableAllNamedEntityRecognize(true);
          List<Term> termList = seg.seg("奥巴马挑战荒野求生");
          System.out.println(termList);
          2、这句话是层叠隐马模型必需的。
          问题出在再次Viterbi之前没有清空最后一个节点的前驱节点的引用,不过我通过其他方法解决了。

          hankcs2年前 (2015-09-19)回复
          • public static int getBiFrequency(int idA, int idB)
            {
            if (idA == -1)
            {
            return 1000;
            }
            if (idB == -1)
            {
            return 1000;
            }
            int index = binarySearch(pair, start[idA], start[idA + 1] – start[idA], idB);
            if (index < 0) return 0;
            index <<= 1;
            return pair[index + 1];
            }但是这样那二元词典的意义就不是很大啦!比如进行分词时,
            int nTwoWordsFreq = CoreBiGramTableDictionary.getBiFrequency(from.wordID, to.wordID);如果二元词典没出现的词就默认1000了?或者是我理解错了

            small bird2年前 (2015-09-19)
          • 不是二元词典没出现的词,而是非核心词典的词,也就是用户词典的词。

            hankcs2年前 (2015-09-19)
          • 那可能需要核心词典要相当全,比如“钱啟挑战”,‘啟’在核心词典没有出现,则“啟@挑战”为1000,如果“未##人@挑战”<1000,那么钱啟会识别不了。感觉可以把参数设置小一点,1000有点大

            small bird2年前 (2015-09-19)
          • 这个倒没问题,[钱啟/nr, 挑战/vn],常见单个汉字基本都收录了。其实也可以在Viterbi方法之前添加一个

            wordNetOptimum.getVertexes()[sentence.length + 1].getFirst().from = null; // 再次维特比前清空引用

            不过我嫌它性能低就没这么干。

            hankcs2年前 (2015-09-19)
          • 我理解错了O(∩_∩)O哈哈~,和1000没有关系,不过“钱啟挑战”钱啟是识别不了

            small bird2年前 (2015-09-19)
          • [钱啟/nr, 挑战/vn]

            hankcs2年前 (2015-09-19)
          • 已经发现问题了,O(∩_∩)O谢谢

            small bird2年前 (2015-09-19)
  7. #12

    Segment seg = HanLP.newSegment().enableAllNamedEntityRecognize(true);List<Term> termList = seg.seg("奥巴马挑战荒野求生");
    粗分结果[奥/b, 巴马/ns, 挑战/vn, 荒野求生/nz],可是我明明在customdictionary中添加了“奥巴马”,单步跟踪到 public V output(int state)
    {
    if (state < 0) return null;
    int n = base[state];
    if (state == check[state] && n < 0)
    {
    return v[-n – 1];
    }
    return null;
    }
    return null了!!

    small bird2年前 (2015-09-19)回复
    • 感谢反馈。这个问题跟我的双数组无关。
      首先,核心词典优先级高于用户词典,核心词典中已经有奥巴马了。(优先级可能会在后续版本改进,符合大家的习惯)
      然后,问题在刚刚得到了解决,请clone Github上的最新版。

      hankcs2年前 (2015-09-19)回复
  8. #11

    博主你好!我有2个小问题请教
    1、我在用户词典中添加“荒野求生”,为什么在机构名识别时又将“荒野求生”分开了?
    2、“奥巴马挑战荒野求生”这一句,“奥巴马”识别为“奥/b,巴马/ns”,然后我想在用户词典中添加“奥巴马”来识别奥巴马,可是CoreDictionary.Attribute output = dat.output(state);output输出为null,我困惑了好几天了

    small low bird2年前 (2015-09-19)回复
    • 反馈问题的时候最好附上版本号、触发代码,节省彼此的时间。

      hankcs2年前 (2015-09-19)回复
  9. #10

    博主,按照你的例子试了下,用DoubleArrayTrie竟然没有结果,为何 ??

    荆棘2年前 (2015-09-09)回复
    • 请单步

      hankcs2年前 (2015-09-09)回复
      • 您试过没问题吗?

        荆棘2年前 (2015-09-09)回复
        • 没有

          hankcs2年前 (2015-09-09)回复
          • 博主,我用这段代码测试的:
            final String text = "奇妙";
            List<String> words = Arrays.asList(
            "一举", "一举一动", "一举成名", "一举成名天下知",
            "万能", "万能胶", "奇怪", "奇妙");
            DoubleArrayTrie dat = new DoubleArrayTrie();
            dat.build(words);
            List<Integer> integerList = dat.commonPrefixSearch(text);
            for (int index : integerList) {
            System.out.println(words.get(index));
            }
            结果如下:
            Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -7
            at DoubleArrayTrie.commonPrefixSearch(DoubleArrayTrie.java:373)
            at DoubleArrayTrie.commonPrefixSearch(DoubleArrayTrie.java:353)
            at Test.main(Test.java:7)

            荆棘2年前 (2015-09-09)
          • final String text = "奇妙";
            List<String> words = Arrays.asList(
            "一举", "一举一动", "一举成名", "一举成名天下知",
            "万能", "万能胶", "奇怪", "奇妙");
            Collections.sort(words);
            DoubleArrayTrie dat = new DoubleArrayTrie();
            dat.build(words);
            List<Integer> integerList = dat.commonPrefixSearch(text);
            for (int index : integerList) {
            System.out.println(words.get(index));
            }

            hankcs2年前 (2015-09-09)
  10. #9

    2天了 没看懂 能请教下吗

    林墓荷2年前 (2015-06-26)回复
  11. #8

    请问下,“我实现了通用的Trie树,支持泛型、遍历、储存、载入。”这个通用的代码在hanlp中,是哪个文件,我去学习下。谢谢!

    weyn3年前 (2015-05-19)回复
  12. #7

    看了两天这个算法没看懂 [汗] ,文中
    “假定有字符串状态s,当前字符串状态为t,假定t加了一个字符c就等于状态tc,加了一个字符x等于状态tx,那么有

    base[t ] + c = base[tc]

    base[t ] + x = base[tx]

    check[tc] = check[tx]
    ”我看了英文那个文章,不应该是base[t ] + c = tc,base[t ] + x = tx 么?
    这个“多说”在我这不是很稳定啊,不知道怎么了,这个评论有时候会丢失。

    lzru--3年前 (2015-02-05)回复
    • darts-java作者参考的是一篇日本论文,不是这篇英文论文,所以代码实现和英文论文不一致。我介绍的内容是从代码里总结出来的,具体是exactMatchSearch这个方法:
      int b = base[nodePos];
      int p;

      for (int i = pos; i < len; i++)
      {
      p = b + (int) (keyChars [i] ) + 1;
      if (b == check [p] )
      b = base [p] ;
      else
      return result;
      }
      你所说的base[t ] + c = tc,是将状态等同于下标,其实对应p = b + (int) (keyChars [i] ) + 1,我所说的base[t ] + c = base[tc],是将状态等同于base的值,其实对应b = base [p] 。在darts-java中,不是下标在转移,而是b值(也就是base [i] )在转移。原理是一样的,我这种状态的描述可能不适合你,有误导作用。

      hankcs3年前 (2015-02-05)回复
  13. #6

    楼主博文中的图作图用的什么软件?

    lzru--3年前 (2015-02-03)回复
  14. #5

    怎么样给定前缀,把所有是这个前缀的词都找出来,类似于搜素引擎的自动提示?

    郭锐3年前 (2015-01-15)回复
  15. #4

    博主,因为写论文需要,所以搜索双数组trie,看了你的博客,真的很佩服,很惭愧。要好好向你学习。惭愧。会继续来向你好好学习的

    web菜鸟3年前 (2015-01-06)回复
  16. #3

    我到github上下载了darts-java,也写了一个单元测试,甚至直接用了博主的测试代码,但是发现原程序有bug,无法得到博主的结果。
    请问您用的是那份代码?请多多指教。

    爱晓3年前 (2014-12-11)回复
    • 就是这份代码,你得自己准备一个./data/small.dic,里面的单词必须是字典序

      hankcs3年前 (2014-12-11)回复
  17. #2

    怎么用这个查找敏感词呢?

    郭锐3年前 (2014-11-21)回复
  18. #1

    看代码,在插入过程中,对于第2点,对于每一群兄弟节点,应该是寻找一个begin值使得check[begin + a1…an] == 0

    邓世龙3年前 (2014-07-04)回复

我的开源项目

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