对字符串匹配算法的一点理解
| 导语 字符串匹配算法通常分为两个步骤：预处理（Preprocessing）和匹配（Matching）。所以算法的总运行时间为预处理和匹配的时间的总和。
1.明确你的目标是算法选择最重要的事
文本匹配算法有很多，按照匹配模式串的个数，通常分为单模匹配和多模匹配，根据匹配的精确程度，可以分为精确匹配和模糊匹配。
无论是单模还是多模，精确抑或模糊，都是由最简单的暴力匹配算法作为基础，通过一点点微小进步，缓慢的优化拓展出来的，一系列基于特定数据结构的算法集合。除了作为字符串匹配算法之源头的暴力匹配算法外，其余的字符串匹配算法，都要经历两个步骤，第一是对元数据预处理，生成特定数据结构，第二是基于此特定数据结构做匹配运算。
既然要经历预处理数据生成特定数据结构和匹配运算这两个过程，那么自然的，也就给字符串匹配算法带来了在内存方面(数据处理)和运算效率(匹配运算)上的考量。
而吊诡之处就在于，这两者既相辅相成，却又互相抵抗。这也是很容易理解的，当你对元数据进行预处理的时候，你分析的越是深入，你得到的有效信息就越多，你就需要消耗更多的内存去存储这些信息，而到匹配运算，你记录的有效信息越多，匹配运算理应越快，用内存换来了效率.。反之亦然。
世界上的事情好像大多都是如此啊，妙在取舍之间。
所以，怎么办？明确你的目标和需求。清晰的目标可以让你拥有做选择的标准。这是我觉得最重要的事。
2.常见字符串匹配算法
字符串匹配算法很多，真的难记？
算法，大多都有它产生的动机。字符串匹配算法的发展，也符合这个规律，在不断重复”发现问题->解决问题”的过程中越来越完善。下面通过几个简单的算法介绍来体会一下这个路径。
字符串匹配问题的形式定义：
文本（Text）是一个长度为 n 的数组 T[1..n]；
模式（Pattern）是一个长度为 m 且m≤n的数组 P[1..m]；
暴力匹配算法
又称为朴素的字符串匹配算法，它的主要特点是：
没有预处理阶段；
整体模式串总是后移 1 位；
对模式中的字符的比较顺序不限定，可以从前到后，也可以从后到前；
匹配阶段需要 O((n - m + 1)m) 的时间复杂度；
需要 2n 次的字符比较；
匹配过程如图：
图片来源于网络
我们观察一下这个图示的过程，已知模式串aab，目标串acaabc，在第(a)步，模式串aab的第二个字母a与目标串acaabc的第二个字母c，匹配失败，已知串aab的第一个字母也是a，那么第二步(b)的比对就很多余，怎么样挖掘已知模式串的规律，来把类似(b)这种无效匹配优化掉呢？KMP！
KMP算法
KMP 算法的主要特点是：
需要对模式字符串做预处理；
预处理阶段需要额外的 O(m) 空间和复杂度；
匹配阶段与字符集的大小无关；
匹配阶段至多执行 2n - 1 次字符比较；
对模式中字符的比较顺序时从左到右；
怎么样来挖掘已知模式串信息，避免指针回溯，达到上面的优化效果呢？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树的基本性质可以归纳为：
根结点不包含字符，除根节点以外每个结点只包含一个字符。
从根结点到某一个结点，路径上经过的字符连接起来，为该结点对应的字符串。
每个结点的所有子结点包含的字符串不相同。
注意：每个结点可以有没有或者一个或者多个字结点，叶子结点没有子结点
而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
如果您觉得我们的内容还不错，就请转发到朋友圈，和小伙伴一起分享吧~