| 串匹配算法中模式串与文本之间关系的研究 |
| |
| 引用本文： | 刘 萍,刘 萍,刘燕兵,郭 莉,方滨兴.串匹配算法中模式串与文本之间关系的研究[J].软件学报,2010,21(7):1503-1514. |
| |
| 作者姓名： | 刘 萍 刘 萍 刘燕兵 郭 莉 方滨兴 |
| |
| 作者单位： | 1. 中国科学院,计算技术研究所,北京,100190;信息内容安全技术国家工程实验室,北京,100190
2. 中国科学院,计算技术研究所,北京,100190;中国科学院,研究生院,北京,100049;信息内容安全技术国家工程实验室,北京,100190 |
| |
| 基金项目： | Supported by the National Basic Research Program of China under Grant No.2007CB311100 (国家重点基础研究发展计划(973)) |
| |
| 摘 要： | 经典的串匹配算法设计和分析中假设“字符互相独立并且等概率出现”,这与实际应用环境差异很大,导致出现很多问题.考虑了字符的概率分布和上下文的关联,同时兼顾应用的方便,提出了命中密度的概念.在给出基本定义和扩展定义后,通过对4种类型的代表性算法的理论和实验分析,给出了命中密度与算法性能之间的关系.同时,在对命中密度的分析中得出一些极具价值的结论.对命中密度概念的多角度理解以及对它与算法性能关系的深入剖析都说明,命中密度作为一个特征量,可以从一个侧面刻画模式串和文本之间的相关性,它对算法的设计和分析以及串匹配领域研究工作的扩展都具有指导意义.
|
| 关 键 词： | 串匹配 字符概率分布 字符串相关性 |
| 收稿时间： | 2008/9/25 0:00:00 |
| 修稿时间： | 2009/3/31 0:00:00 |
Research on Relationship Between Patterns and Text in String Matching Algorithms |
| |
| LIU Ping,LIU Ping,LIU Yan-Bing,GUO Li and FANG Bin-Xing.Research on Relationship Between Patterns and Text in String Matching Algorithms[J].Journal of Software,2010,21(7):1503-1514. |
| |
| Authors: | LIU Ping LIU Ping LIU Yan-Bing GUO Li and FANG Bin-Xing |
| |
| Affiliation: | LIU Ping1,3,LIU Yan-Bing1,2,GUO Li1,FANG Bin-Xing1,3 1(Institute of Computing Technology,The Chinese Academy of Sciences,Beijing 100190,China) 2(Graduate University,Beijing 100049,China) 3(National Engineering Laboratory for Information Security Technologies,China) |
| |
| 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 alg... |
| |
| Keywords: | string matching probability distributions of character relativity of strings |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
