网站关键词突然没有排名了,台州网页设计,装修网站平台推荐,营销技巧在线观看目录
一.引言
二.Tire 树简介
1.树 Tree
2.二叉搜索树 Binary Search Tree
3.字典树 Trie Tree
3.1 基本概念
3.2 额外信息
3.3 结点实现
3.4 查找与存储
三.Trie 树应用
1.应用场景
2.Java / Scala 实现
2.1 Pom 依赖
2.2 关键词匹配
四.总结 一.引言
Trie 树…
目录
一.引言
二.Tire 树简介
1.树 Tree
2.二叉搜索树 Binary Search Tree
3.字典树 Trie Tree
3.1 基本概念
3.2 额外信息
3.3 结点实现
3.4 查找与存储
三.Trie 树应用
1.应用场景
2.Java / Scala 实现
2.1 Pom 依赖
2.2 关键词匹配
四.总结 一.引言
Trie 树即字典树又称为单词查找树或键树是一种树形结构常用于统计排序和保存大量的字符串所以经常被搜索引擎系统用于文本词频统计。
◆ 优点 - 利用字符串的公共前缀来减少查询时间最大限度地减少无谓的字符串比较查询效率比哈希树高。
◆ 思想 - 其核心思想是空间换时间通过拆分字符串并存储换取查询的高效率 二.Tire 树简介
1.树 Tree 上面是最常见的树的形态其拥有根节点 root有左右的 sub-tree 子树每个父结点 Parent Node 可能拥有子节点 Child Node也有可能没有子节点此时为 None。Siblings 代表同级的兄弟姐妹节点Level 代表树的深度即层数。 2.二叉搜索树 Binary Search Tree 二叉搜索树Binary Search Tree简称 BST又被称为二叉查找树、排序二叉树是指一个空树或者具备下列性质的二叉树
◆ 若任意节点的左子树不为空则左子树上所有节点的值都小于它的根节点的值。
◆ 若任意节点的右子树不为空则右子树上所有节点的值都大于它的根节点的值。
◆ 任意节点的左、右子树也分别为二叉搜索树。
◆ 没有键值相等的节点即相同的元素只能出现一次。
其具备以下特性:
◆ 中序遍历 - 对 BST 进行中序遍历会得到一个有序的序列。这是因为在中序遍历的过程中先访问左子节点较小再访问当前节点最后访问右子节点较大。
◆ 查找效率 - 在 BST 中查找一个元素的平均时间复杂度和树的深度有关理想情况下即 BST 是平衡的时候时间复杂度是 O(log n)其中 n 是树中节点的数量。但是在最坏情况下如树完全不平衡退化成链表查找时间复杂度退化为O(n)。
◆ 插入和删除操作 - 插入和删除也有可能改变树的结构。BST 的插入操作是指在满足上述性质的情况下将一个新节点插入到树中。删除操作则可能涉及到重新调整树的结构以保持二叉搜索树的性质。 3.字典树 Trie Tree
3.1 基本概念 注意这里 Trie 树不是二叉树而是一颗多叉树具体分多少叉要根据我们的实际场景来定。例如我们 Trie 树要存储所有英文单词那理论上每一个父结点 Parent Node 要分 26 个子节点 Child Node因为英文有 26 个英文字母。Trie 树具备如下基本性质:
◆ 结构本身不存储完整单词而是存储每个细粒度的拆分项例如单词搜索则存储字母
◆ 结从根结点到某一结点将路径上的字符相连为该结点对应的字符串
◆ 每个结点的所有子结点路径代表的字符都不相同这里其实代表没有重复字符串结点 3.2 额外信息 每个 Node 结点除了存储对应的字符外其还可以具备其自己的属性最简单的上面的示例中给出了对应字符串的出现频次这可以作为搜索推荐的参考依据如果是代码其额外信息可以作为一个 Class 存在内部包含该节点多个属性例如字符串对应的领域、频率、长度、适用范围等等。 说到词频也让我们想起来 Word2vec 里用到的霍夫曼树其在构造编码时也考虑了词频的因素使得词频高的词可以尽可能快的找到。 3.3 结点实现 这里对于每个 Node 而言结点就不存在 Left 和 Right 的概念了而是直接对应下一个可能的字符串选定哪个字符串就到下一个字符串对应的 Node 上。如果我们认为是简单单词且不区分大小写我们可以认为每个 Node 最多有 26 个分叉结点但如果有更多字符或特殊符号的加入那么多叉树会有更多的分叉。如果一个结点指向 null 代表其没有儿子结点此时连接其路径上的字符即可得到该结点对应的字符串表示。 3.4 查找与存储
◆ 存储
假设是上面提到的英文单词查找且不区分大小写此时最坏的情况为 26 叉树每分叉一次一个结点就多 26 个叉这样的指数分叉对于存储空间还是有很大的消耗。
◆ 查找 相比于存储的消耗查找的速度会快很多因为查找的次数是和单词的字符量匹配的常见的英文单词字符量在 10 左右那我们只需要 10 次的常数时间就可以查到以 you 为例只需要 3 步就可以找到。但如果是用二分查找等方法由于整个字典集的数量 n 特别大即使排好序也是 Log(n) 的查找效率会比 Trie 树查找次数多很多。这也体现了我们开头说的 Trie 树的核心思想: 空间换时间。其实这个概念不光是 Trie 树很多算法都会用到这个思想将时间复杂度降低空见复杂度提升。 三.Trie 树应用
1.应用场景 因为 Trie 树公共前缀的使用 所以它十分适合搜索与输入法拓展等领域当我们输入了前面的公共前缀其可以根据词频很容易的给出后面的候选。 实际场景中应用较多的是 Aho-Corasick 算法其适用于确定性的、完全匹配的字符串搜索场景它能够高效地检测出预定义的关键词是否在给定文本中出现。针对每一次输入算法都能找出所有存在的关键词匹配。 2.Java / Scala 实现
2.1 Pom 依赖 !-- https://mvnrepository.com/artifact/org.ahocorasick/ahocorasick --dependencygroupIdorg.ahocorasick/groupIdartifactIdahocorasick/artifactIdversion0.6.3/version/dependency 2.2 关键词匹配
import org.ahocorasick.trie.{Emit, Token, Trie}// 初始化并构建Trieval trie Trie.builder().addKeyword(hers).addKeyword(his).addKeyword(she).addKeyword(he).build()// 搜索文本val text she sells sea shells by the sea shore// 执行搜索val tokens: java.util.Collection[Token] trie.tokenize(text)// 注意这里使用Java转Scala的集合转换import scala.collection.JavaConverters._for (token - tokens.asScala) {if (token.isMatch) {// 打印匹配的词条和位置println(sFound match: ${token.getFragment} at position ${token.getEmit.getStart})}}
- addKeyword 用于添加关键词到 Trie 树中
- text 为代分析的文本
- tokenize 方法分析文本进行关键词匹配
- isMatch getFragment 获取命中的关键词getEmit.getStart 与 getEnd 用于获取 Fragment 片段在 text 中的起始位置 实战场景下Builder 过程中会添加一个很大的字典内容构造 Trie 树随后应用 Trie 树进行文本的关键词匹配判断目标文本是否命中字典中给定的关键字。 四.总结
上面就是 Trie 树的简单介绍与应用。如果想要开发类似 Google 的关键词搜索推荐系统要比使用简单的 Aho-Corasick 算法要复杂得多并且可能需要依赖机器学习和大数据处理技术。 如果你只是想实现一个简单版本的搜索推荐系统可以考虑一些基础的模糊匹配算法或使用现有的搜索引擎库比如 Elasticsearch它内置了自动补全和模糊匹配的功能同时 Elasticsearch 也能够通过集群分布式架构来处理大规模数据集非常适用于构建搜索推荐系统。
