算法字典树

Ⅰ 怎么做字典树

Tries树是典型的用空间换时间的算法。
如果要查找字符串，就算是hash，最快也要比较一次该单词(遍历一次该单词)，而通常冲突是不可避免的。
Tries树通过一颗二十六叉树来存储字典。
结点是这样的:
struct node{
type data;

node* next[26];
int flag;

};
比如字符串acfg
那么首先用root节点(这里置空)，判断node->['a'-‘a'](node初始为root)是否为空，如果不为空，则
node = node->['a'-'a']....依次到最后一个字母g，如果标记flag为1(表示是个单词，避免只是另一个单词的字串，比如acfgd;

Ⅱ 数据结构与算法中，树一般会应用在哪些方面为什么

基础类：二叉搜索（排序）树，线索二叉树，哈夫曼树（最优二叉树），二叉堆
平衡树类：AVL，红黑树，2-3树，2-3-4树，B树，B+树，B-树，treap，SBT。
优先队列类：左高树（左偏树，可并堆，斜堆），双端堆，斐波那契堆
集合类：并查集
区间树类：线段树，划分树，归并树，树状数组
字母树类：字典树，后缀树。AC自动机算法
动态树类：伸展树
计算几何类：KD-tree （块状树），4叉树
RMQ转LCA：笛卡尔树
图论相关：最小生成树，无根树
其它：败者树，博弈树

Ⅲ 字典树和二叉树区别

字典树和二叉树区别有。
1、字典树，是一种空间换时间的数据结构，又称Trie树、前缀树，是一种树形结构(字典树是一种数据结构)，典型用于统计、排序、和保存大量字符串。
2、二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，是树也能简单地转换为二叉树，而二叉树的存储结构及其算法都较为简单，二叉树显得很重要。二叉树特点是每个结点最多只能有两棵子树。

Ⅳ 怎样做字典树

What's on the tree?
There is an dictionary on the book

Ⅳ 算法导论：后缀树

参考资料：
在线构造后缀树
Ukkonen's Algorithm构造后缀树实录
后缀树系列
在阅读本文之前，需要了解字典树，请看 字典树

下面将对后缀树的构建以及优化做出详细的介绍。

以字符串S=MISSISSIPPI$为例
S的所有后缀如下：
S[0…11]= MISSISSIPPI$           字符串本身，起始位置0
S[1…11]=   ISSISSIPPI$            起始位置1
S[2…11]=  SSISSIPPI$            起始位置2
S[3…11]=    SISSIPPI$            起始位置3
   .
   .
S[10…11]=         I$           起始位置10
S[11…11]=        $            终结符
字符串最后的$是人为添加的，这样保证后缀的唯一性，不会出现横跨多个字符串的后缀。

（1）将上述字符串的所有后缀加入到字典树中，得到如下结构：

（2）将字典树中没有分支的路径压缩：

这种方法的含义就是给定一个字符串，直接构造后缀树，不需要先构造字典树。
在讲这个方法之前，需要先了解一些概念：

在这里后缀树中的结点分为两大类，显示结点，隐士结点。显示节点就是那些分支处或者叶子节点，隐式节点是被压缩的那些节点。还有用来辅助构造后缀树的尾部链表，构造时，会沿着尾部链表进行更新。

首先第一个字符a开始，构建如图所示，尾部链表从a的叶子节点指向根节点。现在我们插入下一个字符b，插入字符时说沿着链表进行更新的，这里先更新叶子节点，再更新根节点这个内部节点。

现在插入字符b

是在方法二的基础上进行的优化，下面将哟用具体的例子进行讲解，给出的字符串为abcabxabcd$。

首先构建字符a

我们在按规则插入之后，要在字符a后做一个标记，就像之前讲的隐式结点，表示出有由a开始的后缀，a之后的字符就可以在这里操作。
为了记录这些信息，我们需要引入一些概念：
1、活动点（active point)
是一个三元组(活动结点,活动边, 活动长度)
2、剩余后缀数（remainder）
还没有在后缀树中体现的后缀
  那对于上图，活动点是多少呢？答案是（0，a，1）0表示额就是根节点，在这个结点上进行活动。a表示的是会在由根节点周围a开始的那条边上进行相关操作，1表示的是在一位字符后操作，也就是a后，如果是2呢那就是在b后操作。
  此时还没有体现在后追树上的后缀数是1.也就是后缀a，因为我们并不能找到a这个后缀，我们只是在a后做了标记，表示接下来会有由a开始的标记。

此时活动点变为了（0（根节点），none(无活动边)，0(无长度)）,剩余的后缀是x。
我们会发现图中多了一条=由4指向6的索引。这个就是另一条规则。

在根据规则处理完所有的字符后，得到如图所示的后缀树，因为在整个过程中，只遍历了一遍字符串，且没有进行多余的结点操作，只是记录了一些信息，所以这个方法的时间复杂度是O(n)，可以在线性时间内完成。

Ⅵ 图解：数据结构与算法之字典树

字典树（Trie树）这一数据结构是不太常见但是十分好用<typo id="typo-32" data-origin="而" ignoretag="true">而</typo>一种数据结构，博主也就是最近一段时间做了几道字节的题目才了解到字典树这一数据结构。并将自己的学习内容跟大家分享。

首先，何为字典树（Trie树）？顾名思义，就是在查询目标时，像字典一样按照一定排列顺序标准和步骤访问树的节点，举一个简单例子，英文字典查单词"He"，那么第一步你肯定要按照a-z的顺序先找到h这个首字母，然后再按照相同顺序找到e。博主所要介绍的字典树就是类似字典这样的结构。

上述查找单词的过程就是不断查找与所查单词相同前缀的字符串，直至查找到所查单词的最后一个字母。因此，字典树又称为前缀树(prefix Tree)。

以hell、hi、new、nop为例建立一个字典树，构造如下

根据上文所述可以得到字典树的结构性质

根据以上三点来构造字典树。

字典树的构造其实较为简单，和一般树的构造没有太大区别。接下来将对字典树的插入、删除、查询操作进行分析与讲解。

在没有字典树的时候，我们需要先构建出字典树。

以插入hell为例：

再插入单词hit，过程如下，检查＝>存在则访问/不存在则建立新节点再访问＝>直到要插入的单词到达最后一个字符。

字典树的插入操作比较简单，不需要考虑太多排序问题。

正如上文所说，按照一定的标准进行查询目标字符串，每个节点都储存一个字符，根节点到达子节点路径组成的字符串即为该节点所对应的字符串，那么查询目标字符串时按照从根节点一步一步访问相应字符所在的节点，其实也就是匹配字符串前缀的过程。

如下图，在字典树中，查询"hell"，

[图片上传失败...(image-f028c4-1611057619223)]

如果在该字典中查询no

删除操作相对于插入与查询复杂一点，但是也很简单，删除的前提是单词已经存在于字典树。

删除字典树节点的操作需要考虑目标字符串最后一个字符是否是树中的叶子节点。

因为一个单词可能是另一个单词的前缀部分，如果不是叶子节点，我们只需要把该单词的单词标志位清空即可，无需删除整个“树枝”。

比如，想要删除"no"这个单词

比如，想要删除"hell"这个单词，与第一种删除相同，只不过是从最后一个节点，'l'节点是叶子节点，开始往上进行节点删除操作。

比如，想要删除"hi",那么与前两种其实一致，访问到叶子节点'i',删除叶子节点，并向上访问，访问到'h'，由于删除'i'以后，'h'依然不是叶子节点，因此不再继续删除节点。

比如，想要删除"nop",与前几种类似，先访问到叶子节点'p'删除，然后上移发现'o'是叶子节点，然而'o'有单词标记位，所以，这里不再继续删除。

有上面几种删除操作，我们得到了删除的标准：

了解了这么多字典树的各种操作，相信你对字典树的用途有个大概了解了，字典树最大作用是用于==字符串的各种匹配==，前缀匹配（模糊搜索），字符串查找（字典）等等。

博主只打出了“涓涓清泉”四个关键字，其搜索列表返回了诸多以涓涓清泉为首的选项

顾名思义，就是一个单纯的字典而已，不多举例。

字典树的构建，通过利用空间换时间的思想以及字符串的公共前缀减少无效的字符串比较操作从而使得插入和查找字符串变得高效．其插入或者查找的时间复杂度为O(n)，n为字符串长度。

当然，字典树有着它的弊端，当所插入的单词没有很多公共前缀时，字典树的构建变得十分复杂和低效。

字典树的难度不是很大，但却是一种十分有用的数据结构，掌握之后，对于解决一些有关字符串匹配、公共前缀的问题十分有帮助。

当然我们也说了，字典树有着自己的弊端，由于用空间换时间，如果遇到了一堆公共前缀很少的单词进行字典树构造时，空间需求就显得十分大了。

Ⅶ 算法笔记之前缀树——字典序的第K小数字

前缀树（字典树）的一种应用场景，和传统的前缀树使用不太一样，但是使用了其中的思想。

LeetCode 440. 字典序的第K小数字

定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

题目描述比较简单，据说这是字节跳动面试喜欢出的一道题。

首先简单解释下，字典序就是1、10、11、12这样按照类似字典一样的字符顺序排序数字。

既然要用前缀树的思想，那么我们先把前缀树画出来。

我们可以看到相同前缀的数字可以放到一个子树里，子树的每个层级依次有1、10、100...个节点。

我们可以先判断数字k属于哪个子树，然后在当前子树往下一层级移动。然后重复找子树和往下层移动的过程，直到找到节点（也就是数字）。

Ⅷ 数据结构与算法中，树一般会应用在哪些方面为什么

数据结构就不多说了，树以递归性质这一对计算机而言最普遍的描述结构简直贯穿始终。查找树字典树四叉树哪个都是树的实际应用。除了低维结构不用树描述（其实一维结构也可以看成是退化后的树）。

算法层面，树基本上到处都是（当然有些时候是隐性的）。计算机执行指令是线性的，程序代码也是顺序的，是个一维结构，一旦需要解决高维问题，利用栈、队列等一维基础结构所能做到的只有树，而树则可以用来描述高维逻辑，起到了个桥梁作用。

算法举例如下。
状态空间遍历类：DFS、BFS

决策类：各种自动机（特例还有退化为一位情况的KMP）、贪心、分治、动态规划（同属状态空间遍历）、匹配
图与流：寻路（最短路）、生成树

应用举例就更多了，例如XML、DOM树、编译器中的模式识别和语法树、JSON数据传递、磁盘路径结构……

树的普遍取决于它的结构与通常解决问题的算法的一致性和结构简单严谨：递归定义、拓扑有序（无环）、实现简单。当面临高维状态时，其它结构的处理方式几乎一定不如转化为树来的简单，所以就成为了组织一维实现与高维逻辑中的桥梁。

Ⅸ 自然语言处理（NLP）的基础难点：分词算法

自然语言处理（NLP，Natural Language Processing）是人工智能领域中的一个重要方向，主要研究人与计算机之间用自然语言进行有效通信的各种理论和方法。自然语言处理的底层任务由易到难大致可以分为词法分析、句法分析和语义分析。分词是词法分析（还包括词性标注和命名实体识别）中最基本的任务，也是众多NLP算法中必不可少的第一步，其切分准确与否往往与整体结果息息相关。

金融领域分词的难点

分词既简单又复杂。简单是因为分词的算法研究已经很成熟了，大部分的算法（如HMM分词、CRF分词）准确率都可以达到95%以上；复杂则是因为剩下的5%很难有突破，主要可以归结于三点：

▲粒度，即切分时的最小单位，不同应用对粒度的要求不一样，比如“融资融券”可以是一个词也可以是两个词

▲歧义，比如“恒生”一词，既可指恒生公司，又可指恒生指数

▲未登录词，即未出现在算法使用的词典中的词，比如不常见的专业金融术语，以及各种上市公司的名称

在金融领域中，分词也具有上述三个难点，并且在未登录词方面的难点更为突出，这是因为金融类词汇本来就多，再加上一些专有名词不仅有全称还有简称，这就进一步增大了难度。

在实际应用中，以上难点时常会造成分词效果欠佳，进而影响之后的任务。尤其是在一些金融业务中，有许多需要与用户交互的场景，某些用户会用口语化的词汇描述业务，如果分词错误会影响用户意图的解析，这对分词的准确性提出了更高的要求。因此在进行NLP上层应用开发时，需要对分词算法有一定的了解，从而在效果优化时有能力对分词器进行调整。接下来，我们介绍几种常用的分词算法及其应用在金融中的优劣。

几种常见的分词算法

分词算法根据其核心思想主要分为两种：

第一种是基于字典的分词，先把句子按照字典切分成词，再寻找词的最佳组合方式，包括最大匹配分词算法、最短路径分词算法、基于N-Gram model的分词算法等；

第二种是基于字的分词，即由字构词，先把句子分成一个个字，再将字组合成词，寻找最优的切分策略，同时也可以转化成序列标注问题，包括生成式模型分词算法、判别式模型分词算法、神经网络分词算法等。

最大匹配分词寻找最优组合的方式是将匹配到的最长词组合在一起，主要的思路是先将词典构造成一棵Trie树（也称为字典树），Trie树由词的公共前缀构成节点，降低了存储空间的同时可以提升查找效率。

最大匹配分词将句子与Trie树进行匹配，在匹配到根结点时由下一个字重新开始进行查找。比如正向（从左至右）匹配“他说的确实在理”，得出的结果为“他／说／的确／实在／理”。如果进行反向最大匹配，则为“他／说／的／确实／在理”。

这种方式虽然可以在O(n)时间对句子进行分词，但是只单向匹配太过绝对，尤其是金融这种词汇较丰富的场景，会出现例如“交易费/用”、“报价单/位”等情况，所以除非某些词的优先级很高，否则要尽量避免使用此算法。

最短路径分词算法首先将一句话中的所有词匹配出来，构成词图（有向无环图DAG），之后寻找从起始点到终点的最短路径作为最佳组合方式，例：

我们认为图中每个词的权重都是相等的，因此每条边的权重都为1。

在求解DAG图的最短路径问题时，总是要利用到一种性质：即两点之间的最短路径也包含了路径上其他顶点间的最短路径。比如S->A->B->E为S到E到最短路径，那S->A->B一定是S到B到最短路径，否则会存在一点C使得d(S->C->B)<d(S->A->B)，那S到E的最短路径也会变为S->C->B->E，这就与假设矛盾了。利用上述的最优子结构性质，可以利用贪心算法或动态规划两种求解算法：

（1）基于Dijkstra算法求解最短路径，该算法适用于所有带权有向图，求解源节点到其他所有节点的最短路径，并可以求得全局最优解；

（2）N-最短路径分词算法，该方法是对Dijkstra算法的扩展，在每一步保存最短的N条路径，并记录这些路径上当前节点的前驱，在最后求得最优解时回溯得到最短路径。这种方法的准确率优于Dijkstra算法，但在时间和空间复杂度上都更大。

相较于最大匹配分词算法，最短路径分词算法更加灵活，可以更好地把词典中的词组合起来，能更好地解决有歧义的场景。比如上述“他说的确实在理”这句话，用最短路径算法的计算结果为“他／说／的／确实／在理”，避免了正向最大匹配的错误。但是对于词典中未存在的词基本没有识别能力，无法解决金融领域分词中的“未登录词”难点。

N-Gram（又称N元语法模型）是基于一个假设：第n个词出现与前n-1个词相关，而与其他任何词不相关。在此种假设下，可以简化词的条件概率，进而求解整个句子出现的概率。

现实中，常用词的出现频率或者概率肯定比罕见词要大。因此，可以将求解词图最短路径的问题转化为求解最大概率路径的问题，即分词结果为“最有可能的词的组合“。

计算词出现的概率，仅有词典是不够的，还需要充足的语料，所以分词任务已经从单纯的“算法”上升到了“建模”，即利用统计学方法结合大数据挖掘，对“语言”（句子出现的概率）进行建模。

我们将基于N-gram模型所统计出的概率分布应用到词图中，可以得到词的概率图。对该词图用最短路径分词算法求解最大概率的路径，即可得到分词结果。

相较于前两种分词算法，基于N-Gram model的分词算法对词频进行了统计建模，在切分有歧义的时候力求得到全局最优值，比如在切分方案“证券/自营/业务”和“证券/自/营业/务”中，统计出“证券/自营/业务”出现的概率更大，因此结果有更高的准确率。但也依然无法解决金融场景中未登录词的问题。

生成式模型主要有隐马尔可夫模型（HMM，Hidden Markov Model）、朴素贝叶斯分类等。HMM是常用的分词模型，基于Python的jieba分词器和基于Java的HanLP分词器都使用了HMM。

HMM模型认为在解决序列标注问题时存在两种序列，一种是观测序列，即人们显性观察到的句子，另一种是隐状态序列，即观测序列的标签。假设观测序列为X，隐状态序列是Y，则因果关系为Y->X。因此要得到标注结果Y，必须对X的概率、Y的概率、P(X|Y)进行计算，即建立P(X,Y)的概率分布模型。

HMM算法可以在一定程度上解决未登录词的问题，但生成式模型的准确率往往没有接下来要谈到的判别式模型高。

判别式模型主要有感知机、支持向量机（SVM，Support Vector Machine）、条件随机场（CRF，Conditional Random Field）、最大熵模型等，其中感知机模型和CRF模型是常用的分词模型。

（1）平均感知机分词算法

感知机是一种简单的二分类线性模型，通过构造超平面，将特征空间（输入空间）中的样本分为正负两类。通过组合，感知机也可以处理多分类问题。但由于每次迭代都会更新模型的所有权重，被误分类的样本会造成很大影响，因此采用平均的方法，在处理完一部分样本后对更新的权重进行平均。

（2）CRF分词算法

CRF可以看作一个无向图模型，假设给定的标注序列为Y，观测序列为X，CRF对条件概率P(Y|X)进行定义，而不是对联合概率建模。

平均感知机算法虽然速度快，但仍不够准确。适合一些对速度要求高、对准确性要求相对不那么高的场景。CRF分词算法可以说是目前最常用的分词、词性标注和实体识别算法，它对未登陆词也有很好的识别能力，是目前在速度、准确率以及未登录词识别上综合表现最突出的算法，也是我们目前所采用的解决方案，但速度会比感知机慢一些。

在NLP中，最常用的神经网络为循环神经网络（RNN，Recurrent Neural Network），它在处理变长输入和序列输入问题中有着巨大的优势。LSTM（Long Short-Term Memory，长短期记忆网络）为RNN变种的一种，在一定程度上解决了RNN在训练过程中梯度消失和梯度爆炸的问题。

目前对于序列标注任务，业内公认效果最好的模型是BiLSTM+CRF。相比于上述其它模型，双向循环神经网络BiLSTM，可以更好地编码当前字等上下文信息，并在最终增加CRF层，核心是用Viterbi算法进行解码，以得到全局最优解，避免B,S,E这种不可能的标记结果的出现，提高准确率。

神经网络分词虽然能在准确率、未登录词识别上有更好的表现，但RNN无法并行计算，在速度上没有优势，所以该算法通常在算法研究、句子精确解析等对速度要求不高的场景下使用。

分词作为NLP底层任务之一，既简单又重要，很多时候上层算法的错误都是由分词结果导致的。因此，对于底层实现的算法工程师，不仅需要深入理解分词算法，更需要懂得如何高效地实现和调试。

而对于上层应用的算法工程师，在实际分词时，需要根据业务场景有选择地应用上述算法，比如在搜索引擎对大规模网页进行内容解析时，对分词对速度要求大于精度，而在智能问答中由于句子较短，对分词的精度要求大于速度。