串匹配算法中模式串与文本之间关系的研究.pdf

文档介绍：ISSN 1000-9825, CODEN RUXUEW E-mail: ******@iscas.
Journal of Software, , , July 2010, −1514
doi: . Tel/Fax: [phone]
© by Institute of Software, the Chinese Academy of Sciences. All rights reserved.

∗
串匹配算法中模式串与文本之间关系的研究
刘萍 1,3+, 刘燕兵 1,2,3, 郭莉 1,3, 方滨兴 1,3
1(中国科学院计算技术研究所,北京 100190)
2(中国科学院研究生院,北京 100049)
3(信息内容安全技术国家工程实验室,北京 100190)
Research on Relationship Between Patterns and Text in String Matching Algorithms
LIU Ping1,3+, LIU Yan-Bing1,2,3, GUO Li1,3, FANG Bin-Xing1,3
1(Institute puting Technology, The Chinese Academy of Sciences, Beijing 100190, China)
2(Graduate University, The Chinese Academy of Sciences, Beijing 100049, China)
3(National Engineering Laboratory for Information Security Technologies, Beijing 100190, China)
+ Corresponding author: E-mail: ******@ict.
Liu P, Liu YB, Guo L, Fang BX. Research on relationship between patterns and text in string matching
algorithms. Journal of Software, 2010,21(7):1503−1514. /1000-9825/
Abstract: It was assumed that the pattern and text characters are independent and uniformly distributed over a
finite alphabet in classical string matching algorithms, and this assumption differs from real applications and causes
many problems. Considering the probability distributions, the contexts of the characters, and the convenience of
applications, this paper gives a concept hit rate and four extended concepts about it. Then it gives the theory
analysis and detailed experiments with hit rate on the four classical algorithms. The map of the relationships is
obtained between the hit rate and the algorithms’ performance, and at the same time some valuable conclusions are
made through above work. As a character variable, hit rate describes the relativity of patterns and text and can serve
as guidelines in the algorithms design, analysis and some other extended research fields of the string matching.
Key words: string mat