对字符串匹配算法的一点理解

| 导语 字符串匹配算法通常分为两个步骤：预处理（Preprocessing）和匹配（Matching）。所以算法的总运行时间为预处理和匹配的时间的总和。

1.明确你的目标是算法选择最重要的事

文本匹配算法有很多，按照匹配模式串的个数，通常分为单模匹配和多模匹配，根据匹配的精确程度，可以分为精确匹配和模糊匹配。

无论是单模还是多模，精确抑或模糊，都是由最简单的暴力匹配算法作为基础，通过一点点微小进步，缓慢的优化拓展出来的，一系列基于特定数据结构的算法集合。除了作为字符串匹配算法之源头的暴力匹配算法外，其余的字符串匹配算法，都要经历两个步骤，第一是对元数据预处理，生成特定数据结构，第二是基于此特定数据结构做匹配运算。

既然要经历预处理数据生成特定数据结构和匹配运算这两个过程，那么自然的，也就给字符串匹配算法带来了在内存方面(数据处理)和运算效率(匹配运算)上的考量。

而吊诡之处就在于，这两者既相辅相成，却又互相抵抗。这也是很容易理解的，当你对元数据进行预处理的时候，你分析的越是深入，你得到的有效信息就越多，你就需要消耗更多的内存去存储这些信息，而到匹配运算，你记录的有效信息越多，匹配运算理应越快，用内存换来了效率.。反之亦然。

世界上的事情好像大多都是如此啊，妙在取舍之间。

所以，怎么办？明确你的目标和需求。清晰的目标可以让你拥有做选择的标准。这是我觉得最重要的事。

2.常见字符串匹配算法

字符串匹配算法很多，真的难记？

算法，大多都有它产生的动机。字符串匹配算法的发展，也符合这个规律，在不断重复”发现问题->解决问题”的过程中越来越完善。下面通过几个简单的算法介绍来体会一下这个路径。

字符串匹配问题的形式定义：

• 文本（Text） 是一个长度为 n 的数组 T[1..n]；

• 模式（Pattern） 是一个长度为 m 且m≤n的数组 P[1..m]；

暴力匹配算法

又称为朴素的字符串匹配算法，它的主要特点是：

1. 没有预处理阶段；

2. 整体模式串总是后移 1 位；

3. 对模式中的字符的比较顺序不限定，可以从前到后，也可以从后到前；

4. 匹配阶段需要 O((n - m + 1)m) 的时间复杂度；

5. 需要 2n 次的字符比较；

匹配过程如图：

图片来源于网络

我们观察一下这个图示的过程，已知模式串aab，目标串acaabc，在第(a)步，模式串a a b的第二个字母a与目标串a c aabc的第二个字母c，匹配失败，已知串aab的第一个字母也是a，那么第二步(b)的比对就很多余，怎么样挖掘已知模式串的规律，来把类似(b)这种无效匹配优化掉呢？KMP！

KMP算法

KMP 算法的主要特点是：

1. 需要对模式字符串做预处理；

2. 预处理阶段需要额外的 O(m) 空间和复杂度；

3. 匹配阶段与字符集的大小无关；

4. 匹配阶段至多执行 2n - 1 次字符比较；

5. 对模式中字符的比较顺序时从左到右；

怎么样来挖掘已知模式串信息，避免指针回溯，达到上面的优化效果呢？KMP是预处理模式串，计算出模式串的每个字母失配时候应该移动到的下一个位置Next！

为了计算Next，需要先了解一下前缀，后缀和PMT的概念：

字符串的前缀和后缀：

如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。 例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。

同样可以定义后缀A=SB，其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。 要注意的是，字符串本身并不是自己的后缀。

而PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。

比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}，两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。

假设有一个模式串abababca, 通过预处理, 可以得到一个类似如下的表：

图片来源于 网络

当模式串的某一个字母失配的时候，根据next表，做相应的位移，避免指针回溯。这就是KMP对暴力匹配算法的优化。

KMP是一种从左到右式的前缀匹配算法，在单模式匹配里面，还有从右到左式的后缀匹配算法BM等对其优化。按下不表。

但是如果有多个模式串需要匹配呢?  难道一个串一个串的匹配多次执行KMP算法? 未尝不可。

但显然是有更好的方法的。KMP的数据组织形式是一维的线性数据结构。我们想把它往多模去扩展，是不是可以考虑把数据结构扩展到二维，用树作为基础，实现一种多模匹配算法呢？

这就是字典树。

字典树与AC自动机

字典树前缀构词树。KMP是一对一匹配的时候常用的算法。 而字典树则是一对多的时候匹配常用算法。 其含义是，把一系列的模板串放到一个树里面，然后每个节点存的是它自己的字符，从根节点开始往下遍历就可以得到一个个单词了。

我们知道一个线性表的顺序查找的时间复杂度为O(n)； 二分搜索树的查找为O(log n)，它们都和数据结构中的元素个数相关。

而Trie字典树(主要用于存储字符串)查找速度主要和它的元素(字符串)的长度相关[O(w)]。

trie树的特点：

在trie树中，字符串preview，prepare公共前缀是“pre”，因此可以只存储一份“pre”以节省空间。 当然，如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存，这也是trie树的一个缺点。

Trie树的基本性质可以归纳为：

1. 根结点不包含字符，除根节点以外每个结点只包含一个字符。

2. 从根结点到某一个结点，路径上经过的字符连接起来，为该结点对应的字符串。

3. 每个结点的所有子结点包含的字符串不相同。

注意： 每个结点可以有没有或者一个或者多个字结点，叶子结点没有子结点

而AC自动机，则是对字典树做一个类似KMP算法似的优化，防止指针回溯，提高匹配效率。字典树 + 每个节点的Next表，就是一个AC自动机了。自动是自动的啥？就是指针不用回溯，自动跳到下一个Next节点！

Trie树是基于前缀构造的树，还有后缀树和压缩字典树(节点合并)等一些优化的字符串多模匹配的数据组织方式。

至此，字符串算法演进的路径可窥一二了，由暴力匹配算法而起，防止指针回溯做优化，产生了基于前缀的优化算法KMP，基于后缀的优化算法BM。一对一匹配的问题解决了，而一对多的问题，又扩展出了字典树，之于字典树，又优化出了后缀树和压缩字典树等等字符串匹配算法。

3. 表情推荐算法怎么选的?

表情推荐算法，本来是有模糊匹配的需求的，模糊匹配的需求就要选用AC自动机或AC自动机相关的优化算法。但是需求后来变更为：精确匹配，最大包含10万词的词库。

使用什么数据结构呢？效率和内存都要兼顾。看下常用的数据结构类型：

图片来源于 网络

一维结构， 好像散列是唯一选择了吧， 内存占用与其他一致， 效率却杠杠的。

关于字符串匹配算法详情实现的参考：

http://www-igm.univ-mlv.fr/~lecroq/string/

https://www.zhihu.com/question/21923021/answer/281346746

http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html

http://blog.chinaunix.net/uid-26548237-id-3968132.html

https://blog.csdn.net/u011467044/article/details/55008649

如果您觉得我们的内容还不错，就请转发到朋友圈，和小伙伴一起分享吧~