数据结构:字典树 Trie——打一个字联想出一串词语
2023-02-19 12:24:11 时间
一、前言
Trie 的历史
字典树 Trie 这个词来自于 retrieval,于 1912 年,Axel Thue 首次抽象地描述了一组字符串数据结构的存放方式为 Trie 的想法。这个想法于 1960 年由 Edward Fredkin 独立描述,并创造了 Trie 一词。你看看,多少程序员为了一个词、方法名、属性名,想破脑袋!
二、字典树数据结构
在计算机科学中,字典树(Trie)也被称为”单词查找树“或”数字树“,有时候也被称为基数树或前缀树(因为可以通过前缀的方式进行索引)。—— 它是一种搜索树,一种已排序的数据结构,通常用于存储动态集或键为字符串的关联数组。
与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。
- 这是一个把 battle 单词字符串,按照字母拆分到字典树进行存放的图。
- 键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。也就是26个字母对应的 ASCII 转换后的值。
三、字典树结构实现
字典树字母的存放有26个,也就是说在实现的过程中,每一个节点的分支都有26个槽位用来存放可能出现的字母组合。同理如果是数字树的话就是10个数字的组合,每个字典树上的节点对应的分支则有10个操作存放可能出现组合的数字。
接下来我们就基于 Java 语言实现一个字典树的存放和遍历索引的功能。
- 源码地址:https://github.com/fuzhengwei/java-algorithms
- 本章源码:https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/trie
1. 树枝节点
- 字典的树的节点需要包括此节点内嵌的关联节点,之后是节点的字母、到此字母是否为单词、单词的前缀、单词字符串和当前单词的非必要注释。
2. 插入元素
- insert 方法接收单词和注释信息,并对一个单词按照 char 进行拆分,拆分后则计算出索引位置并以此存放。存放完成后标记单词和附属上单词的注释信息。
3. 索引元素
- 从字典树从检索元素的过程分为2部分,第1部分是根据提供的索引前缀精准匹配到单词信息,第2部分是根据索引前缀的最后一个单词开始,循环递归遍历从当前位置所能关联到的字母直至判断为是单词标记为结束,通过这样的方式把所有匹配动的单词索引出来。
- list.size() >= 15 是判定索引的最大长度,超过这个数量就停止索引了,毕竟这是一种O(n)时间复杂度的操作,如果加载数十万单词进行匹配,执行速度还是比较耗时的。
四、字典树功能测试
- 这里提供一些有相近字母的单词和名词,用于测试。你也可以尝试读取txt文件,检索存入数十万单词进行检索验证。
测试结果
- 通过测试结果可以看到,把所有以 ba开头的单词全部检索出来了。这也是字典树最核心功能的体现。
- 读者在学习的过程中,可以尝试在检索的方法体内打一些断点看一下具体的执行过程,方便学习整个执行步骤。
五、常见面试题
- 简述字典树的数据结构
- 叙述你怎么来实现一个字典树
- 字典树的实际业务场景举例【排序、全文搜索、网络搜索引擎、生物信息】
- 字典树的存入和检索的时间复杂度
- 还有哪些字典树的实现方式【后缀树、哈希树、帽子树】
相关文章
- 学生数据库管理系统
- SpringDataJpa 用MySQL语句怎么分页,spring全家桶SpringDataJpa 用MySQL语句怎么分页
- Docker创建MySQL容器模板命令
- Elasticsearch对应MySQL的对应关系
- 使用SpringDataJpa保存(save)报错误:SQL Error: 1062, SQLState: 23000 控制台会报:Duplicate entry ‘数‘ for key ‘PRIMA
- Navicat Premium 连接sqlserver数据库时提示安装Client失败,解决方案
- Mysql查询当前用户所有数据库语句(SHOW DATABASES)
- MySQL语句-查看当前数据库有哪些表(SHOW TABLES)
- MySQL5.0版本以上新增的 information_schema 数据库是什么?
- MariaDB数据库备份之逻辑备份
- MariaDB数据库创建用户
- MariaDB数据库给用户授权
- MariaDB数据库刷新权限表命令
- MariaDB数据库删除用户命令
- PhpStudy 2016搭建-sqli-libs靶场
- MySQL手动注入步骤
- Pikachu靶场-SQL注入-数字型注入(post)过关步骤
- Pikachu靶场-SQL注入-字符型注入(get)过关步骤
- 利用SQL注入漏洞实现MySQL数据库读写文件
- Kali-工具-sqlmap常见用法