一种基于子串识别的多模式串匹配算法

• 作者: 何慧敏 刘燕兵 谭建龙 郭莉
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 多模式串匹配算法 位哈希表 递归哈希函数 空间压缩
• 年，卷（期）: 2011,（11）
• 所属期刊栏目: 基金项目论文
• 页码范围: 10-14,56
• 分类号: TP301.5
• 字数: 6858字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2011.11.003

摘要

多模式串匹配算法是网络内容过滤系统的核心技术.巨大的存储空间开销是制约多模式匹配串算法应用的瓶颈之一.提出一种基于子串识别的多模式匹配算法—HashBOM,该算法利用位哈希表存储模式串的子串信息以大幅度减少存储空间,利用递归哈希函数计算字符串的哈希值以实现快速匹配.理论分析表明,该算法的空间复杂度为O(rm2),优于基于子串识别的匹配算法BOM的空间复杂度O(mr|∑|log2 mr)；该算法搜索匹配过程的平均时间复杂度力O((nlog|∑|mr)/m),与BOM算法相同(其中m为最短模式串的长度,r为模式串的个数,n为待匹配文本的长度,|∑|为字母表的大小).在随机数据集和真实数据集上的实验表明,该算法的存储空间远远低于BOM算法,而匹配速度与BOM算法相当,非常适合在线实时匹配的应用环境.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谭建龙	中国科学院计算技术研究所	43	444	11.0	19.0
3	郭莉	中国科学院计算技术研究所	64	788	14.0	26.0
5	刘燕兵		20	149	7.0	11.0
13	何慧敏	中国科学院计算技术研究所	1	5	1.0	1.0