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

| 导语 字符串匹配算法通常分为两个步骤:预处理(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

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

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章