「javatire树」java trie树

今天给各位分享javatire树的知识，其中也会对java trie树进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、做一个完整的搜索引擎要学什么编程技术和知识
• 2、那些经典算法：AC自动机
• 3、详谈树结构（传统树、字典树、hash 树、Merkle Patricia Tree）
• 4、java如何实现拼音首字母检索汉字

做一个完整的搜索引擎要学什么编程技术和知识

TCP/IP协议，HTTP协议，前端编程，服务端编程，网络编程，数据库原理，爬虫，自动机，Tire树，数据挖掘，机器学习，自然语言处理等

那些经典算法：AC自动机

第一次看到这个名字的时候觉得非常高级，深入学习就发现，AC就是一种多模式字符串匹配算法。前面介绍的BF算法，RK算法，BM算法，KMP算法都属于单模式匹配算法，而Trie树是多模式匹配算法，多模式匹配算法就是在一个主串中查找多个模式串，举个最常用的例子，比如我们在论坛发表评论或发帖的时候，一般论坛后台会检测我们发的内容是否有敏感词，如果有敏感词要么是用***替换，要么是不让你发送，我们评论是通常是一段话，这些敏感词可能成千上万，如果用每个敏感词都在评论的内容中查找，效率会非常低，AC自动机中，主串会与所有的模式串同时匹配，这时候就可以利用AC自动机这种多模式匹配算法来完成高效的匹配，

AC自动机算法是构造一个Trie树，然后再添加额外的失配指针。这些额外的适配指针准许在查找字符串失败的时候进行回退（例如在Trie树种查找单词bef失败后，但是在Trie树种存中bea这个单词，失配指针会指向前缀be），转向某些前缀分支，免于重复匹配前缀，提高算法效率。

常见于IDS软件或病毒检测软件中病毒特征字符串，可以构建AC自动机，在这种情况下，算法的时间复杂度为输入字符串的长度和匹配数量之和。

假设现有模式字符串集合：{abd,abdk, abchijn, chnit, ijabdf, ijaij} 构建AC自动机如下：

说明：

1）当前指针curr指向AC自动机的根节点：curr=root。

2）从文本串中读取（下）一个字符。

3）从当前节点的所有孩子节点中寻找与该字符匹配的节点：

4）若fail == null，则说明没有任何子串为输入字符串的前缀，这时设置curr = root，执行步骤2.

若fail != null,则将curr指向 fail节点，指向步骤3。

理解起来比较复杂，找网上的一个例子，假设文本串text = “abchnijabdfk”。

查找过程如下：

说明如下：

1）按照字符串顺序依次遍历到：a--b--c--h ,这时候发现文本串中下一个节点n和Trie树中下一个节点i不匹配，且h的fail指针非空，跳转到Trie树中ch位置。

注意c--h的时候判断h不为结束节点，且c的fail指针也不是结束节点。

2）再接着遍历n--i,发现i节点在Trie树中的下一个节点找不到j，且有fail指针，则继续遍历，

遍历到d的时候要注意，d的下一个匹配节点f是结束字符，所以得到匹配字符串：ijabdf，且d的fail节点也是d，且也是结束字符，所以得到匹配字符串abd，不过不是失败的匹配，所以curr不跳转。

先将目标字符串插入到Trie树种，然后通过广度有限遍历为每个节点的所有孩子节点找到正确的fail指针。

具体步骤如下：

1）将根节点的所有孩子节点的fail指针指向根节点，然后将根节点的所有孩子节点依次入队列。

2）若队列不为空：

2.1）出列一个字符，将出列的节点记为curr，failTo表示curr的

fail指针，即failTo = curr.fail 。

2.2) 判断curr.child[i] == failTo.child[i]是不是成立：

成立：curr.child[i].fail = failTo.child[i]

因为当前字符串的后缀和Tire树的前缀最长部分是到fail，

且子字符和failTo的下一个字符相同，则fail指针就是

failTo.child[i]。

不成立： 判断failTo是不是为null是否成立：

成立： curr.child[i].fail = root = null。

不成立： failTo = failTo.fail 继续2.2

curr.child[i]入列，再次执行步骤2）。

3）队列为空结束。

每个结点的fail指向的解决顺序是按照广度有限遍历的顺序完成的，或者说层序遍历的顺序进行，我们根据父结点的fail指针来求当前节点的fail指针。

上图为例，我们要解决y节点的fail指针问题，已经知道y节点的父节点x1的fail是指向x2的，根据fail指针的定义，我们知道红色椭圆中的字符串序列肯定相等，而且是最长的公共部分。依据y.fail的含义，如果x2的某个孩子节点和节点y表示的表示的字符相等，y的fail就指向它。

如果x2的孩子节点中不存在节点y表示的字符。由于x2.fail指向x3，根据x2.fail的含义，我们知道绿色框中的字符序列是相同的。显然如果x3的某个孩子和节点y表示字符相等，则y.fail就指向它。

如果x3的孩子节点不存在节点y表示的字符，我们重复这个步骤，直到xi的fail节点指向null，说明我们达到顶层，只要y.fail= root就可以了。

构造过程就是知道当前节点的最长公共前缀的情况下，去确定孩子节点的最长公共前缀。

下图中，每个节点都有fail虚线，指向根节点的虚线没画出，求图中c的孩子节点h的fail指向：

原图中，深蓝色的框出来的是已经确定fail指针的，求红色框中h节点的fail指针。

这时候，我们看下h的父亲节点c的fail指针指向，为ch中的c（这表示abc字符串的所有后缀bc和c和Trie树的所有前缀中最长公共部分为c），且这个c节点的孩子节点中有字符为h的字符，所以图中红色框中框出的h节点的fail指针指向 ch字符串中的h。

求红色框中i的fail指针指向，上图中，我们可以看到i的父亲节点h的指向为ch中的h，（也就是说我们的目标字符串结合中所有前缀和字符序列abch的所有后缀在Trie树中最长前缀为ch。）我们比较i节点和ch中的h的所有子节点，发现h只有一个n的子节点，所以没办法匹配，那就继续找ch中h的fail指针，图中没画出，那么就是它的fail指针就是root，然后去看root所有子节点中有没有和i相等的，发现最右边的i是和我们要找的i相等的，所以我们就把i的fail指针指向i，如后面的图。

详谈树结构（传统树、字典树、hash 树、Merkle Patricia Tree）

本文参考： 树结构参考文献

[图片上传失败...(image-83b557-1539180310707)]

[图片上传失败...(image-d6bf01-1539180310707)]

性质1. 节点是红色或黑色，根是黑色，所有叶子都是黑色

性质2. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点，即红黑相间)，从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点(简称黑高)。

[图片上传失败...(image-52c714-1539180310707)]

B+树是B树的变体，也是一种多路搜索树：

[图片上传失败...(image-c2ce8e-1539180310707)]

B+ 树的性质：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4. 更适合文件索引系统。

所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

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

Tire树的三个基本性质：

Tire树的应用：

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

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

[图片上传失败...(image-f00bd3-1539180310707)]

[图片上传失败...(image-d70c23-1539180310707)]

[图片上传失败...(image-8a3963-1539180310707)]

[图片上传失败...(image-69461e-1539180310707)]

[图片上传失败...(image-987993-1539180310707)]

[图片上传失败...(image-58f33c-1539180310707)]

参考文献：

1、

2、

3、

4、

java如何实现拼音首字母检索汉字

使用pinyin4j或者jpinyin的，先将汉字转换为拼音，然后记录拼音的首字母，具体的检索过程可以用循环过滤，也可以用前缀树 比如tire树

参考链接：

网页链接 java实现汉字转拼音

网页链接 tire树

javatire树的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java trie树、javatire树的信息别忘了在本站进行查找喔。