高级数据结构之猝死攻略（二）

短命女 2022-05-14 00:40 249阅读 0赞

接上一篇《高级数据结构之猝死攻略（一）》[https://blog.csdn.net/wydyd110/article/details/82190471][https_blog.csdn.net_wydyd110_article_details_82190471]

坚持不易，奖励一个小白脸来养养眼。

![70][]

**目录**

3 Trie树

3.1 等长字符树——26叉Trie

3.2 不等长的字符树，加 “ \* ” 标记

3.3 压缩trie树

3.4 二叉Trie树

3.5 后缀树

3.6 后缀数组 (Suffix Array)

4. 应用

4.1 Trie树应用于搜索提示服务

4.2 Trie树应用于路由转发

4.3 后缀树的应用

4.3.1 精准字符串匹配（ESM）

4.3.2 最长重复子串（LRS）

4.3.3 最长公共子串（LCS）

4.3.4 DNA污染问题

4.3.5 遇难者身份识别问题

4.3.6 回文问题

--------------------

# 3 Trie树 #

Trie ，来源于retrieval检索。

Trie树：字典树，单词查找树，前缀树。

下图是一棵由“北京”、“北京大学”、“北平”、“大便”、“便捷”五个中文词构成的 Trie 树。

![70 1][]

**根节点不包含字符**，除根节点外**每一个节点都只包含一个字符**

从根节点到叶子节点，路径上经过的字符连接起来，构成一个词。

而叶子节点内的数字代表该词在字典树中所处的链路**（字典中有多少个词就有多少条链路）**，具有共同前缀的链路称为串。

Trie 树中任何一个完整的词，都必须是**从根节点开始至叶子节点结束**。

## 3.1 等长字符树——26叉Trie ##

## ![70 2][] ##

一棵子树代表具有相同前缀的关键码的集合

“an”子树代表相同前缀an-具有的关键码集合\{and，ant\}

>   
> 注意：该字符树中，所有的单词都是等长的。即任何一个单词都不是其他单词的前缀。

## 3.2 不等长的字符树，加 “ \* ” 标记 ##

![70 3][]

> 该树中，存在某个单词是另一个单词的前缀，需要加 " \* " 来表示结尾。

## 3.3 压缩trie树 ##

存储单词 an, and, ant, bad, bee

**压缩前 压缩后**

![70 4][] ![70 5][]

> 对靠近叶节点的进行压缩。因为叶节点负责存储信息，中间节点起到索引的作用。

## 3.4 二叉Trie树 ##

• 每个字母或数值采用的二进制编码来表示  
• 编码只有0和1

**例：**存储 2（000010）、5（000101）、9（001001）、17（010001）、41（101001）、45（101101）、63（111111）

**按空间折半划分**

![70 6][]

**按编码划分**

**压缩前 压缩后**

![70 7][] ![70 8][]

> 0则在左分支继续划分

## 3.5 后缀树 ##

ababc的非空后缀子树：ababc, babc, abc, bc, c

**压缩前 压缩后**

![70 9][] ![70 10][]

## 3.6 后缀数组 (Suffix Array) ##

##  ##

![70 11][]

![70 12][]

**构建后缀树**

![70 13][]

> 构建后缀树的算法：UKK
> 
> 构建后缀数组的算法：DC3
> 
> 时间复杂度均为O(k)，其中k为字符串的长度

# 4. 应用 #

## 4.1 Trie树应用于搜索提示服务 ##

![70 14][]

如果是Google,Baidu这种大型搜索系统，或者京东淘宝这种电商系统，搜索提示的调用量是搜索服务本身调用量的几倍，因为你每输入一个键盘，就要调用一次搜索提示服务，这算得上是个标准的高并发系统吧？那么它是怎么实现的呢？

可能很多人脑子里立刻出现了缓存+哈希的系统，把搜索的搜索提示词存在Redis集群中，每次来了请求直接Redis集群中查找Key，然后返回相应的value值就行了，完美解决，虽然耗费点内存，但是空间换时间嘛，也能接受，这么做行不行？恩，我觉得是可以的，但有人这么做吗？没有。

这种搜索提示的功能一般用**trie树**来做，耗费的内存不多，查找速度为O(k)，其中k为字符串的长度，虽然看上去没有哈希表的O(1)好，但是少了网络开销，节约了很多内存，并且实际查找时间还要不比缓存+哈希慢多少。此外，Trie相比Hash具有“路径”信息，于是可以很方便的把有联系的Node遍历出来，这样就很方便的能够实现诸如“联想词”“纠错”“补全”等功能，这是Hash表不具备的。

（参考自《坑：缓存 + 哈希 = 高并发？》—吳YH堅[http://blog.jobbole.com/109905/][http_blog.jobbole.com_109905]）

## 4.2 Trie树应用于路由转发 ##

试想我们有上百台提供服务的机器组成的集群，彼此提供的服务各不相同，前端一个请求过来，其中url是`http://yiduowen.com/xxx/yyy/zzz` 如何进行调度呢？如果使用Trie，可以直接略过前缀“`http://yiduowen.com/`”`，`只需要查询xxx/yyy/zzz就能定位到Node，而Node的Data就是能够提供该服务的IP List，取其一，进行转发代理。

> **此外还有**
> 
>  *  IDE代码补全和提示
>  *  搜索框的高频词补全比如百度主页
>  *  文本字典序排序
>  *  浏览器地址栏浏览历史补全

## 4.3 后缀树的应用 ##

### 4.3.1 精准字符串匹配（ESM） ###

**生物应用**

识别DNA序列中的起始密码子ATG（RNA的转录翻译起始点）

**问题定义**

求长度为m的字符串Q在长度为n的字符串S中出现的位置。

![70 15][]

### 4.3.2 最长重复子串（LRS） ###

**生物应用**

DNA序列中的重复子串，可以相邻，也可以分离，常被用来作为“标记位点”。许多疾病也是由于具有某种结构的重复序列引起的。

**解决方案**

![70 16][]

.............................................................................................................

![70 17][]

### **4.3.3 最长公共子串（LCS）** ###

**生物应用**

发现多个序列的同源性。

**问题定义**

![70 18][]

**解决方案**

![70 19][]

.............................................................................................

![70 20][]

### **4.3.4 DNA污染问题** ###

**生物应用**

如何准确的测定DNA序列？（难道恐龙更接近人？）

**问题定义**

给定一个新测序的DNA序列S1和一个来自可能的污染物的DNA序列S2，若S2中的某个子串出现在S1中，则S1可能已经被污染了。

**解决方案**

![70 21][]

.................................................................................................

![70 22][]

### **4.3.5 遇难者身份识别问题** ###

**生物应用**

识别遇难者（如：在战争中死亡的士兵）的身份

**问题定义**

给定一个长度为m的字符串Q和一个字符串数据库，查找该字符串数据库中包含Q的字符串

**解决方案**

![70 23][]

### **4.3.6 回文问题** ###

**生物应用**

特殊位点识别（如：限制性酶剪切位点）

**问题定义**

![70 24][]

![70 25][]

(来源于《生物信息学概论讲义》[https://wenku.baidu.com/view/b74e9cec0975f46527d3e1d9.html][https_wenku.baidu.com_view_b74e9cec0975f46527d3e1d9.html])

[https_blog.csdn.net_wydyd110_article_details_82190471]: https://blog.csdn.net/wydyd110/article/details/82190471
[70]: /images/20220514/0848050a3cdc4d14a2fc78818333ad00.png
[70 1]: /images/20220514/74d7ed122fb74269bc47ff125f8ea99a.png
[70 2]: /images/20220514/ad87b96ab8944a22add091cde8aaae94.png
[70 3]: /images/20220514/3203e4f475e74c96a305f7d75e399c5e.png
[70 4]: https://img-blog.csdn.net/20180831143835323?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 5]: /images/20220514/9f95b7d3c2a447dd99cd962de4de51d7.png
[70 6]: /images/20220514/873d40ac4f9248e7886178ca3be61ec1.png
[70 7]: https://img-blog.csdn.net/20180831145817662?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 8]: /images/20220514/d8d56771d4e1407484d54878b9cb4a53.png
[70 9]: https://img-blog.csdn.net/20180831151935123?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 10]: /images/20220514/10497dadce724c71bedae2e750ac5bb1.png
[70 11]: /images/20220514/358ead8bf2a74aa68fb9d3bf69615493.png
[70 12]: /images/20220514/2f9ccf09b0f54064a19ad5099467cad8.png
[70 13]: /images/20220514/0b76526b8d684cebac1203cb667f94c4.png
[70 14]: /images/20220514/05bbd088433449598feb4f92e5474043.png
[http_blog.jobbole.com_109905]: http://blog.jobbole.com/109905/
[70 15]: /images/20220514/b996fdbe21f447a9b3640870b9ffe592.png
[70 16]: /images/20220514/dbad8923a5e34845ab400df7f0020ca8.png
[70 17]: /images/20220514/6c2453a4613c4691a3ba89e31c0e5b0b.png
[70 18]: /images/20220514/6ef2ab8b0a404086ba978c6ffa1e8f45.png
[70 19]: /images/20220514/88d80d1140124baca389d427912da98e.png
[70 20]: /images/20220514/e0aa1fc031d345ec9270cde864527de5.png
[70 21]: /images/20220514/dc4baa7ba39c4d2ead8e84111361b0f3.png
[70 22]: /images/20220514/b0dc3eec39fe401e8789fe37ef0e25e3.png
[70 23]: /images/20220514/3998d67fd52f4c8eba02aafd95b368ef.png
[70 24]: /images/20220514/c227b1e37dea44deb7697e1b17dd1e24.png
[70 25]: /images/20220514/69c7b8d7a47b4a3ca06b3419dade32c7.png
[https_wenku.baidu.com_view_b74e9cec0975f46527d3e1d9.html]: https://wenku.baidu.com/view/b74e9cec0975f46527d3e1d9.html