|
|||||
|
|
| 一种基于子串识别的多模式串匹配算法 | |
| 引用本文： | 何慧敏,刘燕兵,谭建龙,郭莉.一种基于子串识别的多模式串匹配算法[J].计算机应用与软件,2011,28(11). |
| 作者姓名： | 何慧敏 刘燕兵 谭建龙 郭莉 |
| 作者单位： | 1. 中国科学院计算技术研究所 北京100190;中国科学院研究生院 北京100049 2. 中国科学院研究生院 北京100049;信息内容安全技术国家工程实验室 北京100190 3. 中国科学院计算技术研究所 北京100190;信息内容安全技术国家工程实验室 北京100190 |
| 基金项目： | 国家自然科学基金项目(61070026); 国家重点基础研究发展计划基金项目(2007CB311100) |
| 摘 要： | 多模式串匹配算法是网络内容过滤系统的核心技术。巨大的存储空间开销是制约多模式匹配串算法应用的瓶颈之一。提出一种基于子串识别的多模式匹配算法—HashBOM,该算法利用位哈希表存储模式串的子串信息以大幅度减少存储空间,利用递归哈希函数计算字符串的哈希值以实现快速匹配。理论分析表明,该算法的空间复杂度为O(rm~2),优于基于子串识别的匹配算法BOM的空间复杂度O(mr|∑|log_2mr);该算法搜索匹配过程的平均时间复杂度为O(nlog|∑|)mr/m,与BOM算法相同(其中m为最短模式串的长度,r为模式串的个数,n为待匹配文本的长度,|∑|为字母表的大小)。在随机数据集和真实数据集上的实验表明,该算法的存储空间远远低于BOM算法,而匹配速度与BOM算法相当,非常适合在线实时匹配的应用环境。 |
| 关 键 词： | 多模式串匹配算法 位哈希表 递归哈希函数 空间压缩 |
A SUBSTRING RECOGNITION BASED MULTIPLE PATTERNS STRING MATCHING ALGORITHM |
|
| He Huimin,Liu Yanbing,Tan Jianlong,Guo Li.A SUBSTRING RECOGNITION BASED MULTIPLE PATTERNS STRING MATCHING ALGORITHM[J].Computer Applications and Software,2011,28(11). | |
| Authors: | He Huimin Liu Yanbing Tan Jianlong Guo Li |
| Affiliation: | He Huimin~(1,2,3) Liu Yanbing~(1,3) Tan Jianlong~(1,3) Guo Li~(1,3) 1(Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China ) 2(Graduate School of the Chinese Academy of Sciences,Beijing 100049,China) 3(National Engineering Laboratory for Information Security Technologies,China) |
| Abstract: | |
| Keywords: | Multiple patterns string matching algorithm Bit hash map Recursive hash function Memory reduction |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
