一 概述
又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。
二 优点
利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
三 性质
(1)根节点不包含字符,除根节点外每一个节点都只包含一个字符;
(2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串;
(3)每个节点的所有子节点包含的字符都不相同。
单词列表为”apps”,”apply”,”apple”,”append”,”back”,”backen”以及”basic”对应的字母树可以是如下图所示。
例如,保存”apple”和 “apply”时,由于它们的前四个字母是相同的,所以希望它们共享这些字母,而只对剩下的部分进行分开存储。可以很明显地发现,字母树很好地利用了串的公共前缀,节约了存储空间。
四 应用
(1)串的快速检索
给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
在这道题中,我们可以用数组枚举,用哈希,用字典树,先把熟词建一棵树,然后读入文章进行比较,这种方法效率是比较高的。
(2)“串”排序
给定N个互不相同的仅由一个单词构成的英文名,让你将他们按字典序从小到大输出用字典树进行排序,采用数组的方式创建字典树,这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。
(3)最长公共前缀
对所有串建立字典树,对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数,于是,问题就转化为当时公共祖先问题。
五 实现
字典树的插入(Insert)、删除( Delete)和查找(Find )都非常简单,用一个一重循环即可,即第 i 次循环找到前 i 个字母所对应的子树,然后进行相应的操作。实现这棵字典树,我们用最常见的数组保存即可,当然也可以开动态的指针类型。至于结点对儿子的指向,一般有三种方法:
(1)对每个结点开一个字母集大小的数组,对应的下标是儿子所表示的字母,内容则是这个儿子对应在大数组上的位置,即标号;
(2)对每个结点挂一个链表,按一定顺序记录每个儿子是谁;
(3)使用左儿子右兄弟表示法记录这棵树。
三种方法,各有千秋。第一种易实现,但实际的空间要求较大;第二种,
较易实现,空间要求相对较小,但比较费时;第三种,空间要求最小,但相对费时且不易写。但总的来说,几种实现方式都是比较简单的,只要在做题时加以合理选择即可。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 26
struct TrieNode{
int count;
TrieNode *next[MAX];
TrieNode(int x):count(x){
for(int i = 0;i < MAX;++i){
next[i] = NULL;
}
}
};
void Insert(TrieNode* &root,string str){
int size = str.size();
int val;
TrieNode *p = root;
for(int i = 0;i < size;++i){
val = str[i] - 'a';
if(p->next[val] == NULL){
p->next[val] = new TrieNode(0);
}
p = p->next[val];
}
p->count++;
}
void Delete(TrieNode* &root,string str){
int size = str.size();
int val;
TrieNode *p = root;
for(int i = 0;i < size;++i){
val = str[i] - 'a';
if(p->next[val] == NULL){
return;
}
p = p->next[val];
}
p->count--;
}
bool Search(TrieNode* root,string str){
if(root == NULL){
return false;
}
int size = str.size();
TrieNode *p = root;
int val;
for(int i = 0;i < size;++i){
val = str[i] - 'a';
if(p->next[val] == NULL){
return false;
}
p = p->next[val];
}
return p->count > 0;
}
void PrintDic(TrieNode* root,vector<vector<char> > &words,vector<char> &word){
if(root == NULL){
return;
}
if(root->count > 0){
words.push_back(word);
}
for(int i = 0;i < 26;++i){
if(root->next[i]){
word.push_back('a'+i);
PrintDic(root->next[i],words,word);
word.pop_back();
}
}
}
int main() {
TrieNode* root = new TrieNode(0);
string strs[] = {"ok","applition","app","apple","apply"};
for(int i = 0;i < 5;++i){
Insert(root,strs[i]);
}
string str("apple");
cout<<"删除单词["<<str<<"]之前查询结果:"<<endl;
if(Search(root,str)){
cout<<"单词["<<str<<"]在字典中"<<endl;
}
else{
cout<<"单词["<<str<<"]不在字典中"<<endl;
}
cout<<"删除单词["<<str<<"]"<<endl;
Delete(root,str);
cout<<"删除单词["<<str<<"]之后查询结果:"<<endl;
if(Search(root,str)){
cout<<"单词["<<str<<"]在字典中"<<endl;
}
else{
cout<<"单词["<<str<<"]不在字典中"<<endl;
}
cout<<"字典列表:"<<endl;
vector<vector<char> > words;
vector<char> word;
PrintDic(root,words,word);
for(int i = 0;i < words.size();++i){
for(int j = 0;j < words[i].size();++j){
cout<<words[i][j];
}
cout<<endl;
}
return 0;
}
六 引用
字典树Trie
算法合集之《浅析字母树在信息学竞赛中的应用》
从Trie树(字典树)谈到后缀树(10.28修订)
有问题欢迎指正,谢谢。。。。。。。
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
字典树:又称为Trie,是一种用于快速检索的多叉树结构。
字典树:又称为Trie,是一种用于快速检索的多叉树结构。Trie把要查找的关键词看作一个字符序列,并根据构成关键词字符的先后顺序构造用于检索的树结构;一棵m度的Trie树或者为空,或者由m棵m度的Trie树构成。
数据结构与算法 课程设计说明书 拼写检查器 trie树 字典树.doc
字典树(Trie)可以保存一些字符串->值的对应关系。基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串。 Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间...
NULL 博文链接:https://auauau.iteye.com/blog/675645
有时,我们会碰到对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(n*lgn),但若采用Trie树,则时间复杂度仅为O(n)
顾名思义,这个可以用于实现字典查找算法。 Trie树就是字符树,其核心思想就是空间换时间。
网上大神的总结,从trie树谈到后缀树,常用的字符串匹配算法
Trie树是搜索树的一种,来自英文单词"Retrieval"的简写,可以建立有效的数据检索组织结构,是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态。在...
什么是Trie树 Trie树通常又称为字典树、单词查找树或前缀树,是一种用于快速检索的多叉树结构。如图数字的字典是一个10叉树: 同理小写英文字母或大写英文字母的字典数是一个26叉树。如上图可知,Trie树的根结点是...
本文实例讲述了Python数据结构与算法之字典树实现方法。分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该...
[原网页] [置顶] 程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大系列集锦 [原网页] 程序员编程艺术第三十~三十一章:字符串转换成整数,通配符字符串...[原网页] 从Trie树(字典树)谈到后缀树(10.28修订)
KMP(字符串匹配),Trie树(字典树),manacher(最长回文子串) 算法思想 代码 经典题目
场景:现在有一个错词库,维护的是错词和正确词对应关系。比如:错词“我门”对应的正确词“我们”。然后在用户输入的文字进行错词校验,需要判断输入的文字是否有错词,并找... Trie树,即字典树,又称单词查找树或键
AC自动机算法的实现。...要搞懂AC自动机,先得有模式树(字典树)Trie和KMP模式匹配算法的基础知识。AC自动机算法分为3步:构造一棵Trie树,构造失败指针和模式匹配过程。本资源简单实现了这些功能。
字典树 trietree 20160624 KMP算法 KMP 20160701 排序算法,插入排序算法、合并排序算法 sort 20160702 MongoDB应用示例 mongoDBDemo 20160703 Redis的java应用示例 JedisDemo 20160704 使用itext读写pdf示例 pdf ...
Algorithms 本次README修订为算法仓库Algorithms的第100次commit,首先我们庆祝自2016年8月4日本仓库建立以来Dev-XYS在算法学习方面取得的显著进步! 这里有各种算法的C++...指针版的字典树 Trie(Pointer)
本文实例讲述了Python实现简单字典树的方法。分享给大家供大家参考,具体如下: #coding=utf8 代码实现了最简单的字典树,只支持由小写字母组成的字符串。 在此代码基础上扩展一下,就可以实现比较复杂的字典树,...
Trie树 二叉查找树 线段树 RMQ LCA+RMQ SB-Tree 数论 生成紧凑素数表 分解质因子 最大公约数 a^b mod n 扩张欧几里德算法 素数表质因子分解 Stirling公式 中国剩余定理 欧拉数(递推法) 欧拉数(公式...
长沙四大名校课件之NOIP 字符串复习,里面包括KMP算法,hash方法,字典树(trie)的具体讲解与题目推荐练习。无论老师授课,还是oier自学,都很方便