`
十三月的
  • 浏览: 170132 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

打破思维断层之最优美的BNDM

阅读更多

 

 

 

 

 BNDM

 

目的:

 

本篇博客以BNDM算法为载体,意图在减少思维断层情况下了解算法思想。

 

目录:

 

       1:其他算法回顾

 

       2BNDM算法介绍

 

       3:构建辅助表B

 

       4:容器创建和更新

 

       5:过程展示

 

1:其他算法回顾

 

在众多单字符匹配算法BFKMPShift-And/OrBMHorspoolSunday,个人最喜欢Shift-And/Or,尽管它不是效率最高的,但是从今以后我更喜欢BNDM

 

其实,自己对BMHorspoolSunday算法并没有什么太多好感。如果唯一觉得好的,估计就是他们让大家的思维产生了跳跃,这个实际上是BM的功劳,但不得不说后两个对BM的简化,让这个跳跃思维更加有魅力。

 

BM中,它利用了两个启发性规则:好后缀规则和坏字符规则。这个过程其实很繁琐,这不要紧,关键是作者将好后缀和坏字符进行了拆分(其实KMP中也是拆分了),根据这两个个体分别建立规则,然后会发现在利用两个规则的时候总觉得不伦不类,缺少整体性,让人觉得不爽。

 

HorspoolSunday其实摒弃了两规则,但是他们采用的规则和坏字符规则类似,实则对字符的随机性进行了利用,当匹配失败的时候用最后一个字符或者最后一个字符的下一个字符进行匹配,但是这个对比较过的好后缀和坏字符并没有加以利用,其实是难以加以利用。

 

如果说Shfit-And/Or是对“位并行”的首次展示就让人惊讶,那么BNDM则利用“位并行”大放异彩令人叹服。

 

下面做一个简单回顾:

 

字符串匹配的时候,是在目标串中寻找是否包含模式串的过程。

 

BF算法最容易想到

 
查找的过程:指针ij首先分别指向了目标串和模式串的首字符。当ij分别指向了目标串和模式串的eu的时候,发现不等,此时BF采取简单的策略是:i回溯指向了nj指向了模式串的首字母i,再次从头开始匹配。这种算法思路最简单,效果当然也是很差,原因在于并没有好好利用已经匹配的结果

 

KMP实现了指针不回溯前进

    
当目标串指针i指向y(此时i=8),模式串指针j指向d的时候(此时j=8),发现不等;KMP算法并没有采取BF的策略只是简单的把i设为1j设为0,从头开始比较,而是移动了5步,i=8(不变),j=3,使得模式串的abc对准了目标串的abc,如上图。因为BF比较的时候中间4步是没必要的。实际上KMP利用了已经比较的字符abcttabc的特性:abc既是前缀又是后缀。效率得到改善。这样指针i就不用回溯了,算法效率是onKMP只是利用了已经匹配成功(abcttabc)的结果,并没有关心匹配失败的yd

 

 

 

Shift-And/Or利用神器“位并行”改善KMP

 

http://wlh0706-163-com.iteye.com/blog/1845919

 

BM首次实现指针跳跃前进

 

BM采取从后向前比较,

 
第一次FT比较,不等;F称为坏字符,检查模式串中发现没有F,移动7

 

第二次-T比较,不等;-称为坏字符,检查模式串中发现有-,移动4,对齐。

 

第三次当比较到LA的时候,L是坏字符,由于模式串中没有L,移动6T是已经匹配的好后缀,根据好后缀需要移动3;取两者中大的6.


 

第四次当比较-H的时候,根据坏字符-需要移动2步才能对齐;根据好后缀AT需要移动5才能将模式串中AT和目标串的AT对齐。


 

BM就是这样比较了14次就成功匹配了。

 

BM利用了已经匹配的结果(好后缀)和没有匹配成功的(坏字符),但是分开利用的。

        HorspoolSunday将指针跳跃前进的效率大大提高。下面以Horspool为例

 
此时并没像BM一样,而是直接就根据最后一个字符n来匹配,将模式串中的字符和n对齐,相当于移动了7步。

Horspool实际只关心是否匹配成功,只要没有成功则按照最后一个字符移动。但是他的效率真的很高,主要是利用了单词中的字符的很随机的性质。

 

       其实,最一般的想法是最好能够同时利用已经成功匹配(好后缀)和没有成功匹配的(坏字符)字符做些事情,当然BM中已经这样做了,但是他是分开利用的,总觉的不是很舒服。

 

BDM(不是BNDM)的出现则很好的解决了这个问题:基于子串进行匹配它把好后缀和坏字符当成一个整体来利用

 

BNDM则是利用了位并行提高了BDM的效率,就像Shift-And提高了KMP算法的效率一样,只是BNDM是基于后缀匹配,ShiftAnd基于前缀。

 

想要了解Shift-And/Or,请参看http://wlh0706-163-com.iteye.com/blog/1845919

 

算法介绍

       BNDM算法维护一个容器,里面记录的是已经成功匹配的所有字符用u表示在模式串中出现位置,这个容器同样是用一个位向量D=dmdm-1…d1来表示。

    
当读入u的第一个字符u1时,模式串中第2位,第6位(从左到右数,下标从0开始)含有u1,则容器的第26位相应设为1;当读入第二个字符u2的时候,如果第1位,第5位让就是u2,则此时设第1位和第5位为1,如果第1位不是u2,则此时只有第5位是1.(可以先看例子,明白的快些)

构建辅助表B

 

       同样,和Shift-And算法一样需要先构建一个辅助表B,B用位掩码记录了某个字符在模式串中出现的位置。

 
结果:


容器创建和更新

创建:

容器默认值是1m(m1m表示的是模式串的字符的个数)

    更新:
 
 
  1步:查询辅助表B,得到新字符tj的掩码B[tj]

2步:左移1

 

过程展示:

伪代码:

 

 

 

 第一次:

 第二次:

 第三次:

 

 

 

 

 

 

 

 当读取了8个字符后,发现D的值仍旧不是0,表明模式串中存在这由njection8个字符组成的子串,此时last=j=1。在读取下一个字符n前,D在更新操作:左移1位后,发现D变成了000000000 这表明匹配失败,模式串向后移动last位,即1位。

 

第四次:

其实,对于last的值,从本案例第三次匹配的时候用到了一次,

 
由于D100000000,这个的意思实际上就是KMP中既是前缀又是后缀的字符的判断。已经匹配的字符”injection”其实是目标串的后缀同时又是模式串的前缀,判断后last被赋值为j1.下一次移动不再是9步而是1步。

附上另外2个案例:第一个是作者论文中的案例

案例1

目标串Targetabbabaabbaab

模式串Patternaabbaab

 

 

 
案例2

 



    
同样运用“位并行”的算法Shift-And/or的出现是在1992年,它的出现将基于前缀匹配的KMP算法的效率大大提高,。但是和BNDM算法相比,不论是效率上还是优美程度上都不可相提并论。当然,Shift-And/or算法一样,这种基于位并行算法会和机器有一定联系(字长),还会有各种各样的算法来解决字长限制的问题,有兴趣可以自己研究BOM算法。

 

 

 

 

 

 

 

 

  • 大小: 7.1 KB
  • 大小: 6.5 KB
  • 大小: 6.4 KB
  • 大小: 8.8 KB
  • 大小: 8.9 KB
  • 大小: 5.9 KB
  • 大小: 6.8 KB
  • 大小: 11 KB
  • 大小: 120.2 KB
  • 大小: 1.8 KB
  • 大小: 6.1 KB
  • 大小: 1.3 KB
  • 大小: 236.3 KB
  • 大小: 11.3 KB
  • 大小: 19.1 KB
  • 大小: 12.4 KB
  • 大小: 12.1 KB
  • 大小: 2.6 KB
  • 大小: 15.5 KB
  • 大小: 31.1 KB
  • 大小: 23.6 KB
  • 大小: 13.8 KB
  • 大小: 404.9 KB
8
1
分享到:
评论
7 楼 JanFan_张过要学会坚持 2014-11-19  
楼主你好,我也写一篇关于字符串匹配的总结,其中受了不少你的启发,欢迎你来点评:-)

http://janfan.github.io/chinese/2014/11/16/string-algorithm.html
6 楼 chinaagan 2013-05-03  
好文章啊,不错
5 楼 十三月的 2013-05-02  
ansjsun 写道
楼主你好...我大概看了下..具体没太明白..但是你的举例是一个模式串..如果是tire树结构..同时应该是多个模式串的匹配..对于这种问题..您提出的这个算法是否依然有效 ...谢谢

是的,这个是单字符串匹配问题解决办法,当然对于多字符串匹配问题同样可以采用此种策略,算法是Mutiple BNDM.其实不只是这个方法,对于单字符串匹配算法3中策略:基于前缀、基于后缀、基于子串匹配,在处理多字符串也可以应用。只是自己能力有限,才刚写到单字符串匹配......
4 楼 ansjsun 2013-05-02  
楼主你好...我大概看了下..具体没太明白..但是你的举例是一个模式串..如果是tire树结构..同时应该是多个模式串的匹配..对于这种问题..您提出的这个算法是否依然有效 ...谢谢
3 楼 十三月的 2013-05-02  
smallbee 写道
看不懂 好像很牛逼样子  能不能有个入门或者使用场景?

你可以直接从“构建辅助表B”开始看这个案例,前面可以先不看,这个算法自己比较喜欢,希望你能够看懂
2 楼 十三月的 2013-05-02  
smallbee 写道
看不懂 好像很牛逼样子  能不能有个入门或者使用场景?

这个算法是解决字符串匹配问题,只是单纯的看bndm的案例应该还是比较简单的,需要自己按照上述例子画一遍,画完之后应该就容易理解。
1 楼 smallbee 2013-05-02  
看不懂 好像很牛逼样子  能不能有个入门或者使用场景?

相关推荐

    《基于YOLOv8的八段锦练习指导系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    大语言模型教育应用中的知识冲突挑战与应对策略

    内容概要:本文详细探讨了大语言模型(LLMs)在教育应用中遇到的知识冲突问题,包括概念定义、事实陈述和逻辑推理层面的认知不一致性。文章分析了知识冲突的技术成因,如训练数据噪声、参数化知识表示的局限、推理机制的缺陷、模型架构的不足及外部知识的偏差,并探讨了这些因素对教育应用的深远影响。文中提出了多维度的解决路径,如通过数据增强优化知识表示、利用提示强化上下文连贯、开发量规完善模型评估等。此外,文章从社会文化的宏观视角剖析了知识冲突的外部驱动因素,探讨如何在多元异质、动态演进的社会建构语境中构建开放进取、兼容融通的智能教育应用体系。 适合人群:从事教育技术研究的学者、教育工作者、人工智能研究人员和技术开发者。 使用场景及目标:①帮助教育工作者理解大语言模型在教育应用中的局限性;②为技术人员提供优化大语言模型教育应用的具体策略;③促进教育人工智能技术的可靠性、适应性和普及性提升。 其他说明:文章强调了知识冲突的有效化解不仅能够提升大语言模型在教育场景中的应用价值,还将为人工智能在更广泛领域的可持续发展奠定坚实基础。

    《基于YOLOv8的家具鉴定系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    数据结构day1-思维导图顺序表

    数据结构day1-思维导图顺序表

    STM32超声波红外避障小车

    STM32超声波红外避障小车项目通过STM32微控制器实现自动避障功能。硬件部分主要包括STM32开发板、超声波传感器、红外传感器、直流电机、电池模块和电机驱动模块。超声波传感器用于测量前方障碍物的距离,红外传感器帮助小车检测地面线路或障碍物。电机驱动模块通过STM32控制直流电机的转动,从而实现小车的前进、后退和转向。 在软件方面,STM32通过编写简单的避障算法,实时读取传感器数据,并根据环境信息控制小车的运动。当超声波传感器检测到障碍物时,系统会触发后退或转向操作,避免碰撞。

    哈尔滨工业大学DeepSeek公开课-从图灵测试到DeepSeek.pdf

    哈尔滨工业大学DeepSeek公开课-从图灵测试到DeepSeek.pdf

    《基于YOLOv8的冰上运动监测系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    《基于YOLOv8的体育产业监测系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    《基于YOLOv8的港口机械识别系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    oooooomy_vchat_1742859071.zip

    app开发

    《基于YOLOv8的3D打印缺陷检测系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    Screenshot_2025-03-31-19-36-01-657_com.UCMobile.jpg

    Screenshot_2025-03-31-19-36-01-657_com.UCMobile.jpg

    半导体过程控制篇 集成电路的可靠性仿真_03_31_153111.docx

    半导体过程控制篇 集成电路的可靠性仿真_03_31_153111.docx

    社交应用_鸿蒙OS_API12_高仿微信APP_开发示例_1742847098.zip

    社交应用_鸿蒙OS_API12_高仿微信APP_开发示例_1742847098.zip

    《基于YOLOv8的民间体育监测系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    安卓_热更新_简化编译_HTHotFix框架_1742849446.zip

    app开发

    2024 最新版智慧消防全流程解决方案(含 BIM+IoT 技术应用 + 典型案例分析)

    2024 最新版智慧消防全流程解决方案(含 BIM+IoT 技术应用 + 典型案例分析)

    电商_微信小程序_学习项目_电商功能演示_1742849441.zip

    电商_微信小程序_学习项目_电商功能演示_1742849441.zip

    jiguang.zip

    jiguang.zip

    《基于YOLOv8的画作真伪鉴别系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

Global site tag (gtag.js) - Google Analytics