|
|
|
| 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 |
|
|
|
|
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.
|
|
Received: 06 April 2009
|
|
|
|
|
|
[1] Chang Y K, Tsai M L, Chung Y R. Multi-Character Processor Array for Pattern Matching in Network Intrusion Detection System // Proc of the 22nd International Conference on Advanced Information Networking and Applications. Okinawa, Japan, 2008: 991-996
[2] Zhou Xueguang, Zhang Huanguo. Flexible Pattern Matching Algorithm in Chinese Strings // Proc of the 27th Chinese Control Conference. Kunming, China, 2008: 610-614
[3] Huang Jian, Yang Zongkai, Du Xu, et al. FPGA Based High Speed and Low Area Cost Pattern Matching. // Proc of the IEEE TENCON. Melbourne, Australia, 2005: 1-5
[4] Liu Shengfei, Zhang Yunquan. Improved Pattern Matching Algorithm of BMH. Computer Science, 2008, 35(11): 164-165 (in Chinese)
(刘胜飞,张云泉.一种改进的BMH模式匹配算法.计算机科学, 2008, 35(11): 164-165)
[5] Lee P Y, Cheng A M K. HAL: A Faster Match Algorithm. IEEE Trans on Knowledge and Data Engineering, 2002, 14(5): 1047-1058
[6] Zhao Yijin. An Improved BM Algorithm for Pattern Matching in Strings. Computer Research and Development, 1998, 35(1): 46-49
[7] Zhang Lixia, Chen Li. Research and Improvement of Pattern Matching Algorithm. Microcomputer Information, 2008, 24(30): 68-70 (in Chinese)
(张丽霞,陈 莉.一种改进的模式匹配算法.微计算机信息, 2008, 24(30): 68-70)
[8] Li Bipeng, Xiao Shucheng, Li Yang. The Improving Algorithm of BM. Journal of Logistical Engineering University, 2008, 24(1): 54-57 (in Chinese)
(李必鹏,肖书成,李 洋.一种BM模式匹配的改进算法.后勤工程学院学报, 2008, 24(1): 54-57) |
|
|
|
2010, Vol. 23 
