前言

上一节的BinTrie的接口做到了1000万字每秒的速度，比Python的64万字每秒提高了两个数量级。但我们是算法工程师，要做到挑战极限。

提示：以下是本篇文章正文内容，下面案例可供参考

一、双数组字典树（DAT）是什么？

Trie树本质是一个确定的有限状态自动机(DFA)，核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

但由于Trie树的稀疏现象严重，空间利用率较低为了让Trie树实现占用较少的空间，同时还要保证查询的效率，最后提出了用2个线性数组来进行Trie树的表示，即双数组Trie(Double Array Trie).

双数组Trie（Double-ArrayTrie）是trie树的一个简单而有效的实现，由两个整数数组构成，一个是base[]，另一个是check[]。

base数组的每个元素表示一个Trie节点，即一个状态(分为空闲状态和占用状态)

check数组的每个元素表示某个状态的前驱状态

公式如下：

p = base[b] + c
check[p] = base[b]

若不满足此条件，则状态转移失败。举个例子，当前状态为自然(状态由一个整数下标表示，下同)，我们想知道是否可以转移到自然人。那么我们先执行自然人=base [自然]+人,然后检查 check [ 自然人]==base[自然]是否成立，据此判断转移是否成功。

也就是说，我们仅仅执行一次加法和一次整数比较就能进行状态转移，因而只花费了常数时间。

二、了解一下源码

1.定义一个双数组

代码如下（示例）：

class DoubleArrayTrie(object):
    def __init__(self, dic: dict) -> None:
        m = JClass('java.util.TreeMap')()
        for k, v in dic.items():
            m[k] = v
        DoubleArrayTrie = JClass('com.hankcs.hanlp.collection.trie.DoubleArrayTrie')
        dat = DoubleArrayTrie(m)
        self.base = dat.getBase()
        self.check = dat.getCheck()
        self.value = dat.getValueArray([''])

这里的双数组的构造直接由Hanlp实现，直接拿到对应的base，check，value值

2.状态转移

前面有讲述，Python的散列值不适合字符，所以直接借用 java 的 hashcode()

代码如下（示例）：

@staticmethod
    def char_hash(c) -> int:
        return JClass('java.lang.Character')(c).hashCode()

此处根据java的character对象创建字符并用hashcode方法取得其散列值

考虑到不是所有节点都对应词语终点，只有字典树中的终点节点（蓝色节点）才对应一个词语。为了区分它们，实现上可以借鉴C语言中的设计，在每个字符串末尾添加一个散列值等于0的\0，也就是说,\0充当了蓝色节点的角色，这样普通节点就不需要分配内存标记自己的颜色了。考虑到用户输入的文本中也可能含有\0，为了避免与此混淆,HanLP采用将文本字符的hashCode加一。一个兼容\0的转移函数的实现如下:

def transition(self, c, b) -> int:
        """
        状态转移
        :param c: 字符
        :param b: 初始状态
        :return: 转移后的状态，-1表示失败
        """
        p = self.base[b] + self.char_hash(c) + 1
        if self.base[b] == self.check[p]:
            return p
        else:
            return -1

除了额外加一的技巧外，这段代码与双数组字典树一致。

3.查询

有了状态转移函数，我们再对键取值查询就方便多了，带上多出来的+1（\0），也就是状态转移至多是len(key)+1次。

def __getitem__(self, key: str):
        b = 0
        for i in range(0, len(key)):  # len(key)次状态转移
            p = self.transition(key[i], b)
            if p is not -1:
                b = p
            else:
                return None
        p = self.base[b]  # 按字符'\0'进行状态转移
        n = self.base[p]  # 查询base
        if p == self.check[p] and n < 0:  # 状态转移成功且对应词语结尾
            index = -n - 1  # 取得字典序
            return self.value[index]
        return None

测试一下效果：

if __name__ == '__main__':
    dic = {'自然': 'nature', '自然人': 'human', '自然语言': 'language', '自语': 'talk  to oneself', '入门': 'introduction'}
    dat = DoubleArrayTrie(dic)
    #assert dat['自然'] == 'nature'
    #assert dat['自然语言'] == 'language'
    #assert dat['不存在'] is None
    #assert dat['自然\0在'] is None
    print(dat['自然'])
    print(dat['自然语言'])
    print(dat['不存在'])
    print(dat['自然\0在'])

总结

多看，多思考，不懂的先保留，重在理解晗佬的思路，解决方案。