在开始之前我们先来看看字符串算法的一个整体目录。这里我们从简单到难的算法来排列,大概就分成这样一个顺序:
m
的字符串和一个长度为 n
的字符串,然后让他们两个互相匹配,这个时候我们有两种匹配方法破解法
,它可能是 m
乘以 n
的时间复杂度,显然这个算法的性能在大量的搜索字符的时候是不行的K
是高德纳,一个著名的写计算机程序设计的老爷子。加上另外两个计算机专家共同发明了 KMP 算法。这个算法就是在一个长字符串里面匹配一个短字符串,这个匹配算法的复杂度可以降到 m + n
。所以这个算法还是非常的厉害的。问号
表示匹配任意字符,星号
表示匹配任意数量的任意字符Wildcard
的这种通配符O(n)
或者 O(m+n)
的时间复杂度内去处理的。这个现象是因为 Wildcard 当中有一个贪心算法,也是它非常神奇的原因。LR
是还没有的,实际上 LR 是一个比 LL 更强大的一个语法分析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 没有本质的区别。
首先我们来加入一个 Trie
类,然后实现一个构建函数 constructor()
,这里为了干净我们就选择使用 Object.create(null)
来创建这个字符串。这样也可以避免受到 Object.prototype
原型上的一些污染。(不过因为我们每次存的是一个字符,也不存在污染的问题,但是这个写法是一个好的习惯,能干净还是尽量干净。)
class Trie {
/** 构建函数 **/
constructor() {
this.root = Object.create(null);
}
}
接下来我们需要编写一个 insert()
方法,这个方法的作用就是把一个字符串插入字典树里面。
这个插入逻辑其实很简单,我们去设一个变量 node
(也就是一个节点) ,一开始让这个节点等于我们的 root
(这里的 root
就是我们树结构的根节点
) 。然后我们就从 root
根节点,逐级地把字符串放进这个树的子树节点里面去。
这里如果我们的主树不存在的话,我们就先创建主树,然后我们再让 node
到下一个层级去(相当于我们在查字典的时候,翻到对应的字母的位置)。
最后我们要注意的是,字符串是会有大量的重复的。比如我们的 ab
和 abc
其实它是两个不同的字符串,所以说 ab
后边我们要有一个截止符。这个截止符我们就用 $
来表示。
!! 其实这里我们用 符是不合适的,因为如果我们的字符串本身就支持 这个内容的话,这样就会出问题了。所以说其实一个更好的方案就是我们使用 Symbol()来 创建一个 Symbol。这里我们可以使用 Symbol 来处理,这样就不会和我们字符里面的
!! 使用了 Symbol 的这种
不可重复
的特点,那么我们就可以让 node 节点最后的截止符更加严谨一些。
这里就讲完 insert()
方法的逻辑思路了,接下来我们看看代码:
/** 创建 $ 唯一的截止符 symbol **/
let $ = Symbol('$');
class Trie {
/** 构建函数 **/
constructor() {
this.root = Object.create(null);
}
/**
* 添加树节点
* @param {String} word 字符
*/
insert(word) {
let node = this.root;
for (let c of word) {
if (!node[c]) node[c] = Object.create(null);
node = node[c];
}
if (!($ in node)) node[$] = 0;
node[$]++;
}
}
这里我们做一个 randomWord()
函数,这个函数会产生一个随机的单词。然后结合我们的字典树,我们就可以轻易的分析一些字符的数据,比如说 "出现最多的单词" 之类的逻辑。
!! 不多说,先点个赞!
这里我们来看看这个函数的实现代码:
function randomWord(length) {
var s = '';
for (let i = 0; i < length; i++) {
s += String.fromCharCode(Math.random() * 26 + 'a'.charCodeAt(0));
}
return s;
}
这里面的 String.fromCharCode(Math.random() * 26 + 'a'.charCodeAt(0))
这一行代码做了什么呢?其实就是在 26 个字母的字符集里面随机拿一个字母出来,因为最大是 26 个,所以我们从字符 a
开始随机往后加入 随机数
* 26,这样我们就可以得到一个随机的数,并且这个数是在 0 - 26 之间。
好,有了这个随机生成单词的方法,我们就可以来生成大量的单词,然后使用我们的 字典树
来实现一个统计分析功能了。
这里我们来构建 10 万个随机单词:
let trie = new Trie();
for (let i = 0; i < 100000; i++) {
trie.insert(randomWord(4));
}
最后我们放入浏览器执行后,我们可以看到 字典树
就生成好了:
这里代表什么呢?如果我们还记得在 "例子分析" 部分讲到的,这里意思就是说我们是有 aaad
、aaag
、aaam
、aaax
、aaaz
这样的一些字符。
!! 好,现在我们想实现我们的业务需求,找出出现最多的随机字符串该怎么写呢?
回到我们的 Trie
字典树的类中,加入我们的 most()
方法。
在我们的 most 方法中,需要去遍历整棵树。在访问这棵树的时候,如果这棵树上没有结束,所以我们需要访问这颗树上的每一个单词,那这种情况该怎么办呢?
首先如果我们要统计所有的单词,我们就需要用递归访问整棵树的节点,然后再访问的同时记录每一个单词的出现次数。但是我们这里是一棵字典树,不是整个单词的数组集合,所以我们需要在树中找到每个字符结束的位置,并且记录这个单词的全部字母。
要找到单词结束的位置,首先我们看这棵树有没有 结束符,如果有 结束符说明当前的位置就是单词的截止的点,找到了截止的点,我们就可以找 max 的节点。但是我们只找到 max 的节点不等于我们找到了这个词。
所以我们需要在递归函数 visit()
的参数中加入 word
参数,这样在我们嵌入这棵树的所有分子的时候,我们都会在这个 word 变量值上追加当前节点的字母,最后整个分支被访问后,叠加出来的就是我们单词的全部字母了!
最后我们用一个变量 max
来记录最后这个 word
出现的次数,也就是每一个单词出现的次数。
听的一脸懵逼了没有?
没听懵的同学,我给你们点个赞,也希望我写的解释可以让大部分的同学听得懂这部分的逻辑。不过要知道要听懂这部分的算法逻辑,必须对 "数据结构
" 中的 "树
" 有一定的了解。如果没有了解这部分的知识,推荐同学们去补一下这方面的知识。
不过就算蒙了,也可以看看代码,可能就突然脑洞大开了呢?!
class Trie {
/** 构建函数 **/
constructor() {
this.root = Object.create(null);
}
/**
* 添加树节点
* @param {String} word 字符
*/
insert(word) {
let node = this.root;
for (let c of word) {
if (!node[c]) node[c] = Object.create(null);
node = node[c];
}
if (!($ in node)) node[$] = 0;
node[$]++;
}
/** 统计最高频单词 */
most() {
let max = 0; // 出现总次数
let maxWord = null; // 单词
/**
* 访问单词的递归方法
* @param {Object} 节点
* @param {String} 拼接的单词
*/
let visit = (node, word) => {
// 遇到单词结束符
if (node[$] && node[$] > max) {
max = node[$];
maxWord = word;
}
// 递归树的整个分支
for (let p in node) {
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 算法的相关知识!