改进的KR模式匹配算法的研究与实现  

On Implementation of Improved Karp-Rabin Pattern Matching Algorighmic

作　　者：巫喜红[1] 

机构地区：[1]嘉应学院计算机学院,广东梅州514015

出　　处：《西南师范大学学报（自然科学版）》2016年第10期124-129,共6页Journal of Southwest China Normal University(Natural Science Edition)

基　　金：广东省科技计划项目(2013B040500010);2016年嘉应学院自然科学重点项目(2016KJZ04)

摘　　要：文章在详细分析KR匹配算法的基础上,提出了改进的I_KR算法.I_KR算法的改进之处:一是采用2次Hash函数的方法在计算T的子串的散列值之后,马上与P的散列值进行比较;二是采用双向并行方式进行匹配.为了分析I_KR算法的性能,从不同文本串和模式串角度,在匹配次数和比较的字符个数方面对I_KR算法进行实验.实验结果表明,I_KR算法能够极大地减少匹配次数,缩短匹配时间,有效地提高模式匹配速度.An improved Karp-Rabin（I_KR）algorithm has been promoted in this paper for string matching based on the detailed analysis of Karp-Rabin（KR）algorithm.The improvements of I_KR algorithm are in two ways：one is that,after the hashed value of the T＇substrings,two times Hash functions has been used,which is compared with the hashed value of the P;the other is that bidirectional parallel is used when matching.To analyze the performance of the I_KR algorithm,some experiments have been done from some aspects which are matched times and compared characters＇ numbers through the number of different text strings and pattern strings.The experimental results show the I_KR algorithm can reduce the times of matching and shorten the time of matching.The I_KR algorithm enhances the algorithm＇s speed effectively.

关 键 词：KR算法 I_KR算法 HASH函数 双向并行 模式匹配 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]