算法之美4 - 字符串

蔚落 2022-03-06 17:00 145阅读 0赞

## 字符串 ##

朴素、KMP、BF 、RK、BM、AC自动机、Trie、后缀数组

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

### 32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ ###

> BF 算法

BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。

这种算法的最坏情况时间复杂度是 O(n\*m)。

但在实际的开发中，它却是一个比较常用的字符串匹配算法。为什么这么说呢？原因有两点。

第一，实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n\*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。

第二，朴素字符串匹配算法**思想简单**，代码实现也非常简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这也是我们常说的KISS（Keep it Simple and Stupid）设计原则。

> RK 算法

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。

哈希算法 - 我们用**二十六进制**来表示一个字符串，对应的哈希值就是二十六进制数转化成十进制的结果。

RK 算法整体的时间复杂度就是 O(n)。

这里还有一个问题就是，模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整型数据可以表示的范围，那该如何解决呢？

重新设计哈希算法

*  将 a~z 对应 1~26 个**自然数**，把字符串中每个字母对应的数字相加，最后得到的和作为哈希值
 *  更加优化的方法，比如将每一个字母从小到大对应一个**素数**，而不是 1，2，3……这样的自然数，这样冲突的概率就会降低一些。

> 思考题

我们今天讲的都是一维字符串的匹配方法，实际上，这两种算法都可以类比到二维空间。假设有下面这样一个二维字符串矩阵（图中的主串），借助今天讲的处理思路，如何在其中查找另一个二维字符串矩阵（图中的模式串）呢？

![006tNbRwly1fyo05ip2q4j30vq0e13z5.jpg][]

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

### 33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ ###

> BM 算法

BM（Boyer-Moore）算法

今天，我们讲了一种比较复杂的字符串匹配算法，BM 算法。尽管复杂、难懂，但匹配的效率却很高，在实际的软件开发中，特别是一些文本编辑器中，应用比较多。

BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。BM 算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现 BM 算法。

> 课后思考  
> 你熟悉的编程语言中的查找函数，或者工具、软件中的查找功能，都是用了哪种字符串匹配算法呢？

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

### 34 | 字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法？ ###

KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。

空间复杂度很容易分析，KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。

KMP 算法包含两部分，第一部分是构建 next 数组，第二部分才是借助 next 数组匹配。所以，关于时间复杂度，我们要分别从这两部分来分析。

next 数组计算的时间复杂度是 O(m)。

匹配部分的时间复杂度是 O(n)。

所以，综合两部分的时间复杂度，KMP 算法的时间复杂度就是O(m+n)。

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

### 35 | Trie树：如何实现搜索引擎的搜索关键词提示功能？ ###

> 什么是“Trie 树”？

Trie 树的本质，就是利用字符串之间的**公共前缀**，将重复的前缀合并在一起。

> 如何实现一棵 Trie 树？

Trie 树主要有两个操作，一个是将字符串集合构造成 Trie 树。这个过程分解开来的话，就是一个将字符串插入到 Trie 树的过程。另一个是在 Trie 树中查询一个字符串。

> 如何存储一个 Trie 树？

借助**散列表**的思想，我们通过一个**下标与字符一一映射**的数组，来存储子节点的指针。

![006tNc79ly1fzdgtkya1mj30vq0jd40n.jpg][]

> 在 Trie 树中，查找某个字符串的时间复杂度是多少？

构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）

构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。

> Trie 树真的很耗内存吗？

Trie 树是非常耗内存的，用的是一种空间换时间的思路

> 缩点优化

![006tNc79ly1fzdgxt9ylwj30vq0g575p.jpg][]

> Trie 树与散列表、红黑树的比较

对于支持动态数据高效操作的数据结构，我们前面已经讲过好多了，比如散列表、红黑树、跳表等等

针对在一组字符串中查找字符串的问题，我们在工程中，更倾向于用散列表或者红黑树。

Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。

Trie 树比较适合的是查找前缀匹配的字符串，比如：搜索引擎的搜索关键词提示功能

> 应用

自动输入补全，比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。

> 小结

今天我们讲了一种特殊的树，Trie 树。Trie 树是一种解决字符串快速匹配问题的数据结构。如果用来构建 Trie 树的这一组字符串中，前缀重复的情况不是很多，那 Trie 树这种数据结构总体上来讲是比较费内存的，是一种空间换时间的解决问题思路。

尽管比较耗费内存，但是对内存不敏感或者内存消耗在接受范围内的情况下，在 Trie 树中做字符串匹配还是非常高效的，时间复杂度是 O(k)，k 表示要匹配的字符串的长度。

但是，Trie 树的优势并不在于，用它来做动态集合数据的查找，因为，这个工作完全可以用更加合适的散列表或者红黑树来替代。Trie 树最有优势的是查找前缀匹配的字符串，比如搜索引擎中的关键词提示功能这个场景，就比较适合用它来解决，也是 Trie 树比较经典的应用场景。

> 思考

我们今天有讲到，Trie 树应用场合对数据要求比较苛刻，比如字符串的字符集不能太大，前缀重合比较多等。如果现在给你一个很大的字符串集合，比如包含 1 万条记录，如何通过编程量化分析这组字符串集合是否比较适合用 Trie 树解决呢？也就是如何统计字符串的字符集大小，以及前缀重合的程度呢？

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

### 36 | AC自动机：如何用多模式串匹配实现敏感词过滤功能？ ###

经典的多模式串匹配算法：AC 自动机

全称是 Aho-Corasick 算法

AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了。

> 小结

今天我们讲了多模式串匹配算法，AC 自动机。单模式串匹配算法是为了快速在主串中查找一个模式串，而多模式串匹配算法是为了快速在主串中查找多个模式串。

AC 自动机是基于 Trie 树的一种改进算法，它跟 Trie 树的关系，就像单模式串中，KMP 算法与 BF 算法的关系一样。KMP 算法中有一个非常关键的 next 数组，类比到 AC 自动机中就是失败指针。而且，AC 自动机失败指针的构建过程，跟 KMP 算法中计算 next 数组极其相似。所以，要理解 AC 自动机，最好先掌握 KMP 算法，因为 AC 自动机其实就是 KMP 算法在多模式串上的改造。

整个 AC 自动机算法包含两个部分，第一部分是将多个模式串构建成 AC 自动机，第二部分是在 AC 自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模式串构建成 Trie 树，另一个是在 Trie 树上构建失败指针。

[006tNbRwly1fyo05ip2q4j30vq0e13z5.jpg]: https://ws1.sinaimg.cn/large/006tNbRwly1fyo05ip2q4j30vq0e13z5.jpg
[006tNc79ly1fzdgtkya1mj30vq0jd40n.jpg]: https://ws3.sinaimg.cn/large/006tNc79ly1fzdgtkya1mj30vq0jd40n.jpg
[006tNc79ly1fzdgxt9ylwj30vq0g575p.jpg]: https://ws2.sinaimg.cn/large/006tNc79ly1fzdgxt9ylwj30vq0g575p.jpg