字典树 —— 字符串分析算法

这里我们继续来编程训练，在《前端进阶》这个系列里面我们已经讲过一些字符串的算法了。然后这篇文章我们就来一起学习，剩下的几个字符串中比较细节的算法。

字符串分析算法

在开始之前我们先来看看字符串算法的一个整体目录。这里我们从简单到难的算法来排列，大概就分成这样一个顺序：

• 字典树

• 大量高重复字符串的储存与分析（完全匹配）

• 比如说我们要处理 1 亿个字符串，这里面有多少出现频率前 50 的这样的字符串，1 亿这个量我们还是可以用字典树去处理的

• 再比如说大家做搜索关键词，或者相同的字符串搜索类型的情况，很多时候我们就会需要用到类似字典树这样的一个结构

• KMP

• 在长字符串里找模式（部分匹配）

• 它跟字典树最大的区别就是字典树是检查两个字符串是否完全匹配，而 KMP 是两个字符串中，一个字符串是两一个字符串的一部分，但是这个就会出现一个更为复杂的问题。

• 如果我们有一个长度为 m 的字符串和一个长度为 n 的字符串，然后让他们两个互相匹配，这个时候我们有两种匹配方法

• 第一种就是暴力 破解法 ，它可能是 m 乘以 n 的时间复杂度，显然这个算法的性能在大量的搜索字符的时候是不行的

• 所以后面几位计算机专家研究出了 KMP 算法，而 KMP 就是三个人的名字的首字母， K 是高德纳，一个著名的写计算机程序设计的老爷子。加上另外两个计算机专家共同发明了 KMP 算法。这个算法就是在一个长字符串里面匹配一个短字符串，这个匹配算法的复杂度可以降到 m + n 。所以这个算法还是非常的厉害的。

• Wildcard

• 在 KMP 的基础上加了通配符的字符串模式

• 通配符包括 问号 表示匹配任意字符， 星号 表示匹配任意数量的任意字符

• 在我们做一些文件查找的时候可能就会运用到 Wildcard 的这种通配符

• 我们也可以理解它为一个弱一点的正则表达式，因为相比正则它只有两种通配符，并且这些通配符与正则有一个显著的区别，就是 Wildcard 其实也是可以在 O(n) 或者 O(m+n) 的时间复杂度内去处理的。这个现象是因为 Wildcard 当中有一个贪心算法，也是它非常神奇的原因。

• 正则

• 正则一般来说都是需要用到回溯的一个系统

• 它可以说是字符串通用模式匹配的终极版本

• 状态机

• 通用的字符串分析

• 与正则表达式相比，状态机会更强大

• 正则表达式与有限状态机在理论上是完全等价的两种东西

• 但是有限状态机不同的是，我们还可以往里面嵌代码，还可以给字符串做而外的处理

• 另外就是正则写起来很方便，有限状态机写起来成本比较高

• LL LR

• 在简单的匹配和分析的基础上，如果我们要对字符串建立多层级的结构，我们就会使用 LL 和 LR 这样的语法分析的算法

• LL 在上一篇文章我们已经学习过了，但是 LR 是还没有的，实际上 LR 是一个比 LL 更强大的一个语法分析

• 但是通常我们简单写，就都用 LL 去写，因为 LR 它 的理论性比较强

• 如果同学们还记得的话，我们在讲解 HTML 的语法分析的时候，我们用了一个 stack 去处理，这个其实就是 LR 算法的一个简化版。它其实是 LR(0) 的语法，但是一般来说我们去处理都会用 LR(1) ，而 LR(1) 是相等于 LL(n) 的这样一种非常强大的分析算法。

字典树

首先我们先了解字典树到底是一个什么东西。我们平时遇到不懂得字都会去查字典对不对？那么我去查字典的时候，我们往往会根据单词的第一个字母（一般是拼音首字母）作为索引去找到这个字大概在那一页，这里用到的就是字典序。

然后如果我们把这种索引寻找方法不断地重复。当我们找好了第一个字母之后，我们再去看它的第二个字母是属于字典中的哪一个部分，最后把这些一路找过来的 线索 变成一个树形的结构。换一句话说也可以理解为 " 查字典的行为变成一个树形的结构 "。—— 而这个树形结构就是我们的字典树了 ，字典树有一个英文的名字叫 " Trie "。

例子分析

接下来我们举个例子：

比如说现在我们有这 4 个字符串

[
'3499'
'0015'
'0002'
'0007'
]

这里它们都是等长的，不过不等长也没有关系的，等一下我们再来了解为什么。那么如果我们用字典树来保存这个 4 个字符串，因给怎么保存呢？

第一层

我们首先来看所有字符串的第一个字母，它们的第一个字母只有 0 和 3 这两种字符，所以我们字典树的第一层就会分成 3 和 0 两个分支。

第二层

接下来我们看看第二层，这里有 4 和 0 两种字符的分支。我们可以看到第一个字符串， 4 的前面是 3 ，并且在这个位置没有出现 4 前面是另外一种字符的情况。

所以这里我们就可以把 4 放到上一个 3 的分支之下，然后 0 也是一样，前一个字符都是 0，所以放在我们的 0 的分支之下。( 这里听的有点蒙不要紧，到了最后看着动画里面的效果来理解，就会更加明确了。 )

第三层

0 后面的分支，发生了一个变化，第二行的 0 后面出现了一个 1 ，然后第一行的 4 后面又有一个 9 。

所以说我们最后出来的字典树，在 4 的后面产生了一个 9 的分支，并且在 0 的分支上会产生了 1 、 0 两个分支。

第四层

同理，在第四层这里 0 的后面出现了 2 和 7 这两种情况，而 1 后面出现了 5 这一种情况。最后的 9 后面再次出现了 9，所以我们只需要再追加一个 9 的分支即可。

最后我们来看看整个字典树的生成过程！

代码实现

接下来我们看看在代码中，可以如何实现这棵字典树，以及看看字典树有什么样的应用场景。

首先我们来讨论一下字典树的存储机制，这里我们会用一个 空对象 来保存字典树里面的值。因为我们字典树在实际场景里面就是一段字符串所以说我们会用一个 对象来作为字典树的节点 。

当然如果大家愿意的话，用 Map 也是可以的， Object 和 Map 就是在 JavaScript 中最适合用来保存字典树里面的分支这种数据结构的。

因为字典树里面只会存字符串，所以说用对象还是 Map 没有本质的区别。

Constructor 构造方法

首先我们来加入一个 Trie 类，然后实现一个构建函数 constructor() ，这里为了干净我们就选择使用 Object.create(null) 来创建这个字符串。这样也可以避免受到 Object.prototype 原型上的一些污染。（不过因为我们每次存的是一个字符，也不存在污染的问题，但是这个写法是一个好的习惯，能干净还是尽量干净。）

classTrie{
/** 构建函数 **/
constructor() {
this.root =Object.create(null);
}
}

Insert 添加树节点方法

接下来我们需要编写一个 insert() 方法，这个方法的作用就是把一个字符串插入字典树里面。

这个插入逻辑其实很简单，我们去设一个变量 node (也就是一个节点) ，一开始让这个节点等于我们的 root (这里的 root 就是我们树结构的 根节点 ) 。然后我们就从 root 根节点，逐级地把字符串放进这个树的子树节点里面去。

这里如果我们的主树不存在的话，我们就先创建主树，然后我们再让 node 到下一个层级去（相当于我们在查字典的时候，翻到对应的字母的位置）。

最后我们要注意的是，字符串是会有大量的重复的。比如我们的 ab 和 abc 其实它是两个不同的字符串，所以说 ab 后边我们要有一个截止符。这个截止符我们就用 $ 来表示。

其实这里我们用 $ 符是不合适的，因为如果我们的字符串本身就支持 $ 这个内容的话，这样就会出问题了。所以说其实一个更好的方案就是我们使用 Symbol() 来 创建一个 Symbol 。这里我们可以使用 Symbol 来处理，这样就不会和我们字符里面的 $ 符号冲突了。

使用了 Symbol 的这种 不可重复 的特点，那么我们就可以让 node 节点最后的截止符更加严谨一些。

这里就讲完 insert() 方法的逻辑思路了，接下来我们看看代码：

/** 创建 $ 唯一的截止符 symbol **/
let$ =Symbol('$');

classTrie{
/** 构建函数 **/
constructor() {
this.root =Object.create(null);
}

/**
* 添加树节点
*@param{String}word 字符
*/
insert(word) {
letnode =this.root;

for(letcofword) {
if(!node[c]) node[c] =Object.create(null);
node = node[c];
}

if(!($innode)) node[$] =0;

node[$]++;
}
}

randomWord 随机单词

这里我们做一个 randomWord() 函数，这个函数会产生一个随机的单词。然后结合我们的字典树，我们就可以轻易的分析一些字符的数据，比如说 "出现最多的单词" 之类的逻辑。

不多说，先点个赞！

这里我们来看看这个函数的实现代码：

functionrandomWord(length){
vars ='';
for(leti =0; i < length; i++) {
s +=String.fromCharCode(Math.random() *26+'a'.charCodeAt(0));
}
returns;
}

这里面的 String.fromCharCode(Math.random() * 26 + 'a'.charCodeAt(0)) 这一行代码做了什么呢？其实就是在 26 个字母的字符集里面随机拿一个字母出来，因为最大是 26 个，所以我们从字符 a 开始随机往后加入 随机数 * 26，这样我们就可以得到一个随机的数，并且这个数是在 0 - 26 之间。

好，有了这个随机生成单词的方法，我们就可以来生成大量的单词，然后使用我们的 字典树 来实现一个统计分析功能了。

这里我们来构建 10 万个随机单词：

lettrie =newTrie();

for(leti =0; i <100000; i++) {
trie.insert(randomWord(4));
}

最后我们放入浏览器执行后，我们可以看到 字典树 就生成好了：

这里代表什么呢？如果我们还记得在 "例子分析" 部分讲到的，这里意思就是说我们是有 aaad 、 aaag 、 aaam 、 aaax 、 aaaz 这样的一些字符。

好，现在我们想实现我们的业务需求，找出出现最多的随机字符串该怎么写呢？

most 统计字符函数

回到我们的 Trie 字典树的类中，加入我们的 most() 方法。

在我们的 most 方法中，需要去遍历整棵树。在访问这棵树的时候，如果这棵树上没有结束，所以我们需要访问这颗树上的每一个单词，那这种情况该怎么办呢？​

首先如果我们要统计所有的单词，我们就需要用递归访问整棵树的节点，然后再访问的同时记录每一个单词的出现次数。但是我们这里是一棵字典树，不是整个单词的数组集合，所以我们需要在树中找到每个字符结束的位置，并且记录这个单词的全部字母。

要找到单词结束的位置，首先我们看这棵树有没有 $ 结束符，如果有 $ 结束符说明当前的位置就是单词的截止的点，找到了截止的点，我们就可以找 max 的节点。但是我们只找到 max 的节点不等于我们找到了这个词。

所以我们需要在递归函数 visit() 的参数中加入 word 参数，这样在我们嵌入这棵树的所有分子的时候，我们都会在这个 word 变量值上追加当前节点的字母，最后整个分支被访问后，叠加出来的就是我们单词的全部字母了！

最后我们用一个变量 max 来记录最后这个 word 出现的次数，也就是每一个单词出现的次数。

听的一脸懵逼了没有？

没听懵的同学，我给你们点个赞，也希望我写的解释可以让大部分的同学听得懂这部分的逻辑。不过要知道要听懂这部分的算法逻辑，必须对 " 数据结构 " 中的 " 树 " 有一定的了解。如果没有了解这部分的知识，推荐同学们去补一下这方面的知识。​

不过就算蒙了，也可以看看代码，可能就突然脑洞大开了呢？！

classTrie{
/** 构建函数 **/
constructor() {
this.root =Object.create(null);
}

/**
* 添加树节点
*@param{String}word 字符
*/
insert(word) {
letnode =this.root;

for(letcofword) {
if(!node[c]) node[c] =Object.create(null);
node = node[c];
}

if(!($innode)) node[$] =0;

node[$]++;
}

/** 统计最高频单词 */
most() {
letmax =0;// 出现总次数
letmaxWord =null;// 单词
/**
* 访问单词的递归方法
* @param {Object} 节点
* @param {String} 拼接的单词
*/
letvisit =(node, word) =>{
// 遇到单词结束符
if(node[$] && node[$] > max) {
max = node[$];
maxWord = word;
}

// 递归树的整个分支
for(letpinnode) {
visit(node[p], word + p);
}
};

visit(this.root,'');
console.log(maxWord, max);
}
}

最后我们在 console 中执行 trie.most() 就会输出我们出现频率最高的单词：

这里我们看到 maek 这个字符在 10 万个随机单词中出现了最多次，一共是 5 次。

在 26 的 4 次方的单词量中，其实这个数还是蛮大的。

等等，26 的 4 次方？这个是什么？如果我们回去看看我们随机生成单词的代码，我们随机生成了 4 个字母的单词，我们一共有 26 个字母，所以 4 个字母的单词一共有多少个组合呢？数学学的好的同学应该知道，在数学中我们可以用 可能有的种类数 的 n 次方就是这组合的可能出现的组合数。这里我们是 4 个字母的组合，所以 n 就是 4 。

不知道我讲的是什么，可以去看一下数学中的 "排列与组合" 的理论知识哦。

推荐同学直接点击这个传送门 《 " 5 分钟彻底了解排列组合 "》

关于这个 Trie 树，我们这里就展示了 Trie 去求出现最多的次数的功能。实际上我们通过 Trie 树还可以找到字典树中最小、字典树中最大，这样的值。

​在 1 万以内的量级，我们想在它们中求最大，求最小，不管这个数字有多少个我们都是可以比较方便地去处理的。

这就是字典树在处理大量的输入和字符串类的问题时候的能力。字典树其实他是哈希树的一种特例，这个哈希树在字符串领域里面 ，它最直接的应用的体现就是字典树。如果说我们处理数字，我们就可以用别的哈希算法来构造别的哈希树。因为我们这里不是主要学习算法，主要还是把字符串这一类常见的问题跟同学们一起了解清楚。

大家都学会了吗？学会了的点个赞，没有学会的点个收藏，觉得这些文章非常值得一看的，给我来个三连吧～谢谢！

这一期我们就讲到这里，下一期我们就来一起深入了解以下 KMP 算法的相关知识！

博主开始在B站每天直播学习，早上 06:00 点到晚上 11:30 。 欢迎过来《 直播间 》一起学习。

我们在这里互相监督，互相鼓励，互相努力走上人生学习之路，让学习改变我们生活！

学习的路上，很枯燥，很寂寞，但是希望这样可以给我们彼此带来多一点陪伴，多一点鼓励。我们一起加油吧！ (๑ •̀ㅂ•́)و

我是来自《 技术银河 》的 三钻 ："学习是为了成长，成长是为了不退步。坚持才能成功，失败只是因为没有坚持。同学们加油哦！下期见！"