数据结构(邓俊辉)学习笔记】串 09——BM_BC算法:以终为始

2024-08-29 00:52

本文主要是介绍数据结构(邓俊辉)学习笔记】串 09——BM_BC算法:以终为始,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. 不对称性
  • 2. 善待教训
  • 3.前轻后重
  • 4.以终为始

1. 不对称性

上一节所介绍的 KMP 算法计算时间,在最坏情况下也可以保证不超过线性。这的确是一个好消息。然而,倘若我们因此就停下继续优化的脚步,那就大错特错了。

在这里插入图片描述

实际上,串匹配问题与一般的搜索问题的确有着本质的区别。在我们此前所讨论的所有搜索算法中,每次比对都是一种一对一的模式,也就是一个目标与另一个候选者判定二者是否相等,的确只需常数的时间。而现在,虽然基本的数据对象是单个的字符,而所谓的串匹配则是相对于由若干个字符在局部组成的一个片段而言的,也就是说是由多个字符对多个字符,二者匹配,当且仅当每一对字符彼此相等。

然而,需要特别注意的是,反过来,一旦发现有一对字符不等,我们就立即可以判断串失配。于此可见,从计算成本的角度来看,判定一对串是否相等与判定它们是否不等并不是完全一样。

我们接下来将要介绍的 BM 算法,就充分地利用了这一性质,从而使得它匹配的效率得以进一步地提高。

实际上,这一算法同时采用了两种策略,在接下来的这一节,我们首先来讨论所谓的坏字符策略。

2. 善待教训

在这里插入图片描述

让我们将视线拉回到蛮力算法。应该记得,蛮力算法一次典型地运行过程,可以表示为这样一幅图。是的,如果将文本串固定在这里(灰色),那么这些就是模式串在不同对齐位置处的历史快照。事实上,模式串在每一个对齐位置的故事,都是类似的。

  1. 首先,要经过若干次成功的比对,在这里,用绿色的线条来表示。
  2. 而接下来,总是一次失败的比对。
  3. 之后,再下一位置的故事依然。该算法也需要经过若干次成功的匹配,然后终止于失败地比对。

而在接下来的第三次、第四次、第五次等等,各次对齐中,也同样都是要经过若干次成功的比对,并终止于一次失败的比对。因此,就局部的每一次对齐而言,我们都需要经过若干次的成功,并终止于一次失败。

请注意,在每次对齐中,尽管只有一次失败,但却足以确定相应的对齐位置是无效的。事实上,只有最后一次对齐位置才有可能是成功的。因此,就整体而言,恰好与刚才局部的模式相反。多次失败,以及至多一次的成功。

因此,如果我们着眼于改进蛮力算法。那么,我们的目标与其说是要加速匹配,不如说是要加速失败,或更准确地讲,要尽可能快速地、低成本地排除掉无效的对齐位置。

事实上,KMP 等算法就是这样。应该记得, KMP 会聪明地排除掉其中的若干个,甚至是大量的对齐位置,从而大大的节省计算的成本。甚至从某种意义上讲,我们或许能够做得比 KMP 还要出色。

正如我们刚才所指出的,就排除某个对齐位置而言,相应的那些成功的比对并不重要,而在这个意义上起实质作用的,反而是那些失败的比对。 如果真的像刚才说的那样,我们总是需要在排除多个无效的对齐位置之后,才能够确定最终有效的对齐位置,那么我们反倒应该更加期盼这种失败的比对出现得更早。

比如,按照这种思路的一种极端情况就是,我或许可能只做这些失败的比对,就足以排除掉相应的对齐位置。为了排除掉一个对齐位置,我们平均只需做常数次比对,而且在理想平均的情况下,甚至不必去关心,哪个字符更有可能首先失败,而只需按部就班地从前向后,自左而右地依次比对就可以了。

是的,如果我们的关注力只停留于单个的比对位置,那么固然如此。但是,倘若我们将所有的对齐位置作为一个整体来考虑,我们就会发现,实际上在每一个对齐位置处,按照什么样的次序去尝试对比各自符却十分敏感而关键。我们的建议是,你或许应该优先去比对那些靠后、乃至最靠后的字符。

也就是说,与我们常规的做法恰恰相反。或许你应该更多地去关注教训。是的,如果教训的确不能避免的话,或许我们应该让它更早地暴露出来,或者再准确地讲,应该让更大的教训更早的暴露出来。

那么,为什么就串匹配算法而言,在越靠后的位置所获得的教训所具有的价值越高呢?

3.前轻后重

在这里插入图片描述

依然来考察蛮力算法的一次典型执行过程。假定在依次排除了一系列的对齐位置之后,抵达了下一个对齐位置。此时我们有两种策略,或者优先去比对靠前的字符,或者反过来优先比对靠后的字符。

这里我们再次强调一下,只要字母表的规模不是很小,那么就每一次字符对字数的比对而言,成功的概率将远远小于失败的概率,也就是说我们更有可能获得教训,而不是经验。

果真如此,在前后这两个位置所获得的教训,其价值大小又有何区别呢?的确有所区别,而且很大,其背后的原因在于,根据这样的每一次教训,我们不仅可以排除一个对齐位置,而且可能排除掉多个对齐位置。

比如,根据在前一位置所获得的教训,我们或者可以同时排除掉三个对齐位置,而不是一个。类似地,在后一位置所获得教训,则有可能帮助我们排除掉更多的对齐位置,远远更多的对齐位置。

是的,如果就这类教训对我们提高计算效率的意义而言,的确呈现出前轻后重的特点。

4.以终为始

在这里插入图片描述
既然按照以上的分析,模式中越靠后的字符对算法性能的优化作用更大,那么或许我们应该把计算的方向和次序颠倒过来,以终为始。此话怎讲呢?

具体来说,在每一趟扫描中,我们都需要从末字符而不是首字符开始比对,也就是说扫描的方向将变成自后向前,而不再是自左向右。

来看这样一个具体的例子:这就是由12个字符所构成的一个文本串,而待匹配的模式串则由这三个字符组成。

  1. 为了启动第一趟扫描,我们首先要将它们的首字符彼此对齐。然而这里,我们将首先从末字符开始比对。可以看到,这是一次失败的比对。

    实际上,这种失败的比对必然是更容易发生的,因为你注意到,我们在这一所采用的字母表是由汉字构成的,即便是只记录常用的汉字,其规模也至少超过5,000,从多达5,000个的候选中任取2个,二者相同的概率自然是非常之低的。反过来不同的概率也就应该很高。

    所以对于这次失败,我们应该有足够的心理准备。因此接下来,或许我们应该静下心来,对这次失败好好地作一分析。或许你能从中悟出点什么。是的,表面上看这里是"名"与"道"之间的冲突,而实际上我们可以将这次教训进一步地概括为,如果需要在"道"的附近实现一次完整的匹配,那么至少与它对应的那个字符就应该也是"道",而非"名"。

  2. 现在,按照这一必要条件来反观我们的模式串,就会发现其实"道"根本就没有出现在其中,这一点非常重要,如果能够悟到这一点,我们就可以大胆地将这个模式串整体的移过这个位置,从而在这样一个新的位置对齐。

  3. 接下来的这趟比对与上一趟基本类似,依然是"名"与"道"不符。所以再一次地,我们同样可以将整个字符串移过这个位置。从而在这样一个新的位置继续对齐。

  4. 接下来的这趟扫描,依然起始于末字符。可以看到这是一次成功的比对,应该觉得非常幸运,因为正如刚才所言,这种成功比对出现的概率是极低的。于是接下来,我们再去进而比对与之在左侧相邻的那一对字符。这依然是一次大概率的失败比对,然而作为一次新的教训,它同样可能让我们悟到点什么。

    是的,依然是这个失配位置处的"可"字。它同样给出了一个能够局部完全匹配的必要条件。然而,如果按照这个必要条件,反观我们的模式串,就会发现其中同样没有出现这个字符。

  5. 因此接下来,我们可以将这个字符串同样整体的移过这个失配的位置,并在这样一个新的位置继续对齐,然后依然从末字符开始继续比对,同样,依然是大概率的失败。

    而此后,只要我们能够静下心来对这一教训作一分析,就同样能够针对完全匹配给出一个必要条件。我想,你已经看出这个必要条件来了。是的,如果能够在包括这个"常"字在内的局部,实现一次完全匹配,那么模式串中与之对齐的,就同样也应该是一个"常"字。

    这一回,我们依次反观模式串,就会发现的确存在一个"常"字。因此接下来,我们就不妨将整个字符串向右移动一个单位,从而让"常"字的确与"常"字相对。在满足的这样一个必要条件之后,我就可以来开始新一轮比对。

  6. 首先是末字符,这是成功的。而且接下来的各次比对也都是成功的。这意味着我们终于发现了一次完全的匹配,整个算法也就可以随即终止。

现在,我们来核算一下这个算法所花费的计算成本,也就是在期间所做的比对次数。按照我们这里标注的习惯,深色的都是成功的比对,灰色的则是失败的比对。而白色的,则是没有进行,从而节省下来的比对。

可以看到,我们累计做了4次成功的比对,以及4次失败的比对。没错,4次加4次,累计不过8次,这一结果意义非凡。因为我们注意到,即便忽略掉模式串,仅文本串也至少有12个字符,而我们在算法过程中所执行的比对次数居然要小于这一长度。换而言之,平均在每个字符上所消耗的比对居然不足一次。

这篇关于数据结构(邓俊辉)学习笔记】串 09——BM_BC算法:以终为始的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1116381

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1