文本词频统计的利器 Trie树

简介: 字典树简介Trie树 Trie树一般指字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

字典树简介

Trie树

Trie树一般指字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

性质

它有3个基本性质:

(1)根节点不包含字符,除根节点外每一个节点都只包含一个字符;

(2)从根节点到某节点,路径上经过的字符连接起来,为该节点对应的字符串;

(3)每个节点的所有子节点包含的字符都不相同。

基本操作

                   其基本操作有:查找、插入和删除,当然删除操作比较少见。

实现方法

搜索字典项目的方法为:

(1) 从根结点开始一次搜索;

(2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;

(3) 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。

(4) 迭代过程……

(5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。

其他操作类似处理

应用举例

串的快速检索

给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。

在这道题中,我们可以用数组枚举,用哈希,用字典树,先把熟词建一棵树,然后读入文章进行比较,这种方法效率是比较高的。

“串”排序

给定N个互不相同的仅由一个单词构成的英文名,让你将他们按字典序从小到大输出

用字典树进行排序,采用数组的方式创建字典树,这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

最长公共前缀

对所有串建立字典树,对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数,于是,问题就转化为当时公共祖先问题。


列如 :我们有and,as,at,cn,com这些关键词,将如下建树

网络异常,图片无法展示
|

代码实现:

    trie[root][id]=tot;  root 为 根节点(父节点),id 为子节点或字符的映射,tot 为节点的编号 或者标记

(1)插入操作:

voidinsert(char*s){//插入单词inti,id,len,root=0; len=strlen(s);
for(i=0;i<len;i++){ 
id=s[i]-'a';//按ASCII编号映射(子节点)if(!trie[root][id])trie[root][id]=++tot;没存在字典树中加入编号(标记)root=trie[root][id]; //跟着树分支走    }
}

(2)查询操作:

intsearch(char*s){//查询单词inti,len,id,root=0;len=strlen(s);
for(i=0;i<len;i++){
id=s[i]-'a';//按ASCII 映射 (子节点)if(!trie[root][id])return0;
root=trie[root][id];
    }
return1;
}

(3)删除操作:

      此方法适用标记型插入方法

voiddelete(char*s){//假定s一定存在inti,len,id,root=0;len=strlen(s);
for(i=0;i<len;i++){
id=s[i]-'a';
root=trie[root][id];
    }
trie[root][id]=0;
}
目录
相关文章
|
2月前
|
存储 算法 大数据
Apriori算法和Eclat算法差异
Apriori算法和Eclat算法差异
|
5月前
|
自然语言处理 算法 搜索推荐
分词算法的基本原理及应用
分词算法的基本原理及应用
|
4月前
|
存储 算法 大数据
Apriori算法和Eclat算法在性能上有哪些主要的差异
Apriori算法和Eclat算法在性能上有哪些主要的差异
|
4月前
|
机器学习/深度学习 人工智能 分布式计算
算法金 | 最难的来了:超参数网格搜索、贝叶斯优化、遗传算法、模型特异化、Hyperopt、Optuna、多目标优化、异步并行优化
机器学习中的超参数调优是提升模型性能的关键步骤,包括网格搜索、随机搜索、贝叶斯优化和遗传算法等方法。网格搜索通过穷举所有可能的超参数组合找到最优,但计算成本高;随机搜索则在预设范围内随机采样,降低计算成本;贝叶斯优化使用代理模型智能选择超参数,效率高且适应性强;遗传算法模拟生物进化,全局搜索能力强。此外,还有多目标优化、异步并行优化等高级技术,以及Hyperopt、Optuna等优化库来提升调优效率。实践中,应结合模型类型、数据规模和计算资源选择合适的调优策略。
160 0
算法金 | 最难的来了:超参数网格搜索、贝叶斯优化、遗传算法、模型特异化、Hyperopt、Optuna、多目标优化、异步并行优化
|
4月前
|
人工智能 自然语言处理 算法
|
6月前
|
算法 数据可视化 数据挖掘
Barnes-Hut t-SNE:大规模数据的高效降维算法
Barnes-Hut t-SNE是一种针对大规模数据集的高效降维算法,它是t-SNE的变体,用于高维数据可视化。t-SNE通过保持概率分布相似性将数据从高维降至2D或3D。Barnes-Hut算法采用天体物理中的方法,将时间复杂度从O(N²)降低到O(NlogN),通过构建空间索引树和近似远距离交互来加速计算。在scikit-learn中可用,代码示例展示了如何使用该算法进行聚类可视化,成功分离出不同簇并获得高轮廓分数,证明其在大數據集上的有效性。
116 1
|
6月前
|
机器学习/深度学习 存储 人工智能
图搜索算法详解
【5月更文挑战第11天】本文介绍了图搜索算法的基础知识,包括深度优先搜索(DFS)、广度优先搜索(BFS)和启发式搜索(如A*算法)。讨论了图搜索中的常见问题、易错点及避免方法,并提供了BFS和A*的Python代码示例。文章强调了正确标记节点、边界条件检查、测试与调试以及选择合适搜索策略的重要性。最后,提到了图搜索在路径规划、游戏AI和网络路由等领域的应用,并概述了性能优化策略。
108 3
|
6月前
|
机器学习/深度学习 存储 算法
Faiss为啥这么快?原来是量化器在做怪!1
Faiss为啥这么快?原来是量化器在做怪!
283 0
|
6月前
|
机器学习/深度学习 存储 算法
R语言实现SMOTE与SMOGN算法解决不平衡数据的回归问题
R语言实现SMOTE与SMOGN算法解决不平衡数据的回归问题
106 1
R语言实现SMOTE与SMOGN算法解决不平衡数据的回归问题
|
6月前
|
算法 搜索推荐 网络架构
关联规则分析(算法+画图
关联规则分析(算法+画图
61 0