字符串算法—字典树

时间:2022-05-16 10:49:54

本文将介绍字符串的查找算法:R-way tries和ternary search tries(TST)。

1. 前文回顾

  在字符串算法—字符串排序(上篇)字符串算法—字符串排序(下篇)中,我们介绍了字符串的排序方法。

  但如果我们只想进行字符串的查找工作而不想排序呢?

  提到查找,我们自然而然地就想起了高效的两种查找算法:搜索算法—红黑树搜索算法—哈希表

  它们的效率如下图:

  字符串算法—字典树

  注释:图中N为元素的总个数。

  先看红黑树,我们可以把每个字符串当成一个节点,然后进行搜索。但是,搜索过程中需要进行数次比较(log2N),每次比较都需两个字符串将所有字符逐一对比,这里相对来说,比较慢。

  在看哈希表,因为只需进行很少次数的比较,所以红黑树的比较问题在哈希表中并不严重。但是,想用哈希表算法,我们是需要计算哈希值的,并且消耗一定量的空间。

  有没有比红黑树和哈希表更快、更省空间的算法呢?

  有!请看下文介绍。

 2. R-way tries

  这个算法名字在网络上并没找到正统的翻译,我就不翻译过来了。

  先从例子中直观地感受一下这棵树:

  字符串算法—字典树

  这里有一堆字符串,每个字符串对应一个数字,数字大小不必在意,反正不重复就行。接下来,把这堆字符串建成树:

  字符串算法—字典树

  这个是R-way tries。应注意到:

  1. 根节点为空;

  2. 每个节点只有一个字符;

  3. 有些节点会有一些数字,而有一些没有。

  为了容易理解,我们先介绍如何查找某个字符串,再介绍如何建这棵树。

寻找字符串“she”

  首先,she的第一个字符为s,从根节点出发,去找s:

  字符串算法—字典树

  找到s了,然后,she的第二个字符为h,从s出发,去找h:

  字符串算法—字典树

  找到h了,然后,she的第三个字符为e,从h出发,去找e:

  字符串算法—字典树

  找到e了,然后,she没有第四个字符。看我们找到的e,它有个数字0,因此she在这堆字符串里,且对应的数字为0。

 

寻找字符串“shell”

  首先,shell的第一个字符为s,从根节点出发,去找s:

  字符串算法—字典树

  找到s了,然后,shell的第二个字符为h,从s出发,去找h:

  字符串算法—字典树

  找到h了,然后,shell的第三个字符为e,从h出发,去找e:

  字符串算法—字典树

  找到e了,然后,shell的第四个字符为l,从e出发,去找l:

  字符串算法—字典树

  找到l了,然后,shell的第五个字符为l,从l出发,去找l:

  字符串算法—字典树

  找到l了,然后,shell没有第六个字符。看我们找到的l,它没有数字,说明shell不在这堆字符串里。

 

查找字符串"are"

  首先,are的第一个字符为a,从根节点出发,去找a:
  找不到!说明are不在这堆字符串里。

  通过上述3个字符串的寻找,相信大家已经会看这棵树了,接下来介绍建树的方法

  首先建个空节点作为根,然后逐一输入字符串:(输入顺序随意)

输入字符串“she”,对应数字为0:

  首先,she的第一个字符为s,从根节点出发,去找s;

  结果s不存在,在根节点下面建一个空节点,并把s放进去:

  字符串算法—字典树

  she的第二个字符为h,从s出发,去找h;

  结果h不存在,在s下面建一个空节点,并把h放进去:

  字符串算法—字典树

  she的第三个字符为e,从h出发,去找e;

  结果e不存在,在h下面建一个空节点,并把e放进去:

  字符串算法—字典树

  she没第四个字符,把对应的数字填入e里:

  字符串算法—字典树

输入字符串“shells”,对应数字为3:

  首先,shells的第一个字符为s,从根节点出发,去找s;

  字符串算法—字典树

  shells的第二个字符为h,从s出发,去找h;

  字符串算法—字典树

  shells的第三个字符为e,从h出发,去找e;

  字符串算法—字典树

  shells的第四个字符为l,从e出发,去找l;

  结果l不存在,在e下面建一个空节点,并把l放进去:

  字符串算法—字典树

  shells的第四个字符为l,从e出发,去找l;

  结果l不存在,在e下面建一个空节点,并把l放进去:

  字符串算法—字典树

  shells的第五个字符为l,从l出发,去找l;

  结果l不存在,在l下面建一个空节点,并把l放进去:

  字符串算法—字典树

  shells的第六个字符为s,从l出发,去找s;

  结果s不存在,在l下面建一个空节点,并把s放进去:

   字符串算法—字典树

  shells没第七个字符,把对应的数字填入s里:

  字符串算法—字典树

输入字符串“sea”,对应数字为6:

  首先,sea的第一个字符为s,从根节点出发,去找s;

  字符串算法—字典树

  sea的第二个字符为e,从s出发,去找e;

  结果e不存在,在s下面建一个空节点,并把e放进去:

  字符串算法—字典树

  sea的第三个字符为a,从e出发,去找a;

  结果a不存在,在e下面建一个空节点,并把a放进去;

  并且sea没第四个字符,把对应的数字放进a里:

  字符串算法—字典树

  注意,在R-way tries里,新建的节点在已有的节点左边还是右边都无所谓。

  如此类推,把所有字符串全部输入进去后,树建成:

  字符串算法—字典树

  到现在为止,我们知道了如何去建树和用树去找字符串,还缺什么操作?删除!

  删除也很简单,例如

删除shells:

  首先,按照查找方法,从根节点开始,逐个字符地找到shells的最后一个字符:

  字符串算法—字典树

  然后把这个s的数字删掉:

  字符串算法—字典树

  然后检查s是否有非空子节点,结果没有,把s删掉:

  字符串算法—字典树

  然后检查s的上一个节点l是否有非空子节点或者数字,结果都没有,把l删掉:

  字符串算法—字典树

  然后检查l的上一个节点l是否有非空子节点或者数字,结果都没有,把l删掉:

  字符串算法—字典树

  然后检查l的上一个节点e是否有非空子节点或者数字,结果有数字,删除操作结束。

  原则上,R-way tries里不允许出现即没非空子节点又没数字的节点。

  从原理上来看,一切都是多么的美好!但用代码实现时,就会遇到一个严重的问题。

  每个节点都有一个节点数组,用来存储此节点的子节点。那么,这个数组建立的时候,应该建多大?

  每个节点会有多少个子节点?这要看输入的字符串里的字符总共有多少种字符。

  如果我们能保证输入的字符串全都是字母,那么每个节点最多有26个子节点(因为只有26个字母),即每个节点的数组应该能容纳26个元素。

  字符串算法—字典树

  根据具体情况来选择R值吧,每个节点最多有R个子节点,即每个节点的数组应该能容纳R个元素。

  此时,再看回我们的这个例子:

  字符串算法—字典树

  假设我们输入的字符串的字符串全都是字母,那么每个节点都有26个子节点,但实际用到的只有几个,其余全都是空节点,这是对内存的极大浪费!

  放心,下面会介绍优化方法。

先看回R-way tries的实现代码:

  字符串算法—字典树

  字符串算法—字典树

  字符串算法—字典树

再看R-way tries的效率:

  字符串算法—字典树

  注释:

  1. N为所有字符串的总个数。

  2. L为字符串的长度

  3. R为我们选择的R值(上文提及的R)

  字符串算法—字典树

  4. moby.txt和actors.txt是测试文件。

  从图中可看出,R-way tries比红黑树快,比哈希表慢,且如果字符串过多,则内存有可能原地爆炸。

 

3. ternary search tries

  这个名字直译过来就是三叉搜索树,但是网络上没看到正统的翻译,所以这里也保留了英文原名。

  ternary search tries简称TST。它是R-way tries的进化版。

  每个节点都有三个子节点,左边的子节点比此节点小,中间的子节点等于此节点,右边的子节点比此节点大。

  从一个例子直观的感受一下:(有些空节点标出来是为了避免歧义)

  字符串算法—字典树

 

  与R-way tries有点像,但根节点不再为空,且找字符串的方法要些许不同。TST的节点最多有3个节点。

  先来看查找字符串:

寻找字符串“by”

  by的第一个字符为b,与根节点对比,b<s,故去s的左节点比较,然后发现s的左节点为b,相等:

  字符串算法—字典树

 

  by的第二字符为y,从目前所处的b节点出发,与此节点的中间节点相比较,相等:

  字符串算法—字典树

  by没第三个字符,我们找到的节点y有数字4,故查找成功,by对应的数字为4。

 

寻找字符串“shor”

  shor的第一个字符为s,与根节点对比,s=s,:

  字符串算法—字典树

  shor的第二个字符为h,从目前所处的s节点出发,与此节点的中间节点相比较,相等:

  字符串算法—字典树

 shor的第三个字符为e,从目前所处的h节点出发,与此节点的中间节点相比较,o>e,故去此节点的右节点中进行比较,相等:

 字符串算法—字典树

  shor的第四个字符为r,从目前所处的o节点出发,与此节点的中间节点相比较,相等:

  字符串算法—字典树

  shor没第五个字符,我们找到的节点r没有数字,故查找失败,shor不在这堆字符串里。

  总结一下:

  1. 假设要查找的字符串为X;整数变量int d=1; 节点Node=根节点;

  2. 把X的第d个字符与Node节点进行比较,如果这个字符大,则去根Node的右节点A,且Node=A; 如果这个字符小,则去Node的左节点B,且Node=B;如果相等,去第4步;

  3. 重复第2步,直到找到与X的第d个字符相等的节点为止,如果找不到,则说明要查找的字符串X不存在。

  4. d+=1; Node=Node的中间节点C;如果C不存在,且d<=X的长度,则说明要查找的字符串X不存在。重复第二步,直到d>X的长度为止,此时,去第5步;

  5. 检查X的最后一个字符所在的节点(即现在的Node)是否有数字,如果有,则说明找到这个字符串了;如果没有,则找不到。

  看懂了查找字符串,添加字符串也差不多了:

添加字符串“share”,对应数字为16:

  share的第一个字符为s,与根节点进行比较,相等:

  字符串算法—字典树

 

  share的第二个字符为h,与s节点的中间节点进行比较,相等:

  字符串算法—字典树

  share的第三个字符为a,与h节点的中间节点进行比较,a小;

  去与h的左节点e进行比较,a小;

  e节点左节点为空节点,把a填进去:

  字符串算法—字典树

  share的第四个字符为r,与a节点的中间节点进行比较,发现中间节点为空节点,把r填进去:

  字符串算法—字典树

  share的第五个字符为e,与r节点的中间节点进行比较,发现中间节点为空节点,把e填进去,且由于share没第六个字符,把数字也进去:

  字符串算法—字典树

  添加完毕。

  删除操作与R-way tries的一模一样,这里不做累述

 实现代码:

  字符串算法—字典树

  字符串算法—字典树

  字符串算法—字典树

TST的效率:

  字符串算法—字典树

  

 注释:

  1. N为所有字符串的总个数。

  2. L为字符串的长度

  3. R为我们选择的R值(上文提及的R)

  字符串算法—字典树

  4. moby.txt和actors.txt是测试文件。

  TST速度上比哈希表还要快,占用的空间相对来说也不多!

 

4. 算法应用

字符串排序:

  在TST的基础上是可以进行字符串排序的,只需从最左边一直读到最右边即可。

  字符串算法—字典树

代码实现:

  字符串算法—字典树

 

搜索引擎:

  字符串算法—字典树

  像google这类的引擎,我们可以用TST来实现。

  例如在我们上述的例子中:

  字符串算法—字典树

  当我们输入了"she",我们先搜索she:

  字符串算法—字典树

  经过3次键索后,找到了she,然后我们发现e下面有非空节点,继续往下走,就可以得到共用“she”的字符串:she,shells,sheore。

实现代码:

  字符串算法—字典树

  TST的应用还有很多,这里不一一列举。