专栏首页朴素人工智能图文并茂!字符串匹配之Sunday、KMP和BM算法入门级讲解

图文并茂!字符串匹配之Sunday、KMP和BM算法入门级讲解

全网最幼稚园级别的字符串匹配算法科普,手把手带你辨别字符串匹配的花样套路。

字符串的模式匹配是NLP领域的基础任务,可以帮助我们在大量的文本内容中快速找到需要的文本信息,比如在文章中搜索关键词的位置和数量。

字符串模式匹配问题按照具体任务类型可以分为单模式匹配多模式匹配。单模式匹配是指匹配模板为单个字符串,即从待匹配字符串 (string) 中找出匹配模板 (pattern),比如著名的KMP算法和BM算法等等;而多模式匹配则表示匹配模板为多个字符串组成的模板集合,即从 中找到匹配模板集合 的所有匹配结果,比如AC自动机等等。

本文主要介绍单模式匹配的常见算法:

  • 朴素查找算法 Naïve String Search Algorithm
  • Sunday算法 Sunday Algorithm
  • KMP算法 Knuth–Morris–Pratt Algorithm
  • BM算法 Boyer–Moore Algorithm

1 朴素查找算法

朴素查找算法又被称为暴力算法(Brutal Force),是待匹配字符串 和模板 逐个字符依次进行匹配的简单粗暴算法。这种算法中,模板 先与 左侧对齐,从左往右逐位与 相应位置的字符比对,一旦失配, 右移一位,再重复上述步骤,直至完全找到匹配的部分,否则不存在相应的匹配。

如下图所示,蓝色表示匹配,红色表示失配。 与 从左往右逐位比对,失配后右移1位,连续右移4位后匹配成功。

朴素算法的思路简单,完全没有考察pattern本身的特点,没有考察匹配部分和未匹配部分的特点,进行了很多完全没有必要的比对。

下面要介绍的算法,会通过研究模板和待匹配字符串的特点,跳过一些不必要的比较,让 每次可以多走几步

2 Sunday算法

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配算法,它比后面要介绍的KMP算法和BM算法都要晚提出。不过其逻辑和处理方式比后二者要更简单清晰,故提前介绍。

Sunday算法会提前记录 的组成和每种字符在 中最右出现的位置,比如 : "abcab",每种字符在模板中的最靠右的位置为{'a':3, 'b':4, 'c':2}。

在每一次的比较中,一旦出现失配,算法会去看 中在当前匹配段后一位的字符 ,找到这个字符在 中最右出现的位置,并与其对齐,如果在 中没有对应的字符 ,则直接右移跳过整段的匹配段

看下面的例子:

与 在当前位置失配,直接去看 在当前匹配段(灰色线框)的后一个字符 为'b'(绿色方框),并在 中找到最靠右的'b', 右移1步至两个'b'对齐(下图蓝色线框)。

新的位置仍然失配, 在该匹配段的后一个字符 为'c',同样的操作,将 右移3位,使 中的'c'与 中的这个'c'对齐,成功匹配。

可以看到,巧妙地利用字符串的特点可以有效减少匹配的次数,提高匹配效率。

3 KMP算法

Knuth–Morris–Pratt Algorithm是以3个发明者的名字命名的字符串匹配算法,类似的,它也通过右移 从左往右依次匹配 。

该算法需要提前计算 部分匹配值表PMT(Partial Matching Table),其中元素为 每一个前缀子串的所有前缀和后缀的最大重叠串的长度。我们先来看看PMT表格。

对于字符串 :"abcab",其PMT表格为:

字符

a

b

c

a

b

序号

0

1

2

3

4

PMT

0

0

0

1

2

可以看到表格中PMT[3]=1,即前缀子串"abca"的PMT值为1,具体的计算过程如下:

查看的前缀子串"abca",这个子串的所有的前缀和后缀(不包括自身)为:

  • 所有前缀:{"a", "ab", "abc"}
  • 所有后缀:{"a", "ca", "bca"}

前缀和后缀的最大重叠的字符串为"a",故其PMT值为1。

下面我们来看,怎么在具体的例子中应用PMT:

图中,该匹配段在最后一个字符失配,已经匹配成功的子串 为"abca",根据上表,PMT[3]=1。右移的位数为已匹配的前缀子串(即 )的长度-PMT值,此处需要右移 步。可以看到, 的前缀"a"移动到了后缀"a"之前所在的位置上。

右移3位之后,匹配部分 为"a",长度为1,此时PMT[0]=0,故右移 位,成功匹配。

可以看到,计算PMT的主要目的,是通过研究模板 自身的特性,如果成功匹配部分 的前缀和后缀相同,就可以直接将相应前缀移动到对应的后缀上去,减少移动步数

4 BM算法

Boyer-Moore算法是于1977年由德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授提出。 右移去匹配 ,但与上文的方法不同的是,这里是从右往左依次匹配。这种算法将会引入2种不同的规则。

4.1 坏字符规则 Bad-Character Heuristics

对 中与 的失配字符 ,如果 中有 ,则移动 ,使其中最靠右的 与 中的 对齐

上图中 中与 失配的字符 为'a', 右移1位,让 中最靠右的'a'和 中失配的'a'对齐(下图蓝色线框)。

上图新的位置失配字符 为'a',继续使用坏字符规则,让 中最靠右的'a'和 中失配的'a'对齐,发现此时 需要左移1位。

可以看到,仅仅使用坏字符规则, 可能还需要左移走回头路,这是不可以接受的,此时需要结合另一个规则一起使用:好后缀规则。

4.2 好后缀规则 Good-Suffix Heuristics

对成功匹配的后缀子串 ,考查:

  • 如果 中还存在其他完整的 ,则将 右移,使 中的 与 中除了句末的 之外最靠右的 对齐
  • 如果 中不存在其他完整的 ,则如果 的后缀中有和 的前缀相同的部分,则右移 ,使 的前缀与 的后缀对齐。

在刚才的匹配中,坏字符规则后的中间步结果为:

当前匹配成功的子串 为"ab",在 中还存在一个"ab"子串,则右移 ,让前一个位置的"ab"与当前 中的"ab"对齐,成功匹配。

为了解释好后缀规则的第2种情况,这里引入一个新的例子来介绍:

当前匹配成功的子串 为"ba",在这个 中不存在另一个"ba"子串,则查看 的后缀中是否有与 的前缀相同的部分,发现存在相同子串"a",则右移 ,使得两个"a"对齐,并成功匹配。

以上即对好后缀规则的两种情况的介绍。

在应用中,坏字符和好后缀规则会分别给出右移距离,选择较大的那个右移距离,不允许出现走回头路的情况发生

可以看到,BM算法中,坏字符规则类似于Sunday算法(实际上是Sunday算法在BM的基础上的改进),好后缀规则类似于KMP算法。这些算法的原理和规则实际上都是利用字符串自身的特点和匹配时的特征,使可以跳过确定无法匹配成功的位置,从而加快搜索的速度。

参考文献

  1. Sunday 字符串匹配算法(C++实现) \ www.cnblogs.com/lyc94620/p/11420092.html
  2. 字符串匹配的Boyer-Moore算法 \ https://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
  3. 字符串匹配的KMP算法 \ https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
  4. 算法之「字符串匹配算法」\ https://juejin.im/post/5ccef225e51d456e4b3c6f31
  5. 浅谈字符串匹配 \ https://blog.brickgao.com/2015/08/08/string-searching-algorithm/

本文分享自微信公众号 - 朴素人工智能(sunnyday_no1),作者:戴师傅

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 大教堂与集市(中)

    可以很明显地观察到市集模式极大地加速了debug与程序演化。另一件可以清楚明白的是,在微观上,开发者与测试者的每天活动中,市集模式如何与为何可以达到这样的成果。...

    朴素人工智能
  • 表格问答2:模型

    说回正题,今天我们将介绍两个NL2SQL模型,X-SQL和HydraNet。它俩都来自微软,分别推出于2019年和2020年。X-SQL跟它之前的方案比如SQl...

    朴素人工智能
  • 分享一个介绍语言模型的好视频

    嗨,不知道大家是怎么度过这个四年才能遇见一次的2月29号的?我的朋友圈里好多人选择了吃一顿好的~

    朴素人工智能
  • [Skill]从零掌握正则表达式

    无论你是出于什么原因需要掌握正则表达式(诸如爬虫、文本检索、后端服务开发或Linux脚本),如果之前从没接触过正则表达式(比如我)很容易在如山般的公式中迷失,以...

    TOMOCAT
  • 机器学习及大数据相关面试的职责和面试问题

    ? 目录 · 机器学习、大数据相关岗位的职责 · 面试问题 · 答题思路 · 准备建议 · 总结 各个企业对这类岗位的命名可能有所不同,比如推荐算法/数据挖掘...

    小莹莹
  • PySpark ML——分布式机器学习库

    继续PySpark学习之路,本篇开启机器学习子模块的介绍,不会更多关注机器学习算法原理,仅对ML库的基本框架和理念加以介绍。最后用一个小例子实战对比下sklea...

    luanhz
  • 推荐几个在线练题平台

    最近在刷LeetCode,对于这种刷题平台由衷的喜欢,同时发现了几个非常好的在线练习平台,分别是学习 Git、SQL、正则表达式的在线练习平台。

    星星在线
  • 若想世界不崩塌,先开发后量子时代加密算法

    2020年,世界上产生的数据量预计有40ZB,如果一个硬盘的存储量是1T,那么一个ZB相当于10亿个硬盘。

    AI科技评论
  • 策略模式

    策略模式Strategy Pattern也称为政策模式Policy Pattern,其定义一系列算法,将每一个算法封装起来,并让它们可以相互替换,策略模式让算法...

    WindrunnerMax
  • ICML 2016 谷歌 DeepMind 论文上辑(大咖点评附下载)

    【新智元导读】ICLR2016 最佳论文获奖团队、谷歌 DeepMind 有9篇论文被即将于19日召开的深度学习重要会议 ICML2016 接收。新智元系统整理...

    新智元

扫码关注云+社区

领取腾讯云代金券