《快速精确字符串匹配算法研究》由会员分享，可在线阅读，更多相关《快速精确字符串匹配算法研究（61页珍藏版）》请在金锄头文库上搜索。
1、合肥工业大学 硕士学位论文 快速精确字符串匹配算法研究 姓名：何畏 申请学位级别：硕士 专业：计算机系统结构 指导教师：汪荣贵 20100401 快速精确字符串匹配算法研究 摘要 字符串匹配算法是计算机应用、信息检索及计算生物学等的重要研究 内容，在日常生活及科学研究中有着广阔的应用。随着计算机技术和网络 技术的发展，新的应用对匹配实时性的要求不断提高。本文在对精确字符 串匹配问题的研究与现状及其各种方法进行深入探讨的基础上，针对单模 式精确字符串匹配及多模式字符串匹配中，被广泛使用的B M 和W M 两种 算法进行深入系统的研究，并提出相应的改进算法并通过实验验证了新算 法的优越性。全文主要
2、内容如下： 1 分析了字符串匹配算法的国内外研究现状，详细讨论了精确字符串 匹配下的三种搜索方式，研究并实现了单模式字符串匹配及多模式字符串 匹配下的若干典型算法，包括S h i f t A n d 及S h i f t O r 算法、H o r s p o o l 算法、 B N D M 及B O M 算法、A C 算法、w M 算法、S B O M 算法。 2 传统的B M 算法在不匹配发生时，匹配窗口移动的最大距离较小并 且匹配窗口能够移动的最大安全距离也不够大。因此，字符串匹配速度仍 有提升空间。针对这种情况，本文提出了一种新的可以增加平均移动距离 的改进的B M 算法。该算法首先在预
3、处理阶段使用任意的两个字符作为字 符块来计算移动距离，并设置最大移动距离为模式串长度加一；然后在查 找阶段通过比较连续的两个字符块来增加大距离移动的概率。实验结果表 明该算法相比于原算法在速度性能上提高明显。 3 传统的W M 算法在发生不匹配时安全移动距离明显较小，而当与 模式串匹配后的移动距离又较保守，并且存在单次匹配而整个模式串不匹 配的概率较大的情况。针对这些问题，本文提出了一种新的改进的W M 算 法，该算法首先对S H I F T 表进行改进，使得安全移动的距离有了较为明显 的提高；其次改进搜索查找算法，通过增加比较字符块使得单次匹配而整 个模式串不匹配的概率下降并使与模式串匹配后
4、的移动距离不再为1 。实 验表明，本算法较原算法在匹配速度上具有较好的实验效果。 关键字：字符串匹配；模式串匹配；精确串匹配；B M 算法；W M 算法 T h eR e s e a r c hf o rF a s tE x a c tS t r i n gM a t c h i n gA l g o r i t h m A BS T R A C T S t r i n gm a t c h i n ga l g o r i t h mi st h ei m p o r t a n tr e s e a r c ht o p i ci nc o m p u t e r a p p l i c
5、a t i o n ，i n f o r m a t i o nr e t r i e v a la n dc o m p u t a t i o n a lb i o l o g ya n dS Oo n I th a s ab r o a da p p l i c a t i o ni nt h e d a i l yl i f e a n ds c i e n t i f i cr e s e a r c h W i t ht h e d e v e l o p m e n t o f c o m p u t e rt e c h n o l o g y a n d n e t w o
6、r k t e c h n o l o g y ，n e w a p p l i c a t i o n sc o n t i n u et oi n c r e a s et h er e q u i r e m e n t so f r e a l - t i m eo ft h em a t c h i n g I n t h i sp a p e r ，o nt h eb a s e so fs t u d y i n gt h er e s e a r c ha n ds t a t u so ft h ee x a c t s t r i n gm a t c h i n gp r
7、 o b l e ma n di t sv a r i o u sm e t h o d s ，Id e e p l ya n ds y s t e m a t i c l y s t u d yt h eB Ma l g o r i t h ma n dW Ma l g o r i t h m ，w h i c ha r ew i d e l yu s e di ne x a c t s t r i n gm a t c h i n gf o rs i n g l e m o d ea n dm u l t i - p a t t e r ns t r i n gm a t c h i n
8、g ，a n d p r o p o s et h ec o r r e s p o n d i n gi m p r o v e da l g o r i t h m s ，w h o s es u p e r i o r i t i e s a r e e x p e r i m e n t a l l yv e r i f i e d T h em a i nc o n c e p t so ft h i sp a p e ra r ea sf o l l o w s ： 1 a n a l y s et h er e s e a r c hs i t u a t i o na th o
9、 m ea n da b r o a do fs t r i n g m a t c h i n g a l g o r i t h m ，d i s c u s st h et h r e ek i n d so fs e a r c hm e t h o d su n d e re x a c ts t r i n g m a t c h i n gi nd e t a i l ，s t u d ya n di m p l e m e n ts o m et y p i c a la l g o r i t h m su n d e r s i n g l e p a t t e r ns
10、 t r i n gm a t c h i n ga n dm u l t i p a t t e r ns t r i n gm a t c h i n g ，i n c l u d i n g S h i f t - A n da n dS h i f t O ra l g o r i t h m ，H o r s p o o la l g o r i t h m ，B N D Ma n dB O M a l g o r i t h m ，A Ca l g o r i t h m ，W Ma l g o r i t h m ，S B O Ma l g o r i t h m 2 I nt
11、h et r a d i t i o n a lB Ma l g o r i t h m ，w h e nn om a t c h i n gO c c u r s ，t h e m a x i m u md i s t a n c eo fm a t c h i n gw i n d o wm o v e di sm u c hs m a l l e ra n dt h e m a x i m u ms a f ed i s t a n c eo fm a t c h i n gw i n d o wm o v e di sa l s on o tb i ge n o u g h T h e
12、 r e f o r e ，t ot h es p e e do fs t r i n gm a t c h i n g ，t h e r ei ss t i l lr o o mf o ri m p r o v e m e n t I nv i e wo ft h i ss i t u a t i o n ，t h i sp a p e rp r e s e n t san e wi m p r o v e dB Ma l g o r i t h m ， w h i c hc a ni n c r e a s et h ea v e r a g em o v i n gd i s t a n
13、 c e F i r s t l y , i nt h ep r e p r o c e s s i n g s t a g e ，t h ea l g o r i t h mc a l c u l a t e st h em o v i n gd i s t a n c eu s i n ga n yt w oc h a r a c t e r s a st h ec h a r a c t e rb l o c k ，a n ds e t st h em a x i m u mm o v i n gd i s t a n c ea st h el e n g t ho f s t r i
14、n gp l u s i n go n e ；t h e n ，i nt h es e a r c h i n gs t a g e ，i ti n c r e a s e st h el a r g ed i s t a n c e s m o v i n gp r o b a b i l i t yb yc o m p a r i n gt h et w oc o n s e c u t i v ec h a r a c t e rb l o c k s E x p e r i m e n t a l r e s u l t ss h o wt h a tt h e a l g o r i
15、 t h m c a ni m p r o v et h e s p e e d s i g n i f i c a n t l yc o m p a r i n gt ot h eo r i g i n a la l g o r i t h m s 3 W h e nn o tm a t c h i n g t h es a f em o v i n gd i s t a n c eo ft h et r a d i t i o n a lW M a l g o r i t h mi sc l e a rs m a l l ，a n dt h em o v i n gd i s t a n
16、c ei sm o r ec o n s e r v a t i v ea f t e rt h e l I p a t t e r ns t r i n gm a t c h i n g ，w h a t Sm o r e ，t h ep r o b a b i l i t yo fs i n g l em a t c h i n ga n dt h e w h o l ep a t t e r ns t r i n gn o tm a t c h i n gi Sm u c h l a r g e r T os o l v et h e s ep r o b l e m s t h i s p a p e rp r e s e n t san e wi m p r o v e dW Ma l g o r i t h m ，w h i c hf i r s t l yi m p r o v et h e S H I F T t a b l e ， s i g n i f i c a n t l yi m p r o
