《面向网络内容筛选的串匹配技术研究》由会员分享，可在线阅读，更多相关《面向网络内容筛选的串匹配技术研究（59页珍藏版）》请在金锄头文库上搜索。
1、摘壁摘要串匹配是计算机科学理论中的一个经典问题，它指在一个符号串中寻找具有特定性质的模式，比如在一个字符串中寻找某个子串对于这个古老的问题，已经有很多的研究，也有很多优秀的算法。然而近年来，随着网络和生物信息学的发展，对于串匹配技术提出了许多新的需求，对于这个经典问题大家又重新产生了浓厚的兴趣。在网络技术中，随着网络应用的日渐普及，网络信息在迅速膨胀，因此如何能够及时，准确、安全地在庞大的实时网络信息流中获得特定的信息，已经成为网络信息安全领域的热点问题。由于数据量的庞大、检索的实时性以及待检索文本的结构化等需求，因此必须有针对性地改进已有的串匹配技术，才能够解决网络信息过滤问题。本文印为解决
2、此问题的一项尝试，并取得了如下成果：1 分析总结了部分经典算法在随机数掘上的性能：本文总结了当前精确模式串匹配算法的研究现状，包括针对单模式串的K M P 算法、B o y e rM o o r e 算法和B O M ( B a c k w a r dO r a c l e M a t c h i n g ) 算法，针对多模式串的A h o C o r a s i c k 算法、W u M a n b e r 算法和S B O M( S e tB a c k w a r dO r a c l eM a t c h i n g ) 算法。从理论的角度，本文对这些算法的平均时问复杂度进行了仞步分析
3、：并在随机的网络数掘测试集合上，验证了以上结论：进而总结出多模式串匹配算法性能的4 条性质。2 提出了多模式串匹配的划分策略：经典的多模式匹配算法，在模式数目多于5 0 0 0时性能有着明显的下降。针对这个问题，本文提出了分组的策略以提高匹配性能。本文证明了最优划分的两个性质：一是最优划分的连续性定理，一是最优划分的等长分组性定理。3 设计并实现了一种大规模多模式串匹配的算法一C O M ：它使用动态规划方法或最短路径方法求解最优的划分，并对每组进行训练以得到一种最适用的串匹配方法实验结果表明，C O M 算法的扫描匹配速度足传统算法的l 一3 倍。4 提出了针对结构化的X M L 文本的快速
4、串匹配的算法- - X M a t c h ：在对于X M L 文本的含路径信息的模式串匹配中，由fX M L 文本的结构化特点，使得传统的串匹配算法不能直接有效地使用。X M a t c h 在对X M L 文本的结构- - s c h e m a 进行分析的同时，结摘璧合模式串的路径信息，建立一个扫描自动机的有限状态自动机；此外，算法还支持带循环引用路径信息的模式串匹配。X M a t c h 容易扩展，可以支持在普通的结构化文本上进行的串匹配实验结果显示，本算法的效率比使用S A X 事件驱动的方法有明显的提高。A b 缸r a dR e s e a r c ho fS t r i n
5、gM a t c h i n gf o rI n t e r n e tC o n t e n tF i l t e r i n gL i u p i n gD i r e c t e db yB a iS h u oS t r i n gm a t c h i n g ，a l lo l d e s tp r o b l e mi nc o m p u t e rs c i e n c e ，c a l lb eu n d e r s t o o da st h ep r o b l e mo fs e a r c h i n gf o rap a t t e r nw i t hs o m
6、 ep r o p e r t yw i t h i nag i v e ns e q u e n c e T h es i m p l e s te a s ei sf i n d i n gag i v e ns t r i n gi n s i d eas e q u e n c e ，w h i c hs u f f e r e dag r e a td e a lo fr e s e a r c ha n ds o m ee x c e l l e n ta l g o r i t h m sw e r ep r o p o s e d R e c e n ty e a r s ，h
7、 o w e v e r , h a v ew i t n e s s e dad r a m a t i ci n c r e a s ei ni n t e r e s to ns t r i n gm a t c h i n gp r o b l e m s , e s p e c i a l l yw i t h i nt h er a p i d l yg r o w i n go f I n t e r n e ta n dC o m p u t a t i o n a lB i o l o g y W i t ht h ei n c r e a s eo f t h ea p p
8、 l i c a t i o no fI n t e m e t ，t h ei n f o r m a t i o ni nI n t e r n e ti sg r o w i n gr a p i d l y ；a n dh e n c er a i s e dag r e a tc h a l l e n g ef i n d i n gas p e c i f i ci n f o r m a t i o nt i m e l ya n de x a c t l ya n ds e c u r e l yi nt h eg i g a n t i ci n f o r m a t i
9、 o ns t r e a m F o rt h el a r g em a g n i t u d eo ft h ed a t a , t h er e a lt i m er e q u i r e m e n to ft h ei n f o r m a t i o nr e t r i e v a la n dt h es t r u c t u r a lp r o p e r t yo ft h em a t c h i n gt e x t ，i m p r o v e m e n to ft h ec l a s s i c a ls t r i n gm a t c h i
10、 n gt e c h n i q u e ss h o u l db em a d et Oo v e r c o m et h i sc h a l l e n g e T h i st h e s i ss u m m a r i z e so u ra t t e m p tt Os o l v et h e s eq u e s t i o n sa n da c h i e v es o m er e s u l t sa sf o l l o w ：1 P r o p e r t i e so fs o m ec l a s s i c a la l g o r i t h m
11、so nr a n d o md a t aw e r es u m m a r i z e da n da n a l y z e d T h ec u r r c n tr e s e a r c ho ft h es t r i n gm a t c h i n ga l g o r i t h m sw e r es u m m a r i z e di nt h i st h e s i s ，i n c l u d eo fs i n g l es t r i n gm a t c h i n ga l g o r i t h m s ，s u c ha sK M Pa l g o
12、 r i t h m ，B o y e r - M o o ra l g o r i t h ma n dB O Ma l g o r i t h m ，a n dm u l t i p l es t r i n gm a t c h i n ga l g o r i t h m s ，e g ，A h o C o r a s i c k ，W u M a n b e ra n dS B O Ma l g o r i t h m T h ea v e r a g et i m ec o m p l e x i t yo f t h o s ea l g o r i t h m sw e r e
13、a l s og i v e n , w h i c hW a sv a l i d a t e db yt e s t so nt h er a n d o md a t as e t s A sr e s u l t , f o u rp r o p e r t i e so fm u l t i p l es t r i n gm a t c h i n ga l g o r i t h mw e r eg i v e nt og u i d ea l g o r i t h m sd e s i g n i n g 2 Ap a r t i t i o ns t r a t e g y
14、w a sp r o p o s e df o rm u l t i p l es t r i n gm a t c h i n g E x p e r i m e n t a lr e s u l ts h o w st h a tt h es p e e do ft h ec l a s s i c a lm u l t i p l es t r i n gm a t c h i n ga l g o r i t h m sd e c r e a s e dr a p i d l yw h e nt h en u m b e ro fs t r i n g se x c e e d s5
15、0 0 0 T os o l v et h i sp r o b l e m ，ap a r t i t i o ns t r a t e g y6A b s t r a c tw a sp r o p o s e dt os p e e du p T w ot h e o r e m sa b o u tt h eo p t i m a lp a r t i t i o nw e r ep r o v e d ：o n ei st h ec o n t i n u i t yt h e o r e m ，a n dt h eo t h e ri st h es a m el e n g t
16、kp n r m i o nt h e o r e m 3 C O M ，am a t c h i n ga l g o r i t h mf o rl a r g es c a l eo fs t r i n g s ，w a sd e s i g n e da n di m p l e m e n t e d E m p l o y i n gt h ed y n a m i cp r o g r a m m i n go rs h o r t e s tp a t ht e c h n i q u e ，C O Mw o r k e do u tt h eo p t i m a lp a r t i t i o n , a n dt h e nc h o s et h eo p t i m a lm a t c h i n ga l g o r i t h mf o re a c hg r o u pb ya 仃m m n gp r o c e s s T h ee x p e r i m e n tr e s u l
