期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于Bloom filter的高效正则表达式匹配算法 被引量：4

Efficient regular expression matching algorithm based on Bloom filter
在线阅读 下载PDF
导出
摘要 针对确定有限自动机(DFA)的正则表达式匹配技术存在状态膨胀和一次状态转移只能处理单个字符的问题,提出了一种基于布鲁姆过滤器的正则表达式匹配算法。该算法将正则表达式中的每个确定字符串组成DFA的一个状态,添加比特向量完成匹配过程,并且在一次状态转移中根据确定字符串的匹配结果达到处理多个字符的目的。实验分析表明该算法有效降低了DFA状态的膨胀,提高了匹配速率。 Regular expression matching technology based on DFA requires prohibitively large amounts of memory and process only one character per transition. So this paper presented an efficient regular expression matching algorithm based on Bloom filter. Literal characters of regular expression were regards as a state of DFA, and introduced bit vector to realize the matching process. Then it could process variable characters per transition based on the result of literal characters matching. The result of simulation shows the algorithm not only reduces the required memory of DFA, but also increases the matching speed.
作者 李鲲鹏 兰巨龙 李印海
机构地区 国家数字交换系统工程技术研究中心
出处 《计算机应用研究》 CSCD 北大核心 2012年第3期950-954,共5页 Application Research of Computers
基金 国家"863"计划资助项目(2009AA01A346)
关键词 正则表达式 确定有限自动机 布鲁姆过滤器 比特向量 确定字符串 匹配概率 匹配速率 regular expression DFA Bloom filter bit vector literal characters matching probability matching speed
分类号 TP393.08 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献15

  • 1YU Fang, CHEN Zhi-feng, DIAO Yan-lei, et al. Fast and memory- efficient regular expression matching for deep packet inspection [ C ]// Proc of the 2006 ACM/IEEE Symposium on Architecture for Networ- king and Communications Systems. New York:ACM Press, 2006: 93-102.
  • 2KUMAR S, DHARMAPURIKAR S, YU Fang, et al. Algorithms to accelerate multiple regular expressions matching for deep packet in- spection [ C ]//Proc of SIGCOMM' 06. New York : ACM Press, 2006 : 339-350.
  • 3于强,霍红卫.一组提高存储效率的深度包检测算法[J].软件学报,2011,22(1):149-163. 被引量：14
  • 4KUMAR S, TURNER J, WILLIAMS J. Advanced algorithms for fast and scalable deep packet inspection [ C ]//Proc of ACM/IEEE Sym- posium on Architecture for Networking and Communications Systems. New York : ACM Press, 2006 : 81-92.
  • 5BECCHI M, CADAMBI S. Memory-efficient regular expression search using state merging[ C ]//Proc of IEEE INFOCOM. Washington DC: IEEE Press, 2007 : 1064-1072.
  • 6王磊,陈曙晖,苏金树,许孟晋.深度报文检测中基于GPU的正则表达式匹配引擎[J].计算机应用研究,2010,27(11):4324-4327. 被引量：10
  • 7BECCHI M, CROWLEY P. A hybrid finite automaton for practical deep packet inspection [ C ]//Proc of ACM CoNEXT Conference. New York:ACM Press, 2007: 1-12.
  • 8徐乾,鄂跃鹏,葛敬国,钱华林.深度包检测中一种高效的正则表达式压缩算法[J].软件学报,2009,20(8):2214-2226. 被引量：29
  • 9KUMAR S, CHANDRASEKARAN B, TURNER J, et al. Curing re- gular expressions matching algorithms from insomnia, amnesia and acalculia automata[ C]//Proc of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems. New York: ACM Press,2007 : 155-164.
  • 10SMITH R, ESTAN C, JHA S. XFA: faster signature matching with extended automata [ C ]//Proc of IEEE Symposium on Security and Privacy. Washington DC : IEEE Press, 2008 : 187- 201.

二级参考文献37

  • 1李伟男,鄂跃鹏,葛敬国,钱华林.多模式匹配算法及硬件实现[J].软件学报,2006,17(12):2403-2415. 被引量：42
  • 2Regular expression processor [ EB/OL ]. http ://www. titanicsystems. com/pdf/products/1. pdf.
  • 3BRODIE B C, TAYLOR D E, CYTRON R K. A scalable architecture for high-throughput regular-expression pattern matching [ J ]. SIGARCH Comput Archit News ,2006,34 ( 2 ) : 191 - 202.
  • 4SIDHU R, PRASANNA V K. Fast regular expression matching using FPGAs[ C ]//Proc of the 9th Annual IEEE Symposium on FCCM. Washington DC : IEEE Computer Society,2001:227- 238.
  • 5YU Fang, KATZ R H, LAKSHMAN T V. Gigabit rate packet pattern-matching using TCAM [ C ]//Proc of the 12th IEEE International Conference on Network Protocols. Washington DC : IEEE Computer Society,2004 : 174 - 183.
  • 6YU Jian-ming, LI Jun. A parallel NIDS pattern matching engine and its implementation on network processor [ C ]//Proc of International Conference on Security and Management. Las Vegas: CSREA Press, 2005:375-381.
  • 7LIU R Tong-tai, HUANG Nen-fu, KAO C N, et al. A fast patternmatch engine for network processor-based network intrusion detection system [ C ]//Proc of International Conference on Information Technology: Coding and Computing. Washington DC:IEEE Computer Society,2004:97-101.
  • 8CUDA programming guide [ EB/OL]. http://www, serc. iisc. ernet. in/ComputingFacilities/systems/Tesla _ Doc/NVIDIA _ CUDA _ Programming_Guide_2.3.pdf.
  • 9SMITH R, GOYAL N, ORMONTT J, et al. Evaluating GPUs for network packet signature matching[ C ]//Proc of International Symposium on Performance Analysis of Systems and Software. 2009.
  • 10SMITH R, ESTAN C, JHA S. XFA: faster signature matching with extended automata [ C ]//Proc of IEEE Symposium on Security and Privacy. Los Alamitos : IEEE Computer Society,2008 : 187- 201.

共引文献45

同被引文献36

  • 1吕丽珊.词语搭配——词汇研究的新视角[J].疯狂英语（教师版）,2007,0(2):58-59. 被引量：2
  • 2WHITE T. Hadoop: The Definitive Guide [ M ]. MA : O' Reilly Media, 2009 : 1 - 60.
  • 3MITZENMACHER M. Compressed Bloom filters [ J ]. IEEE-ACM Trans. on Networking, 2002, 10 (5) : 604 - 612.
  • 4L~MMEL R. Google' s MapReduce programming model-Revisited [ J ]. Science of Computer Program, 2008,70 ( 1 ) : 1 - 30.
  • 5LAM C. Hadoop in Action [ M ]. Stamford : Manning Publications, 2010:86 - 110.
  • 6GHEMAWAT S, GOBIOFF H, LEUNG S T. The gongle file system[ J ]. ACM SIGOPS Operating Systems Review,2003,37 (5) : 29 - 43.
  • 7BRODER A, MITZENMACHER M. Network applications of Bloom filters: A survey [ J ]. Intemet Mathematics, 2002, 1 (4) : 636 - 646.
  • 8GREMILLION L L. Designing a Bloom filter for differential file access [ J ]. Communications of the ACM, 1982, 25 (9) : 600 - 604.
  • 9JAMES K M. A second look at Bloom filters[J]. Communications of the ACM, 1983, 26(8) :570 -571.
  • 10Kumar S, Dharmapurikar S, Yu Fang, et al.Algorithms to accelerate multiple regular expressions matching for deep packet inspection[C]// Proceedings of the 2006 ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications.2006:339-350.

引证文献4

二级引证文献5

计算机应用研究
2012年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部