负责做网站的叫什么公司,wordpress 下载模板站,wordpress关闭网站,杭州建站程序作者 | 神奕来源 | 前端应届生头图 | 下载于视觉中国出品 | CSDN云计算#xff08;ID#xff1a;CSDNcloud#xff09;在计算机科学中#xff0c;trie#xff0c;又称前缀树或字典树#xff0c;是一种有序树#xff0c;用于保存关联数组#xff0c;其中的键通常是字符串… 作者 | 神奕来源 | 前端应届生头图 | 下载于视觉中国出品 | CSDN云计算IDCSDNcloud在计算机科学中trie又称前缀树或字典树是一种有序树用于保存关联数组其中的键通常是字符串。与二叉查找树不同键不是直接保存在节点中而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀也就是这个节点对应的字符串而根节点对应空字符串。什么是Trie树Trie树又叫字典树、前缀树Prefix Tree、单词查找树 或 键树是一种多叉树结构。如下图上图是一棵Trie树表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质根节点不包含字符除根节点外的每一个子节点都包含一个字符。从根节点到某一个节点路径上经过的字符连接起来为该节点对应的字符串。每个节点的所有子节点包含的字符互不相同。通常在实现的时候会在节点结构中设置一个标志用来标记该结点处是否构成一个单词关键字。可以看出Trie树的关键字一般都是字符串而且Trie树把每个关键字保存在一条路径上而不是一个结点中。另外两个有公共前缀的关键字在Trie树中前缀部分的路径相同所以Trie树又叫做前缀树Prefix Tree。Trie树的优缺点Trie树的核心思想是空间换时间利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。优点插入和查询的效率很高都为O(m)O(m)其中 mm 是待插入/查询的字符串的长度。关于查询会有人说 hash 表时间复杂度是O(1)O(1)不是更快但是哈希搜索的效率通常取决于 hash 函数的好坏若一个坏的 hash 函数导致很多的冲突效率并不一定比Trie树高。Trie树中不同的关键字不会产生冲突。Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。Trie树不用求 hash 值对短字符串有更快的速度。通常求hash值也是需要遍历字符串的。Trie树可以对关键字按字典序排序。缺点当 hash 函数很好时Trie树的查找效率会低于哈希搜索空间消耗比较大。Trie树的应用1、字符串检索检索/查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较如果沿路比较发现不同的字符则表示该字符串在集合中不存在。如果所有的字符全部比较完并且全部相同还需判断最后一个节点的标志位标记该节点是否代表一个关键字。struct trie_node
{bool isKey; // 标记该节点是否代表一个关键字trie_node *children[26]; // 各个子节点
};2、词频统计Trie树常被搜索引擎系统用于文本词频统计 。struct trie_node
{int count; // 记录该节点代表的单词的个数trie_node *children[26]; // 各个子节点
};思路为了实现词频统计我们修改了节点结构用一个整型变量count来计数。对每一个关键字执行插入操作若已存在计数加1若不存在插入后count置1。注意第一、第二种应用也都可以用 hash table 来做。3、字符串排序Trie树可以对大量字符串按字典序进行排序思路也很简单遍历一次所有关键字将它们全部插入trie树树的每个结点的所有儿子很显然地按照字母表排序然后先序遍历输出Trie树中所有关键字即可。4、前缀匹配例如找出一个字符串集合中所有以ab开头的字符串。我们只需要用所有字符串构造一个trie树然后输出以a-b-开头的路径上的关键字即可。trie树前缀匹配常用于搜索提示。如当输入一个网址可以自动搜索出可能的选择。当没有完全匹配的搜索结果可以返回前缀最相似的可能。5、作为其他数据结构和算法的辅助结构如后缀树AC自动机等。Trie树的实现这里为了方便我们假设所有的关键字都由 a-z 的字母组成。下面是 trie 树的一种典型实现#include iostream
#include string
using namespace std;#define ALPHABET_SIZE 26typedef struct trie_node
{int count; // 记录该节点代表的单词的个数trie_node *children[ALPHABET_SIZE]; // 各个子节点
}*trie;trie_node* create_trie_node()
{trie_node* pNode new trie_node();pNode-count 0;for(int i0; iALPHABET_SIZE; i)pNode-children[i] NULL;return pNode;
}void trie_insert(trie root, char* key)
{trie_node* node root;char* p key;while(*p){if(node-children[*p-a] NULL){node-children[*p-a] create_trie_node();}node node-children[*p-a];p;}node-count 1;
}/*** 查询不存在返回0存在返回出现的次数*/
int trie_search(trie root, char* key)
{trie_node* node root;char* p key;while(*p node!NULL){node node-children[*p-a];p;}if(node NULL)return 0;elsereturn node-count;
}int main()
{// 关键字集合char keys[][8] {the, a, there, answer, any, by, bye, their};trie root create_trie_node();// 创建trie树for(int i 0; i 8; i)trie_insert(root, keys[i]);// 检索字符串char s[][32] {Present in trie, Not present in trie};printf(%s --- %s\n, the, trie_search(root, the)0?s[0]:s[1]);printf(%s --- %s\n, these, trie_search(root, these)0?s[0]:s[1]);printf(%s --- %s\n, their, trie_search(root, their)0?s[0]:s[1]);printf(%s --- %s\n, thaw, trie_search(root, thaw)0?s[0]:s[1]);return 0;
}对于Trie树我们一般只实现插入和搜索操作。这段代码可以用来检索单词和统计词频。博文链接blog.csdn.net/lisonglisonglisong/article/details/45584721
CSDN协同行业大佬
打造13长热门知识图谱及IT成长路线
助力千万IT人成长快速实现职场进阶
更多精彩推荐
☞经典永不过时重温设计模式☞PassMark 更新排行苹果 M1 杀疯了☞干货Redis集群工作原理解析点分享点收藏点点赞点在看
