基于BPM-BM算法的地名数据匹配

在对基于过滤方法的中文字符串模糊匹配算法BPM-BM的基本原理、特点和计算流程等进行研究的基础上,与地名数据匹配理论相结合,建立了一种新的地名快速匹配方法。以"全国传染病疫情报告地理信息系统(乡级)建设工程"作为一个具体实例,使用C语言来完成地名数据的匹配。

基于BPM-BM过滤优化的近似字符串匹配算法

BPM-BM算法结合位并行和过滤技术,是当前近似字符串匹配算法中效率最高的算法之一。算法中过滤机制容易导致位并行计算连续性中断,使位并行计算回溯导致性能大幅降低。针对此问题提出了基于过滤优化的BPM-BM算法。实验结果表明:优化算法在大字符集环境下继承了BPM-BM算法的运行高效性,在非大字符集环境下较BPM-BM算法提升显著,且随着编辑距离的增长,其时间开销增长的稳定性大幅优于BPM-BM算法。

分块法的模式匹配算法的研究

为提高模式匹配算法性能,介绍经典的模式匹配算法Byoer-Moore和Sunday,分析它们改进后的效率,根据分块法的特点,提出一种新的分块模式匹配(block pattern matching,BPM)算法。BPM算法在预处理阶段先确定模式串的首字符在文本串的位置,再确定此字符后长度等于模式串长度的字符是否等于模式串的尾字符,若符合条件,采用单链表存储结构进行存储,在匹配阶段,利用单链表信息进行双向匹配。实验结果表明,BPM算法大大减少了匹配次数和字符比较个数,从而提高匹配效率。