| 一种基于Bloom Filter的正则表达式集合快速搜索算法 |
| |
| 引用本文： | 徐克付,齐德昱,郑伟平,钱正平.一种基于Bloom Filter的正则表达式集合快速搜索算法[J].华南理工大学学报(自然科学版),2009,37(4). |
| |
| 作者姓名： | 徐克付 齐德昱 郑伟平 钱正平 |
| |
| 作者单位： | 华南理工大学,计算机系统结构研究所,广东,广州,510640 |
| |
| 基金项目： | 中国博士后自然科学基金，粤港关键领域重点突破项目 |
| |
| 摘 要： | 正则表达式搜索算法的性能与从非确定性有限状态自动机(NFA)的初始状态到终止状态的最短路径Lmin成正比,与正则表达式所表达的语言的前缀集合Pref(RE)成反比,而一般情况下Pref(RE)较大,确定Pref(RE)中的元素在目标文本中的出现位置比较困难.文中提出了一种基于Bloom Filter的正则表达式集合搜索算法,此算法利用Bloom Filter集合查询时间与集合大小无关的特点,可以快速准备定位Pref(RE)的出现位置,使得搜索速度不受Pref(RE)的影响,如果采用多个Bloom Filter并行,还可以间接增大Lmin.分析与测试结果表明,该算法较大地加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,在Lmin较长、Pref(RE)较大时,搜索速度可以提高数倍至数十倍,适合大规模的多正则表达式的快速搜索.
|
| 关 键 词： | 正则表达式匹配 自动机 模式匹配 |
A Fast Regular Expression Set Matching Algorithm Based on Bloom Filter |
| |
| Xu Ke-fu,Qi De-yu,Zheng Wei-ping,Qian Zheng-ping.A Fast Regular Expression Set Matching Algorithm Based on Bloom Filter[J].Journal of South China University of Technology(Natural Science Edition),2009,37(4). |
| |
| Authors: | Xu Ke-fu Qi De-yu Zheng Wei-ping Qian Zheng-ping |
| |
| Abstract: | |
| |
| Keywords: | Bloom Filter |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
