BNDM
目的:
本篇博客以BNDM算法为载体,意图在减少思维断层情况下了解算法思想。
目录:
1:其他算法回顾
2:BNDM算法介绍
3:构建辅助表B
4:容器创建和更新
5:过程展示
1:其他算法回顾
在众多单字符匹配算法BF、KMP、Shift-And/Or、BM、Horspool、Sunday,个人最喜欢Shift-And/Or,尽管它不是效率最高的,但是从今以后我更喜欢BNDM。
其实,自己对BM、Horspool和Sunday算法并没有什么太多好感。如果唯一觉得好的,估计就是他们让大家的思维产生了跳跃,这个实际上是BM的功劳,但不得不说后两个对BM的简化,让这个跳跃思维更加有魅力。
在BM中,它利用了两个启发性规则:好后缀规则和坏字符规则。这个过程其实很繁琐,这不要紧,关键是作者将好后缀和坏字符进行了拆分(其实KMP中也是拆分了),根据这两个个体分别建立规则,然后会发现在利用两个规则的时候总觉得不伦不类,缺少整体性,让人觉得不爽。
Horspool和Sunday其实摒弃了两规则,但是他们采用的规则和坏字符规则类似,实则对字符的随机性进行了利用,当匹配失败的时候用最后一个字符或者最后一个字符的下一个字符进行匹配,但是这个对比较过的好后缀和坏字符并没有加以利用,其实是难以加以利用。
如果说Shfit-And/Or是对“位并行”的首次展示就让人惊讶,那么BNDM则利用“位并行”大放异彩令人叹服。
下面做一个简单回顾:
字符串匹配的时候,是在目标串中寻找是否包含模式串的过程。
BF算法:最容易想到
查找的过程:指针i和j首先分别指向了目标串和模式串的首字符。当i和j分别指向了目标串和模式串的e与u的时候,发现不等,此时BF采取简单的策略是:i回溯指向了n,j指向了模式串的首字母i,再次从头开始匹配。这种算法思路最简单,效果当然也是很差,原因在于并没有好好利用已经匹配的结果。
KMP实现了指针不回溯前进。
当目标串指针i指向y(此时i=8),模式串指针j指向d的时候(此时j=8),发现不等;KMP算法并没有采取BF的策略只是简单的把i设为1,j设为0,从头开始比较,而是移动了5步,i=8(不变),j=3,使得模式串的abc对准了目标串的abc,如上图。因为BF比较的时候中间4步是没必要的。实际上KMP利用了已经比较的字符abcttabc的特性:abc既是前缀又是后缀。效率得到改善。这样指针i就不用回溯了,算法效率是o(n)。KMP只是利用了已经匹配成功(abcttabc)的结果,并没有关心匹配失败的y和d。
Shift-And/Or:利用神器“位并行”改善KMP。
http://wlh0706-163-com.iteye.com/blog/1845919
BM:首次实现指针跳跃前进
BM采取从后向前比较,
第一次F和T比较,不等;F称为坏字符,检查模式串中发现没有F,移动7
第二次-和T比较,不等;-称为坏字符,检查模式串中发现有-,移动4,对齐。
第三次当比较到L和A的时候,L是坏字符,由于模式串中没有L,移动6;T是已经匹配的好后缀,根据好后缀需要移动3;取两者中大的6.
第四次当比较-和H的时候,根据坏字符-需要移动2步才能对齐;根据好后缀AT需要移动5才能将模式串中AT和目标串的AT对齐。
BM就是这样比较了14次就成功匹配了。
BM利用了已经匹配的结果(好后缀)和没有匹配成功的(坏字符),但是分开利用的。
Horspool和Sunday将指针跳跃前进的效率大大提高。下面以Horspool为例
此时并没像BM一样,而是直接就根据最后一个字符n来匹配,将模式串中的字符和n对齐,相当于移动了7步。
Horspool实际只关心是否匹配成功,只要没有成功则按照最后一个字符移动。但是他的效率真的很高,主要是利用了单词中的字符的很随机的性质。
其实,最一般的想法是最好能够同时利用已经成功匹配(好后缀)和没有成功匹配的(坏字符)字符做些事情,当然BM中已经这样做了,但是他是分开利用的,总觉的不是很舒服。
BDM(不是BNDM)的出现则很好的解决了这个问题:基于子串进行匹配,它把好后缀和坏字符当成一个整体来利用。
BNDM则是利用了位并行提高了BDM的效率,就像Shift-And提高了KMP算法的效率一样,只是BNDM是基于后缀匹配,Shift—And基于前缀。
想要了解Shift-And/Or,请参看http://wlh0706-163-com.iteye.com/blog/1845919
算法介绍
BNDM算法维护一个容器,里面记录的是已经成功匹配的所有字符用u表示在模式串中出现位置,这个容器同样是用一个位向量D=dmdm-1…d1来表示。
当读入u的第一个字符u1时,模式串中第2位,第6位(从左到右数,下标从0开始)含有u1,则容器的第2,6位相应设为1;当读入第二个字符u2的时候,如果第1位,第5位让就是u2,则此时设第1位和第5位为1,如果第1位不是u2,则此时只有第5位是1.(可以先看例子,明白的快些)
构建辅助表B
同样,和Shift-And算法一样需要先构建一个辅助表B,B用位掩码记录了某个字符在模式串中出现的位置。
结果:
容器创建和更新
创建:
容器默认值是1m(m个1,m表示的是模式串的字符的个数)
更新:
第1步:查询辅助表B,得到新字符tj的掩码B[tj]
第2步:左移1位
过程展示:
伪代码:
第一次:
第二次:
第三次:
当读取了8个字符后,发现D的值仍旧不是0,表明模式串中存在这由njection这8个字符组成的子串,此时last=j=1。在读取下一个字符n前,D在更新操作:左移1位后,发现D变成了000000000 这表明匹配失败,模式串向后移动last位,即1位。
第四次:
其实,对于last的值,从本案例第三次匹配的时候用到了一次,
由于D是100000000,这个的意思实际上就是KMP中既是前缀又是后缀的字符的判断。已经匹配的字符”injection”其实是目标串的后缀同时又是模式串的前缀,判断后last被赋值为j即1.下一次移动不再是9步而是1步。
附上另外2个案例:第一个是作者论文中的案例
案例1:
目标串Target:abbabaabbaab
模式串Pattern:aabbaab
案例2:
同样运用“位并行”的算法Shift-And/or的出现是在1992年,它的出现将基于前缀匹配的KMP算法的效率大大提高,。但是和BNDM算法相比,不论是效率上还是优美程度上都不可相提并论。当然,Shift-And/or算法一样,这种基于位并行算法会和机器有一定联系(字长),还会有各种各样的算法来解决字长限制的问题,有兴趣可以自己研究BOM算法。
相关推荐
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
内容概要:本文详细探讨了大语言模型(LLMs)在教育应用中遇到的知识冲突问题,包括概念定义、事实陈述和逻辑推理层面的认知不一致性。文章分析了知识冲突的技术成因,如训练数据噪声、参数化知识表示的局限、推理机制的缺陷、模型架构的不足及外部知识的偏差,并探讨了这些因素对教育应用的深远影响。文中提出了多维度的解决路径,如通过数据增强优化知识表示、利用提示强化上下文连贯、开发量规完善模型评估等。此外,文章从社会文化的宏观视角剖析了知识冲突的外部驱动因素,探讨如何在多元异质、动态演进的社会建构语境中构建开放进取、兼容融通的智能教育应用体系。 适合人群:从事教育技术研究的学者、教育工作者、人工智能研究人员和技术开发者。 使用场景及目标:①帮助教育工作者理解大语言模型在教育应用中的局限性;②为技术人员提供优化大语言模型教育应用的具体策略;③促进教育人工智能技术的可靠性、适应性和普及性提升。 其他说明:文章强调了知识冲突的有效化解不仅能够提升大语言模型在教育场景中的应用价值,还将为人工智能在更广泛领域的可持续发展奠定坚实基础。
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
数据结构day1-思维导图顺序表
STM32超声波红外避障小车项目通过STM32微控制器实现自动避障功能。硬件部分主要包括STM32开发板、超声波传感器、红外传感器、直流电机、电池模块和电机驱动模块。超声波传感器用于测量前方障碍物的距离,红外传感器帮助小车检测地面线路或障碍物。电机驱动模块通过STM32控制直流电机的转动,从而实现小车的前进、后退和转向。 在软件方面,STM32通过编写简单的避障算法,实时读取传感器数据,并根据环境信息控制小车的运动。当超声波传感器检测到障碍物时,系统会触发后退或转向操作,避免碰撞。
哈尔滨工业大学DeepSeek公开课-从图灵测试到DeepSeek.pdf
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
app开发
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
Screenshot_2025-03-31-19-36-01-657_com.UCMobile.jpg
半导体过程控制篇 集成电路的可靠性仿真_03_31_153111.docx
社交应用_鸿蒙OS_API12_高仿微信APP_开发示例_1742847098.zip
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
app开发
2024 最新版智慧消防全流程解决方案(含 BIM+IoT 技术应用 + 典型案例分析)
电商_微信小程序_学习项目_电商功能演示_1742849441.zip
jiguang.zip
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。