双数组Trie树（Double-array Trie, DAT）是由三个日本人提出的一种Trie树的高效实现 [1]，兼顾了查询效率与空间存储。Ansj便是用DAT（虽然作者宣称是三数组Trie树，但本质上还是DAT）构造词典用作初次分词，极大地节省了内存占用。本文将简要地介绍DAT，并实现了基于DAT的前向最大匹配的中文分词算法。

1. Trie树

两种实现

Trie树（也称为字典树、前缀树）是一种常被用于词检索的树结构，其思想非常简单：利用词的共同前缀以达到节省空间的目的；基本的实现有array与linked-list两种。array实现需要为每一个字符开辟一个字母表大小的数组：

上图给出四个单词bachelor, baby, badge, jar的Trie树array实现示例图；对应的Java代码如下：

class TrieNode {  public Character value;  public TrieNode[] next = new TrieNode[65536]; // 65536 = 2^16}

虽然，array的查询时间复杂度为\(O(1)\)；但是，从图中可以看出，存在着大量的空间浪费。当然，有人会想到用HashMap来代替数组，以减少空间浪费：

class TrieNode {  public Character value;  public Map
    
      next = new HashMap
     
      ();}
     
    

便是以此来实现Trie树的。但是，HashMap本质上就是一个；存在着一定程度上的空间浪费。由此，容易想到用linked-list实现Trie树：

虽然linked-list避免了空间浪费，却增加了查询时间复杂度，因为公共前缀就意味着多次回溯。

Double-array实现

Double-array结合了array查询效率高、list节省空间的优点，具体是通过两个数组base、check来实现。Trie树可以等同于一个，状态为树节点的编号，边为字符；那么goto函数\(g(r,c) = s\)则表示状态r可以按字符c转移到状态s。base数组便是goto函数array实现，check数组为验证转移的有效性；两个数组满足如下转移方程：

base[r] + c = scheck[s] = r

值得指出的是，代入上述式子中的c为该字符的整数编码值。那么，bachelor, baby, badge, jar的DAT如下图所示：

其中，字符的编码表为{'#'=1, 'a'=2, 'b'=3, 'c'=4, etc. }。为了对Trie做进一步的压缩，用tail数组存储无公共前缀的尾字符串，且满足如下的特点：

tail of string [b1..bh] has no common prefix and the corresponding state is m:    base[m] < 0;    p = -base[m], tail[p] = b1, tail[p+1] = b2, ..., tail[p+h-1] = bh;

那么，用DAT检索词badge的过程如下：

// root -> bbase[1] + 'b' = 4 + 3 = 7// root -> b -> abase[7] + 'a' = 1 + 2 = 3// root -> b -> a -> dbase[3] + 'd' = 1 + 5 = 6// badge#base[6] = -12tail[12..14] = 'ge#'

至于如何构造数组base、check，可参考原论文 [1]及文章 [2].

2. DAT应用

以下代码分析基于ansj-5.1.1 版本。

词典

的core.dic给出中文词典的DAT实现：

24995237  %   65536   -1  3   {q=1}39  '   65536   -1  4   {en=1}46  .   65536   -1  5   {nb=1}...21360   印   92338   -1  2   {j=24, n=1, ng=2, nr=0, v=32}24230   度   89338   -1  2   {k=0, ng=2, q=28, v=7, vg=2}27827   河   142597  -1  2   {n=29, q=0}...116568  印度  71557   21360   2   {ns=51}99384   印度河 65536   116568  3   {ns=0}116553  振臂一 94926   129740  1   null116566  捅娄子 65536   116571  3   {v=0}65333   Ｕ   65536   -1  4   {en=1}...

词典共有6列，分别为

index   name    base    check   status  {词性->词频}

其中，index表示字符串的id（若为单字符，则为其unicode编码对应的整数值），name为词，base、check分别为DAT的base数组、check数组，status记录当前词的状态，最后一列表示词性集合，对应于类org.ansj.domain.AnsjItem中的成员变量termNatures。那么，根据DAT的转移方程则有

index['印度'] = 116568 = base['印'] + index['度'] = 92338 + 24230check['印度'] = 21360 = index['印']index['印度河'] = 99384 = base['印度'] + index['河'] = 71557 + 27827check['印度河'] = 116568 = index['印度']

此外，status的数值具有如下含义：

• 1对应的词性为null，name不能单独成词，应继续，比如“振臂一”；
• 2表示name既可单独成词，也可与其他字符组成新词，比如词“印度”；
• 3表示词结束，name成词不再继续，比如词“捅娄子”；
• 4表示英文字母（包括全角）+字符'，共计105(26*4+1)个字符;
• 5表示数字（包括全角）+小数点，共有21(10*2+1)个字符.

分词

正向最大匹配（Forward Maximum Matching, FMM）的分词思路非常简单：正向匹配词典中的词，取最长匹配者。Scala 2.11 实现FMM如下：

import org.ansj.library.DATDictionaryimport scala.collection.mutable.ArrayBuffer// max-matching algorithm for CWSdef maxMatching(sentence: String): Array[String] = {  val segmented = ArrayBuffer.empty[String]  val chars = sentence.toCharArray  var i = 0  while (i < chars.length) {    DATDictionary.status(chars(i)) match {      // not in core.dic or word-end or last char      case t if t == 0 || t == 3 || i == chars.length - 1 =>        i = singleCharWord(chars, i, segmented)      // word-start      case t if t == 1 || t == 2 =>        i = goOnWord(chars, i, segmented)      // English character or number      case _ =>        i = goOnEnNum(chars, i, segmented)    }  }  segmented.toArray}// a single character segmentprivate def singleCharWord(chars: Array[Char], start: Int, arr: ArrayBuffer[String]): Int = {  arr += chars(start).toString  start + 1}// word segment which is in core.dicprivate def goOnWord(chars: Array[Char], start: Int, arr: ArrayBuffer[String]): Int = {  var nextIndex: Int = chars(start).toInt  for (j <- start + 1 until chars.length) {    val preIndex = nextIndex    nextIndex = DATDictionary.getItem(nextIndex).getBase + chars(j).toInt    if (DATDictionary.getItem(nextIndex).getCheck != preIndex) {      arr += chars.subSequence(start, j).toString      return j    }  }  chars.length}// English chars and numbers compose a wordprivate def goOnEnNum(chars: Array[Char], start: Int, arr: ArrayBuffer[String]): Int = {  for (j <- start + 1 until chars.length) {    val status = DATDictionary.status(chars(j))    if (status != 4 && status != 5) {      arr += chars.subSequence(start, j).toString      return j    }  }  chars.length}

函数goOnWord用到了DAT的转移方程。直观感受下FMM的分词效果：

val sentence = "非农一触即发，现货原油扑朔迷离，伦敦金回暖已定"println(maxMatching(sentence).mkString("/"))// 非农/一触即发/，/现货/原油/扑朔迷离/，/伦敦/金/回暖/已/定

---

我实现了一个DAT生成算法，扔在中文分词项目。

3. 参考资料

[1] Aoe, J. I., Morimoto, K., & Sato, T. (1992). An efficient implementation of trie structures. Software: Practice and Experience, 22(9), 695-721.

[2] Theppitak Karoonboonyanan, .