简单易懂的字典树

全文字数：3837字

阅读时间：15分钟

前言

字典树是一个比较简单的数据结构，字典树可以利用字符串的公共前缀减少查询字符串的时间，因此字典树常常用在需要大量查询字符串的操作任务中。本文主要从最基本的字典树入手，介绍什么是字典树以及字典树的增删改查，着重介绍字典树的插入和查询操作，最后通过伪代码的形式更好的介绍字典树。

a

什么是字典树？

字典树（Trie树、前缀树）是一种用于快速检索的多叉树结构。字典树把字符串看成字符序列，根据字符串中字符序列的先后顺序构造从上到下的树结构，树结构中的每一条边都对应着一个字符。字典树上存储的字符串被视为从根节点到某个节点之间的一条路径，并在终点节点上做个标记"该节点对应词语的结尾"，正因为有终点节点的存在，字典树不仅可以实现简单的存储字符串，还可以实现字符串的映射，只需要将相对应的值悬挂在终点节点上即可，比如"自然"="nature"的映射，只需要将"自然"路径上终点节点的值设置为"natrue"。

下面是一个典型的字典树：

▲字典树

使用蓝色标记该节点是一个字符串的结尾，数字是人为的编号。通过上面这棵典型的字典树可以直观的看出字典树的一些特点：

• 根节点不包含任何字符（0号节点），其余的每一个节点只包含一个字符（具体应该是连接的边上）；
• 终点节点不一定是叶子节点，每一个终点节点都对应着一个字符串，从根节点到终点节点路径上的字符连接起来即为该终点节点所对应的字符串；
• 拥有相同字符前缀的字符串共享路径，这也是字典树又被称为前缀树的原因，字典树能够利用字符串中的公共前缀，这样可能会节省内存，不过通过上图中字符"语"来看，如果系统中存在大量字符串并且这些字符串基本没有前缀，相应的字典树内存消耗也会很大；
• 不过利用字符串的公共前缀可以减少查询字符串的时间，能够最大限度的减少无谓的字符串比较，同时在查询的过程中不需要预知待查询字符串的长度，沿着字典树的边进行匹配，查询效率比较高，这也是字典树算法的优点所在；

正是由于字典树的这些特点，字典树被用于统计、排序和保存大量的字符串（不仅限于字符串）。

在基于词典的中文分词任务中，分词的词典是由一系列字符串所组成的，而基于词典的中文分词任务的核心就是字符序列与词典中的字符串进行匹配：

• 如果匹配成功则将字符序列确定为分词结果；
• 如果匹配失败则重新选择字符序列；

匹配的过程简单来说就是看看分得的字符序列在词典中能不能找到，而这些操作的效率直接影响到最终中文分词任务的效率，并且在基于词典的中文分词任务中核心价值不在于精度，而在于速度。当然不仅仅局限在基于词典的中文分词任务中，还可以用在任何需要词典、需要进行大量的字符串匹配的任务中。字典树的优点在于字符串的查询效率，而在使用基于词典的任务中需要大量的字符串查询操作，因此可以将词典中的字符串构造成字典树，这样在匹配待分词的字符序列的时候能够提高效率。

b

字典树的增删改查

字典树的基本操作增删改查，也就是插入（insert）、删除（delete）、修改（update）和查询（search）。删除和修改操作本质上和查询操作是一样的，删除操作通过查询找到对应的终点节点，将终点节点设置为None即可，而修改操作只需将终点节点设置为另外一个字符值，因此对于字典树来说最主要的就是插入和查询操作，接下来具体的看一看字典树的插入和查询操作。

▍ 字典树的插入

字典树的插入操作简单来说就是将字符串插入表示字典树的结构中。为了方便这里以文章开头展示的字典树为例，将"入门", "自然", "自然人", "自然语言", "自语"5个单词插入到字典树中。

在进行插入操作之前首先定义一个变量p用于表示当前处理的节点对象。为了叙述方便，这里将节点上人为定义的编号表示当前的节点对象，并使用红色箭头进行标识。比如p = 0，表示p为0号节点对象，即根节点的对象。

• 将"入门"插入到字典树中

初始节点对象p=0，此时的红色箭头定位到根节点的位置，首先插入字符"入"：

1. 判断与根节点连接的子节点中是否有一条标识为"入"的边 --> 没有；
2. 创建一个新节点编号为1，将1号节点作为0号节点的子节点并将连接的边标识为"入"；
3. 判断字符"入"是否为"入门"的最后一个字符 --> 不是；

▲插入"入"字符到字典树中

节点变量p = 1，此时的红色箭头定位到1号节点的位置，接下来插入字符"门"：

1. 判断与1号节点连接的子节点中是否有一条标识为"门"的边 --> 没有；
2. 创建一个新节点编号为2，将2号节点作为1号节点的子节点并将连接的边标识为"门"；
3. 判断字符"门"是否为"入门"的最后一个字符 --> 是；
4. 将2号节点标识为终止节点；

▲插入"门"字符到字典树中

• 将"自然"插入到字典树中

插入"自然"字符串和插入"入门"类似，不过要注意每次插入新的字符串都需要将变量p设置为0，也就是定位到根节点。由于插入过程类似，这里不再赘述。

▲插入"自然"后的字典树

• 将"自然人"插入到字典树中

由于"自然"和"自然人"拥有相同的字符前缀，因此插入过程稍有不同。由于是新插入的字符串，因此将变量p设置为0，此时的红色箭头定位到根节点的位置，首先插入字符"自"：

1. 判断与根节点连接的子节点中是否有一条标识为"自"的边 --> 有；
2. 获取对应子节点的对象，并将p设置为此节点；
3. 判断字符"自"是否为"自然人"的最后一个字符 --> 不是；

▲插入"自"字符到字典树中

节点变量p = 3，此时的红色箭头定位到3号节点的位置，接下来插入字符"然"：

1. 判断与3号节点连接的子节点中是否有一条标识为"然"的边 --> 有；
2. 获取对应子节点的对象，并将p设置为此节点；
3. 判断字符"然"是否为"自然人"的最后一个字符 --> 不是；

▲插入"然"字符到字典树中

节点变量p = 4，此时的红色箭头定位到4号节点的位置，最后插入字符"人"：

1. 判断与4号节点连接的子节点中是否有一条标识为"人"的边 --> 没有；
2. 创建一个新节点编号为5，将5号节点作为4号节点的子节点并将连接的边标识为"人"；
3. 判断字符"人"是否为"自然人"的最后一个字符 --> 是；
4. 将5号节点标识为终点节点；

▲插入"人"字符到字典树中

有了前面的介绍，插入"自然语言"和"自语"就非常简单了，这里不再赘述。

通过上面的介绍，对于字典树的插入操作需要注意：

1. 每次新插入字符串的时候，都需要先定位到根节点；
2. 插入操作的过程中包含着查询操作，其实无外乎有两种情况：
   1. 查询到对应字符边的子节点，则将对应子节点赋值给变量p；
   2. 没有查询到对应字符边的子节点，则创建新的子节点，将连接的边标识为对应的字符，最后变量p设置新创建的子节点；

通过上面的介绍大致了解了字典树插入操作的整个流程，相对来说比较简单，下面给出简单的伪代码：

def insert(string):
    """
    字典树的插入操作
    :param string: 要插入的字符串
    :return:
    """
    p = root # 初始为root根节点
    for i in range(string.len): # 遍历要插入的字符序列
        s = string[i]
        if p.get_childNode(s) == None: # 没有找到边标识为字符s的子节点
            p.add_childNode(s, new Node()) # 在p指向的节点下创建新的子节点，并将边标识为字符s
        p = p.get_childNode(s) # 找到边标识为字符s的子节点，更新p为对应的子节点
    p.markEndPoint() # 结尾字符进行标识

▍ 字典树的查询

字典树的查询操作简单来说就是看字典树中包不包含指定的字符串。其实查询操作比较简单，只需要从根节点开始，沿着树的边进行移动：

• 如果成功到达终止节点，则说明字符串在字典树中。比如想要查询"入门"字符串，在对应的字典树中从根节点开始沿着0-1-2的路径进行移动，最后到达的2号节点是终止节点，因此匹配成功，说明"入门"在字典树中；
• 如果最后没有路径或者到达的节点不是终点节点，则说明字符串不在字典树中。例如想要查询"自然界"，在对应的字典树中从根节点来时沿着0-3-4路径开始，不过字符还没匹配完，字典树中就没有对应的路径了，因此匹配失败，说明"自然界"不在字典树中；

通过上面的介绍大致了解了字典树查询操作的整个流程，下面给出简单的伪代码：

def search(string):
    """
    字符串的查询操作
    :param string: 待查询的字符串
    :return: 字符串是否在字典树中
    """
    p = root # 初始为root根节点
    for i in range(string.len): # 遍历要插入的字符序列
        s = string[i]
        if p.get_childNode(s) == None: # 没有找到边标识为字符s的子节点
            return False
        p = p.get_childNode(s) # 找到边标识为字符s的子节点，更新p为对应的子节点
    if ismarkEndPoint(p): # 最后判断p是否为终点节点
        return False # 如果不是则返回False，匹配失败
    return True

有了字典树插入和查询的伪代码就可以非常简单的实现一个最为朴素的字典树。

参考：

1. 百度百科
2. 《自然语言处理入门》