《Java 数据结构与算法》：字典，附面试题

1.前言

Trie 的历史

字典树 Trie 这个词来自于 1912 年的 retrieval，Axel thue 最先被抽象描述时间将一组字符串数据结构存储为 Trie 的想法。 1960年，Edward·弗雷德金（Fuzzy Fredkin）独立描述了这个想法，并创造了特里（Trie）一词。 看看有多少程序员试图仅仅对一个单词、方法名称或属性名称感到困惑！

2。字典树的数据结构

在计算机科学中，字典树（Trie）也称为“词搜索树”或“数树”。它有时被称为基数树或前缀树（因为它可以通过前缀进行索引）。 - 它是一个搜索树，一种排序的数据结构，通常用于存储动态集合或以字符串为键的关联数组。

与二叉搜索树不同，键不直接存储在节点中，而是由节点在树中的位置确定。一个节点的所有子节点都有相同的前缀，即该节点对应的字符串，根节点对应空字符串。一般来说，并非所有节点都有匹配值。只有叶子节点和一些内部节点对应的键才有相关值。

• 这是一个将battle的单词串按字母拆分成字典树存储的图。
• 键标记在节点中，值标记在节点下方。每个完整的英文单词对应一个特定的整数。这意味着转换后的 ASCII 值对应于 26 个字母。

3。字典树结构的实现

字典树中存储了26个字母，这意味着在实现过程中，每个节点分支有26个槽来存储字母的可能组合。同样，如果是数树，就是10个数字的组合。每棵字典树上的一个节点对应的分支有10个操作来存储可能的数字组合。

接下来我们基于Java语言实现存储字典树和遍历索引的功能。

• 源码地址：https://github.com/fuzhengwei/java-algorithms
• 本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structs /src/main/java/stack

1.

public class TrieNode {

    /** 形成一个链 */
    public TrieNode[] slot = new TrieNode[26];

    /** 字母 */
    public char c;

    /** 单词：数量 > 0 表示一个单词 */
    public boolean isWord;

    /** 前缀 */
    public int prefix;

    /** 单词：具体的一个单词字符串 */
    public String word;

    /** 解释：单词的注释说明 */
    public String explain;

}

• 字典分支节点的树节点必须包含嵌入在该节点中的关联节点，后跟该节点的字母、该字母是否是单词、单词前缀、单词字符串以及该节点的可选注释当前词。

2。插入元素

public void insert(String words, String explain) {
    TrieNode root = wordsTree;
    char[] chars = words.toCharArray();
    for (char c : chars) {
        int idx = c - 'a'; // - a 从 0 开始，参考 ASCII 码表
        if (root.slot[idx] == null) {
            root.slot[idx] = new TrieNode();
        }
        root = root.slot[idx];
        root.c = c;
        root.prefix++;
    }
    root.explain = explain; // 单词的注释说明信息
    root.isWord = true;     // 循环拆解单词后标记
}

• 插入方法获取单词和注释信息，并按字符拆分单词。分割后，相应地计算并存储索引位置。完成后，保存标记的单词以及单词附带的注释信息。

3。索引元素

public List<String> searchPrefix(String prefix) {
    TrieNode root = wordsTree;
    char[] chars = prefix.toCharArray();
    StringBuilder cache = new StringBuilder();
    // 精准匹配：根据前置精准查找
    for (char c : chars) {
        int idx = c - 'a';
        // 匹配为空
        if (idx > root.slot.length || idx < 0 || root.slot[idx] == null) {
            return Collections.emptyList();
        }
        cache.append(c);
        root = root.slot[idx];
    }
    // 模糊匹配：根据前缀的最后一个单词，递归遍历所有的单词
    ArrayList<String> list = new ArrayList<>();
    if (root.prefix != 0) {
        for (int i = 0; i < root.slot.length; i++) {
            if (root.slot[i] != null) {
                char c = (char) (i + 'a');
                collect(root.slot[i], String.valueOf(cache) + c, list, 15);
                if (list.size() >= 15) {
                    return list;
                }
            }
        }
    }
    return list;
}

protected void collect(TrieNode trieNode, String pre, List<String> queue, int resultLimit) {
    // 找到单词
    if (trieNode.isWord) {
        trieNode.word = pre;
        // 保存检索到的单词到 queue
        queue.add(trieNode.word + " -> " + trieNode.explain);
        if (queue.size() >= resultLimit) {
            return;
        }
    }
    // 递归调用，查找单词
    for (int i = 0; i < trieNode.slot.length; i++) {
        char c = (char) ('a' + i);
        if (trieNode.slot[i] != null) {
            collect(trieNode.slot[i], pre + c, queue, resultLimit);
        }
    }
}

• 从字典树中检索元素的过程分为两部分。第一部分是根据提供的索引前缀精确匹配单词信息，第二部分是从索引前缀的最后一个单词开始。 ，循环从当前位置开始递归地遍历可以匹配的字母，直到被认为是单词标记并终止。这样，所有匹配的单词就被索引了。
• list.size()>=15是索引的最大长度。如果超过这个数字，索引就会停止。毕竟，这是一个 O(n) 时间复杂度的操作。如果加载几十万个单词进行匹配，执行速度还是相当耗时的。

4。词汇树功能测试

@Test
public void test_trie() {
    Trie trie = new Trie();
    // 存入
    trie.insert("bat","大厂");
    trie.insert("batch", "批量");
    trie.insert("bitch", "彪子");
    trie.insert("battle", "战斗");
    logger.info(trie.toString());
    // 检索
    List<String> trieNodes = trie.searchPrefix("ba");
    logger.info("测试结果：{}", JSON.toJSONString(trieNodes));
}

• 这里有一些带有相似字母的单词和名词来测试。您还可以尝试读取txt文件并获取并保存数十万个单词以进行验证。

测试结果

06:21:38.226 [main]INFOtrie.__test__.TrieTest- 测试结果：["bat -> 大厂","batch -> 批量","battle -> 战斗"]

Process finished with exit code 0

• 从测试结果中可以看到，所有以ba开头的单词都被找到了。这也是字典树基本功能的体现。
• 在学习过程中，读者可以尝试在搜索方法体内打几个断点，看看具体的执行过程，以方便学习所有的执行步骤。 ？资料】
• 存储和检索字典树的时间消耗
• 还有哪些方式实现字典树【后缀树、哈希树、帽子树】

作者：小付哥博客https://bugstack .cn