Trie树

一切知识都从一个小问题开始:

​ 给定一些命令,如set, setbit, setnx, strlen,get, getbit, exists 实现自动补全功能,例如输入se, 提示set, setbit, setnx

此视频为录制的redis客户端命令操作,很显然redis-cli就实现了这样的功能

假设我们运用现有的知识,应当如何解决这个问题呢?

  1. MySQL

    直接使用MySQL的 like 'se%' 命令即可,确实,作为一个每天沉迷业务的程序员很快就能想到这样的方式,但是就这么个小问题,需要使用上MySQL吗,不至于不至于

  2. B+Tree

    我们知道,MySQL的数据结构使用的是B+Tree, (什么?你不知道?现在你知道了吧「滑稽.jpg」),它构建好后就像这样

    查找过程如下:

    ​ se -> 转ASCII码, 与根结点比较,小于setbit的ASCII码,走左边,定位到set,依次从左往右遍历,一一比较,输出所有前缀为se的字符串。

  3. 有序数组

    虽然b+数的查找效率确实很好,但是构建过程却是比较复杂的,有没有一个更加简单的数据结构呢?通过分析b+树的解决方式,我们可以发现,这里用到了两个特性:二分,有序,通过二分的方式快速定位到最小结点,就能有序的从左往右取出值了,考虑到我们的命令不是很多,如果我们只使用有序这个特性会怎样呢?就像这样:

    [exists, get, getbit, set, setbit, setnx, strlen]
    

    查找过程如下:

    输入se,从左往右遍历匹配,找到符合se前缀的值set开始输出,直到遇到不符合的值strlen,停止遍历

    这样的方式就非常简单了,但是效率确实不如b+tree

所以到底有没有更加好的方式呢?我们先来总结一下,更加好的方式需要满足的特性:

  • 二分,可以快速定位
  • 有序,顺序的取出符合要求的元素
  • 简单,结构简单

其实,这就是一颗有序的且结构简单的树(最常见的能二分的结构其实就是树了),也就是本次的主角:Trie树

概念

计算机科学中,trie,又称前缀树字典树,是一种有序,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

构建过程

根据维基百科的概念,我们可以总结出以下特性

  1. 根节点对应空字符串。
  2. 一个节点的所有子孙都有相同的前缀。
  3. 不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

所以我们将set, setbit, setnx, strlen, get, getbit, exists构建好后,它的样子如图

可以对比一下这张图和几个特性

Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起

我给大家介绍一下这颗树

  • 上面的黄色结点表示终点(构建时打上标记),指一个完整的字符串,如第二条链中的get,getbit, 一般情况下除了黄色结点是不会有值的,这里只是为了更好的展现出来。
  • 树的每一层都是按照字母顺序(a-z)从左到右排列

那么,我先现在就尝试查找一个字符串是否存在,比如查找get

  1. g -> 定位到 g字母对应的叉 -getbit
  2. e -> 定位到 -etbit
  3. t -> 判断t点是否是终点 -> 是 -> 存在

时间复杂度为O(n) n为需要查找的字符串长度

为什么是O(n)? get定位了3次,难道每次定位一个字符都是O(1)? 怎么做到的?

查询前缀同理

所以我们想要做一个自动补全功能时,比如输入se,流程如下:

  1. s -> 找到s对应的叉
  2. e -> 找到s链的e结点对应的叉
  3. 遍历e结点下的整颗树
  4. 当遇见黄点时输出该值

到这里,原理相信大家都已经明白了,那么代码应当如何实现呢?

代码

树的实现无非两种,数组 或者 链表,通过观察上面的树,可以发现,每一层的结点最多有26个(a-z),我们可以直接开辟26个长度的数组存储这些结点,又因为每一层的字符是有序的,于是定位一个字符c的时候只需要c-'a'就能得出下标,如定位g

'g' - 'a' = 6

数据结构如下:

public class TrieNode {
	// 是否是终点
  boolean isEnd;
  // 字符串的值,isEnd = true 时才有
  String value;
  // 子结点
  TrieNode[] childrenNodes = new TrieNode[26];
}

完整代码:

public class TrieTree {

    TrieNode trieNode;

    public TrieTree() {
        this.trieNode = new TrieNode();
    }

    /**
     * 增加一个结点
     * 
     * @param word 单词
     */
    public void add(String word) {
        char[] chars = word.toLowerCase().toCharArray();
        TrieNode next = trieNode;
        for (char c : chars) {
            TrieNode trieNode = next.childrenNodes[c - 'a'];
            if (trieNode == null) {
                trieNode = new TrieNode();
                next.childrenNodes[c - 'a'] = trieNode;
            }
            next = trieNode;
        }
        next.isEnd = true;
        next.value = word;
    }

    /**
     * 查询单词是否存在
     * 
     * @param word 单词
     * @return 是否存在
     */
    public boolean search(String word){
        TrieNode trieNode = searchNode(word);
        return trieNode != null && trieNode.isEnd;
    }

    /**
     * 判断前缀是否存在
     * 
     * @param prefix 前缀
     * @return 是否存在
     */
    public boolean starsWith(String prefix){
        return searchNode(prefix) != null;
    }

    /**
     * 查询结点
     * 
     * @param word 单词
     * @return 结点
     */
    private TrieNode searchNode(String word){
        char[] chars = word.toLowerCase().toCharArray();
        TrieNode next = trieNode;
        for (char c : chars) {
            TrieNode trieNode = next.childrenNodes[c - 'a'];
            if (trieNode == null) {
                return null;
            }
            next = trieNode;
        }
        return next;
    }

    /**
     * 自动补全
     * @param prefix 前缀
     * @param list 结果集
     */
    public void autocomplete(String prefix, List<String> list){
        TrieNode trieNode = searchNode(prefix);
        if (trieNode != null) {
            autocomplete(trieNode, list);
        }
    }

    private void autocomplete(TrieNode trieNode, List<String> list){
        TrieNode[] trieNodes = trieNode.childrenNodes;
        for (TrieNode node : trieNodes) {
            if (node != null) {
                if (node.isEnd) {
                    list.add(node.value);
                }
                autocomplete(node, list);
            }
        }
    }

    public class TrieNode {
        // 是否是终点
        boolean isEnd;
        // 字符串的值,isEnd = true 时才有
        String value;
        // 子结点
        TrieNode[] childrenNodes = new TrieNode[26];
    }

    public static void main(String[] args) {
        TrieTree trieTree = new TrieTree();
        trieTree.add("apple");
        trieTree.add("apply");
        trieTree.add("application");
        System.out.println(trieTree.search("apple"));
        System.out.println(trieTree.search("app"));
        System.out.println(trieTree.starsWith("app"));
        List<String> list = new ArrayList<>();
        trieTree.autocomplete("app", list);
        System.out.println(list);
    }
}

测试结果

true
false
true
[apple, application, apply]

小结

本篇介绍了什么是Trie树,以及通过Trie树如何实现一个自动补全功能,下面我们计算一下它的时间复杂度和空间复杂度

时间复杂度:O(n) n为需要查找的字符串长度

空间复杂度:26^n

26^n这个字眼着实令人咂舌,这也是大家常说trie树是一颗空间换时间的树,而且这还只是只有英文字符的情况,倘若加上数字呢,中文呢?

那么有没有什么优化的办法呢?

有的,比如查看上图就能发现,虽然把所有前缀相同的单词合并到了一起,但是还是有很多重复的,比如 setbit, getbit, 这两个单词出入开头的s和g不同,其他的都是相同的,如果我们能把他们共用,岂不也能大大缩小空间,如何实现,下次再说!

Trie树的应用场景

  1. 词语查找,比如在中文分词器中,就可以使用用户字典构建一颗Trie树,使用时输入句子进行匹配分词
  2. 自动补全
  3. 拼写检查
#   trie 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×