| 基于坏字符序检测的快速模式匹配算法 |
| |
| 引用本文： | 王浩,张霖. 基于坏字符序检测的快速模式匹配算法[J]. 计算机应用与软件, 2012, 29(5): 114-116,129 |
| |
| 作者姓名： | 王浩 张霖 |
| |
| 作者单位： | 安徽建筑工业学院信息网络中心 安徽 合肥 230022 |
| |
| 基金项目： | 安徽高校省级自然科学研究重点项目，安徽高校省级自然科学研究一般项目 |
| |
| 摘 要： | 提出一种基于坏字符序检测的快速模式匹配算法(BCSBM)。该算法利用相邻字符序列在模式串中不出现的概率较单字符高的特性,基于好字符和坏字符序表实现字符匹配过程的"跳跃"。BCSBM算法显著减少了匹配窗口内字符的匹配次数,同时增大了匹配窗口的平均移动距离。算法的实际测试效率较高,在文本或模式串相对较长的情况下该算法的效率提高明显。
|
| 关 键 词： | 模式匹配 字符序 BM算法 BMHS算法 |
QUICK PATTERN MATCHING ALGORITHM BASED ON BAD CHARACTER SEQUENCE CHECKING |
| |
| Wang Hao , Zhang Lin. QUICK PATTERN MATCHING ALGORITHM BASED ON BAD CHARACTER SEQUENCE CHECKING[J]. Computer Applications and Software, 2012, 29(5): 114-116,129 |
| |
| Authors: | Wang Hao Zhang Lin |
| |
| Affiliation: | Wang Hao Zhang Lin(Information and Network Center,Anhui Institute of Architecture and Industry,Hefei 230022,Anhui,China) |
| |
| Abstract: | The paper introduces BCSBM algorithm based on bad characters sequence checking.BCSBM algorithm takes advantages of the less probability of the presence of an adjacent character sequence than that of a single character within a pattern string,and realizes the jumping of the character matching process according to good characters and bad character sequences.BCSBM algorithm significantly reduces the times of character matching inside the matching window while increases the average movement distance of the matching window.As tested in reality,the algorithm’s efficiency is higher than other pattern matching algorithms,especially when there are longer texts or pattern strings. |
| |
| Keywords: | Pattern matching Character sequence BM algorithm BMHS algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
