数据结构：字典树 (Trie)

您所在的位置：网站首页 › 字典树查询时间复杂度 › 数据结构：字典树 (Trie)

数据结构：字典树 (Trie)

2024-02-22 09:46| 来源: 网络整理| 查看: 265

目录导言字典树字典树的性质字典树的应用结点结构体定义插入操作伪代码代码实现查找操作伪代码代码实现简单应用代码实现调试效果情景应用外地人情景解析代码实现参考资料

导言

我们肯定是天天都在用搜索引擎啦，例如我用百度查找资料，会发现当我输入一段字符时，百度就自动跳出了一些热搜关键词，在推荐页面也会想你推荐一些实时热点，这是怎么实现的呢？可以使用类似 map 容器的对象，“键”是关键词，“值”是被搜索的次数，每次需要更新数据时，先找到被搜索的热词，使其的值加 1，然后来个快速排序，但是这种方式需要频繁的对数据进行操作，时间复杂度和空间复杂度都很大，对于一个优秀的搜索引擎来说是绝对不可取的。

字典树

这里就要引入一种更厉害的结构啦——字典树 (Trie)，又称单词查找树、前缀树，是一种树形结构，是一种哈希树的变种。在统计、排序和保存大量的字符串（但不仅限于字符串）是具有更小的时间复杂度，因此可以应用于搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。例如我有 "a"、"apple"、"appeal"、"appear"、"bee"、"beef"、"cat" 这 7 个单词，那么就能够组织成如图所示字典树，如果我们要获取 "apple" 这个单词的信息，那么就按顺序访问对应的结点就行啦。

字典树的性质根节点不包含字符，除根节点外每一个节点都只包含一个字符；从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；每个节点的所有子节点包含的字符都不相同。字典树的应用应用说明字典字符串集合对应一定的信息计算热词统计字符串在集合中出现的个数串的快速检索给出 N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，按最早出现的顺序写出所有不在熟词表中的生词。可以把熟词建成字典树，然后读入文章进行比较，这种方法效率是比较高的。 “串”排序给定N个互不相同的仅由一个单词构成的英文名，将他们按字典序从小到大输出，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可最长公共前缀对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先问题。结点结构体定义

为了更好地理解，这里使用顺序存储结构描述字典树。链式存储结构实现的字典树，在另一篇博客——AC 自动机(Aho-Corasick automaton)有所介绍。假如这个字典只包括 26 个小写英文字母，虽然这个字典可能会容纳贼多、贼长的单词，但是一个结点会有多少种后继是可以确定的，因为对于一个单词而言，任何一位的字母一定是 26 个字母中的一个，我们可以根据需要选择一个字母的后继有几个结点。例如刚才这棵字典树，对于根结点而言，可能会有 26 种后继，但是我的字典里只有 “a”、“b”、“c” 3 种开头的单词，因此我选择这 3 个结点作为根结点的后继。例如图中被标绿色的结点，“appea” 的后继可能是 “l”,“r”，分别表示 "appeal"、"appear" 两个单词。我们的做法是使用顺序存储结构表示树，因此需要先开辟一个足够大的数组，使用静态链表的思想，用游标表示结点的后继。由于我们确定一个结点的后继可能存在 26 个，因此选择开辟一个数组来描述。定义一个包含 26 个后缀指针的结构体，其中再开一个 bool 类型的成语，用于判定是否是单词的结尾。

#define MAXSIZE 26 struct node { bool flag; //若结点是单词的结尾，值为 true，否则为 false int next[MAXSIZE]; //指向后继的游标数组 }trie[1000001]; 插入操作

插入操作，即向字典树中保存一个单词，初始化字典树就是重复地插入已有的单词啦。由于我们使用类静态链表的做法，因此需要用一个游标来定向空闲的空间，在我们需要插入新结点的时候可以拿该游标的元素来使用。当然你可以另外搞一些代码来描述闲置链表，但是字典树很少涉及删除操作，因此忽略。如果你不知道静态链表是啥，可以参考我的另一篇博客静态链表及思想应用。

伪代码

代码实现 void Insert(string str, int &space) { int order; int idx = 1; //从第一层向下挖掘 for (int i = 0; i < str.length(); i++) { order = str[i] - 'a'; //将字符转换为其在字母表的顺序 if (trie[idx].next[order] == 0) //若 idx 没有该字符的子结点 { trie[idx].next[order] = space++; //启用第 space 号结点，拷贝新结点的编号 idx = trie[idx].next[order]; //idx 结点的对应字母的后继为 space trie[idx].flag = false; //标记新结点不是单词的结尾 } else idx = trie[idx].next[order]; //前缀已存在,继续挖掘 } trie[idx].flag = true; //flag 成员设置为 true，表示单词结尾 } 查找操作

查找操作的结构设计与插入操作类似，按照字符串的字母字典序向下访问结点，如果访问到空结点即表示失配，返回 false，需要注意的是即使匹配成功，若字母不为单词的结尾也算失配。

伪代码

代码实现 bool Find(string str) { int order; int idx = 1; //从第一层向下挖掘 for (int i = 0; i < str.length(); i++) { order = str[i] - 'a'; //将字符转换为其在字母表的顺序 if (trie[idx].next[order] == 0) //若字母失配,匹配结束 { return false; } idx = trie[idx].next[order]; //存在对应字母，匹配继续 } if (trie[idx].flag == false) //若成功匹配，但是不为单词结尾 return false; else return true; //单词匹配成功，返回 true } 简单应用

要求构造一个字典树，先输入单词的数量，随后按行输入单词并存入字典树中。接着输入需要匹配的单词数量，随后按行输入需要匹配的单词，匹配成功输出 “YES”，否则输出 “NO”。

代码实现

把上述函数封装好，写个主函数组织一下结构即可：

int main() { int num1, num2; int space = 1; //表示第一个空闲空间的下标 string str; cout > num1; cout num2; cout str; if (Find(str)) cout

【本文地址】

数据结构：字典树 (Trie)

数据结构：字典树 (Trie)

今日新闻

推荐新闻