一种改进的字符串模式匹配算法  

An Improved Character String Pattern Matching Algorithm

作　　者：胡金柱[1] 熊春秀[1] 舒江波[1] 周星[1] 程文涛[1] 

机构地区：[1]华中师范大学计算机科学系,武汉430079

出　　处：《模式识别与人工智能》2010年第1期103-106,共4页Pattern Recognition and Artificial Intelligence

基　　金：国家教育部重点研究基地重大研究项目(No.07JJD740063);湖北省科技攻关项目(No.2007AA101c49)资助

摘　　要：提出一种改进的字符串模式匹配算法.该算法对文本串进行预处理,即对文本串中不存在于模式串中的字符以及文本串中剩下的出现次数最少的字符分别进行标记,再通过匹配模式串的首尾字符来减少出现次数最少的字符的标记个数.发生匹配失败时,将模式串直接滑动到标记了的出现次数最少的字符处.通过实验证明,该算法的移动次数和比较次数有较大减少,耗费的额外空间的大小也不超过模式串的长度,进一步提高模式匹配的效率.By analyzing a variety of improved pattern matching algorithms, an pattern improved. Firstly, the text string is preprocessed. Two kinds of characters are made in the pattern string, and the other is the characters that appear the least. Secondly, matching algorithm is up. One does not exist through matching both the first character and the last character of the pattern string, the number of the marked characters which appear the least is reduced. If the matching fails, the pattern string directly slides to the next marked character which appears the least. Finally, experimental results show that the frequencies of the movement and the comparison decreased greatly by the improved algorithm, and the additional cost of space is less than the length of the pattern string. Moreover, the efficiency of the pattern matching is improved.

关 键 词：模式匹配 文本串 模式串 预处理 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]