基于BPM-BM的半模糊模式匹配算法.pdf

1、本文針對(duì)實(shí)際應(yīng)用中的一種特殊的模式匹配需求:對(duì)模式的一部分采取精確匹配,對(duì)另一部分采取形式復(fù)雜的模糊匹配,提出了半模糊模式匹配的概念。此問(wèn)題在眾多領(lǐng)域有廣泛的實(shí)用價(jià)值。國(guó)內(nèi)外針對(duì)半模糊模式匹配問(wèn)題的研究很少,特別是缺少針對(duì)大數(shù)據(jù)的快速有效的算法。本文通過(guò)構(gòu)造半模糊模式的結(jié)構(gòu),將該問(wèn)題轉(zhuǎn)化為普通模糊模式匹配問(wèn)題,根據(jù)其在模式匹配中的作用對(duì)模式中的字符進(jìn)行了分類,并總結(jié)了半模糊模式的性質(zhì)。通過(guò)分析普通模糊匹配算法中的幾種位并行方法和過(guò)濾方法

2、,本文基于BPM—BM算法,利用半模糊模式的特殊性質(zhì),研究了效果明顯的改進(jìn)措施,提出了解決半模糊模式的單模式匹配問(wèn)題的BPM／SA—BM算法,并將它推廣到多模式匹配的場(chǎng)合。通過(guò)分析多模式匹配時(shí)遇到的特殊問(wèn)題,基于MBPM—BM提出了MBPM／SA—BM算法。實(shí)驗(yàn)結(jié)果證實(shí),本文提出的算法克服了大目標(biāo)樣本以及半模糊模式特有的超長(zhǎng)模式、大模糊誤差率等因素對(duì)算法效率的不利影響,在各種情況下均取得了比現(xiàn)有算法更好的性能。并且,如果對(duì)普通模糊模式匹