模式识别与人工智能
2025年4月4日 星期五   首 页     期刊简介     编委会     投稿指南     伦理声明     联系我们                                                                English
模式识别与人工智能  2010, Vol. 23 Issue (1): 103-106    DOI:
研究与应用 最新目录| 下期目录| 过刊浏览| 高级检索 |
一种改进的字符串模式匹配算法
胡金柱,熊春秀,舒江波,周星,程文涛
华中师范大学 计算机科学系 武汉 430079
An Improved Character String Pattern Matching Algorithm
HU Jin-Zhu,XIONG Chun-Xiu,SHU Jiang-Bo,ZHOU Xin,CHENG Wen-Tao
Department of Computer Science,Huazhong Normal University,Wuhan 430079

全文: PDF (279 KB)   HTML (1 KB) 
输出: BibTeX | EndNote (RIS)      
摘要 提出一种改进的字符串模式匹配算法。该算法对文本串进行预处理,即对文本串中不存在于模式串中的字符以及文本串中剩下的出现次数最少的字符分别进行标记,再通过匹配模式串的首尾字符来减少出现次数最少的字符的标记个数。发生匹配失败时,将模式串直接滑动到标记了的出现次数最少的字符处。通过实验证明,该算法的移动次数和比较次数有较大减少,耗费的额外空间的大小也不超过模式串的长度,进一步提高模式匹配的效率。
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
胡金柱
熊春秀
舒江波
周星
程文涛
关键词 模式匹配文本串模式串预处理    
Abstract:By analyzing a variety of improved pattern matching algorithms, an pattern matching algorithm is improved. Firstly, the text string is preprocessed. Two kinds of characters are made up. One does not exist in the pattern string, and the other is the characters that appear the least. Secondly, 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.
Key wordsPattern Matching    Text String    Pattern String    Preprocessing   
收稿日期: 2009-04-06     
ZTFLH: TP391  
基金资助:国家教育部重点研究基地重大研究项目(No.07JJD740063)、湖北省科技攻关项目(No.2007AA101c49)资助
作者简介: 胡金柱,男,1947年生,教授,主要研究方向为软件工程与分布式信息系统.E-mail:xiongchunxiu@126.com.熊春秀,女,1984年生,硕士研究生,主要研究方向为软件工程与分布式信息系统.舒江波,男,1982年生,博士研究生,主要研究方向为软件工程、中文信息处理.周星,女,1985年生,硕士研究生,主要研究方向为软件工程与分布式信息系统.程文涛,男,1982年生,硕士研究生,主要研究方向为软件工程与分布式信息系统.
引用本文:   
胡金柱,熊春秀,舒江波,周星,程文涛. 一种改进的字符串模式匹配算法[J]. 模式识别与人工智能, 2010, 23(1): 103-106. HU Jin-Zhu,XIONG Chun-Xiu,SHU Jiang-Bo,ZHOU Xin,CHENG Wen-Tao. An Improved Character String Pattern Matching Algorithm. , 2010, 23(1): 103-106.
链接本文:  
http://manu46.magtech.com.cn/Jweb_prai/CN/      或     http://manu46.magtech.com.cn/Jweb_prai/CN/Y2010/V23/I1/103
版权所有 © 《模式识别与人工智能》编辑部
地址:安微省合肥市蜀山湖路350号 电话:0551-65591176 传真:0551-65591176 Email:bjb@iim.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn