字典树与实际应用：拼写检查与搜索建议

hello，大家好，我是 Lorin，今天给大家带来数据结构中，多叉树的一种应用-字典树，来看看它为什么可以广泛应用于字符串处理、搜索引擎、自动完成、拼写检查等领域。

字典树

字典树，又称前缀树（Trie Tree），是一种基于树状结构的数据结构，广泛应用于字符串处理、搜索引擎、自动完成、拼写检查等领域。本文将深入探讨字典树的定义、原理、Java 实现方式以及一些常见的使用场景。

定义

字典树是一种多叉树结构，通常包含以下基本特点：

代码语言：txt复制

1、每个节点代表一个字符。
2、从根节点到任何一个节点，路径上经过的字符连接起来就是该节点所代表的字符串。
3、每个节点可以包含多个子节点，每个子节点代表不同的字符。

下面是一个由单词 aa、ac、cd、die 构成的字典树：

性能分析

时间复杂度

插入操作的时间复杂度：对于要插入的字符串，需要从根节点开始，逐个字符进行查找和插入。插入的时间复杂度与字符串的长度成正比，即 O(L)，其中 L 是字符串的长度。
查询操作的时间复杂度：查询操作也需要从根节点开始，逐个字符进行查找。查询的时间复杂度同样与查询的字符串长度成正比，即 O(L)。

空间复杂度

插入操作的空间复杂度：字典树的空间复杂度主要受到存储的字符串数量和字符串长度的影响。在最坏情况下，每个字符都需要创建一个节点，因此字典树的空间复杂度可以表示为 O(N*L)，其中 N 是存储的字符串数量，L 是字符串的平均长度。
查询操作的空间复杂度：查询操作不会显著影响字典树的空间复杂度。它仅需要一些额外的内存来存储临时变量和循环过程中的指针，因此空间复杂度仍然是 O(1)。

使用场景

字典树在以下场景中具有广泛的应用：

自动完成和搜索建议

字典树可用于实现搜索引擎的自动完成和搜索建议功能。通过将搜索关键字构建成字典树，可以快速地查找以用户输入为前缀的所有可能搜索词汇。

拼写检查和纠正

字典树也被用于拼写检查和纠正。通过将正确的单词构建成字典树，可以在用户输入错误拼写时，快速地找到可能的正确拼写建议。

IP 路由表

字典树还在网络路由表的查找中发挥了重要作用。可以帮助路由器快速匹配目标 IP 地址，以确定下一跳路由。

拼写补全

拼写补全和上面提到的 “自动完成和搜索建议” 类似，基于常见词汇表和拼写习惯，提示用户可能会输入的词，帮助用户提高拼写速度。

字典树构建思路

字典树的构建是一个逐字符插入的过程。从根节点开始，按照字符串中的字符顺序依次插入节点，如果节点不存在，则创建新节点。这个过程一直重复，直到所有的字符串都被插入为止。

Java 版实现

代码语言：java复制

public class Trie {

    private final int CHAR_ENUM_SIZE = 26;

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public static void main(String[] args) {
        String[] stringArr = {"dasdbehfb", "fsdfds", "asda", "dasdasdrew", "rewrewrrw"};
        Trie trie = new Trie();
        for (String s : stringArr) {
            trie.insert(s);
        }
        if (trie.isExist(stringArr[1])) {
            System.out.println(stringArr[1]   "存在");
        }
        if (!trie.isExist("abc")) {
            System.out.println("abc不存在");
        }
        // output
        // fsdfds存在
        // abc不存在
    }

    /**
     * 插入字符串
     *
     * @param str
     * @return
     */
    public void insert(String str) {
        TrieNode currentTrieNode = root;
        for (char c : str.toCharArray()) {
            if (currentTrieNode.nextNode[c - 'a'] == null) {
                currentTrieNode.nextNode[c - 'a'] = new TrieNode();
            }
            currentTrieNode = currentTrieNode.nextNode[c - 'a'];
            currentTrieNode.count =  1;
        }
    }

    /**
     * 查询字符是否存在
     *
     * @param str
     * @return
     */
    public Boolean isExist(String str) {
        TrieNode currentTrieNode = root;
        for (char c : str.toCharArray()) {
            if (currentTrieNode.nextNode[c - 'a'] == null) {
                return false;
            }
            currentTrieNode = currentTrieNode.nextNode[c - 'a'];
        }
        return true;
    }

    /***
     * 字典树节点
     */
    class TrieNode {
        /**
         * 统计存在该前缀的字符个数
         */
        int count;
        TrieNode[] nextNode = new TrieNode[CHAR_ENUM_SIZE];

        public TrieNode() {
            count = 0;
        }
    }
}

个人简介

2023腾讯·技术创作特训营第三期数据结构

0 人点赞