当前位置: 首页 » 资料 » 健康论文 » 一种基于Bloom Filter的正则表达式集合快速搜索算法

一种基于Bloom Filter的正则表达式集合快速搜索算法

放大字体  缩小字体 更新日期:2018-11-26  浏览次数:2
摘 要:正则表达式搜索算法的性能与从非确定性有限状态自动机(NFA)的初始状态到终止状态的最短路径Lmin成正比,与正则表达式所表达的语言的前缀集合Pref(RE)成反比,而一般情况下Pref(RE)较大,确
  • 【题 名】一种基于Bloom Filter的正则表达式集合快速搜索算法
  • 【作 者】徐克付 齐德昱 郑伟平 钱正平
  • 【机 构】华南理工大学计算机系统结构研究所 广东广州510640
  • 【刊 名】《华南理工大学学报:自然科学版》2009年 第4期 37-41页 共5页
  • 【关键词】正则表达式匹配 Bloom Filter 自动机 模式匹配
  • 【文 摘】正则表达式搜索算法的性能与从非确定性有限状态自动机(NFA)的初始状态到终止状态的最短路径Lmin成正比,与正则表达式所表达的语言的前缀集合Pref(RE)成反比,而一般情况下Pref(RE)较大,确定Pref(RE)中的元素在目标文本中的出现位置比较困难.文中提出了一种基于Bloom Filter的正则表达式集合搜索算法,此算法利用Bloom Filter集合查询时间与集合大小无关的特点,可以快速准备定位Pref(RE)的出现位置,使得搜索速度不受Pref(RE)的影响,如果采用多个Bloom Filter并行,还可以间接增大Lmin.分析与测试结果表明,该算法较大地加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,在Lmin较长、Pref(RE)较大时,搜索速度可以提高数倍至数十倍,适合大规模的多正则表达式的快速搜索.
 
本文导航:
  • (1) 正则表达式匹配,Bloom,Filter,自动机,模式匹配
  • 下一篇:鳖甲
  • 上一篇:暂无
 
[ 资料搜索 ]  [ 加入收藏 ]  [ 告诉好友 ]  [ 打印本文 ]  [ 关闭窗口 ]

 

 
推荐图文
推荐资料
热门关注