一种降低误判率的BF快速匹配算法结构
字符串匹配在当前网络环境中得到了广泛的应用,为了提高匹配查找效率,快速发现疑似字符串,采用Bloom Filter算法是一种有效的手段.通过对BF算法的改进,将原始算法中的位数组个数增加为哈希函数的个数,使元素在每次哈希之后映射到不同的位数组中,同时用计数器对位置信息进行记录,使得BF算法结构对哈希函数之间相互独立性的要求有所降低.另外,本文提出的算法结构能够达到比原结构更低的误判率,从而降低非规则集合元素要进行精确匹配的概率,提高了查找匹配的运算效率,也便于规则集合的更新维护操作.需要指出的是,该结构实现算法性能的改善是在增加位数组个数的基础上的,即以增加向量空间大小为代价的,因此认为其更适用于软件处理的应用环境。
网络信息 查找匹配算法 结构特征 误判率
王春厚 许都 孙健
电子科技大学光互联网及移动信息网络研究中心,成都 611731
国内会议
昆明
中文
277-282
2010-08-07（万方平台首次上网日期，不代表论文的发表时间）