基于位标识的可擦写高效过滤器算法与实现  

Algorithm and Implementation of Erasable High-efficiency Filter Based on Bit Mark

作　　者：雷蒙 肖文超 高佳宁 廖雪花[1] LEI Meng;XIAO Wen-chao;GAO Jia-ning;LIAO Xue-hua(School of Computer Science,Sichuan Normal University,Chengdu 610101,China;College of Physics and Electronic Engineering,Sichuan Normal University,Chengdu 610101,China)

机构地区：[1]四川师范大学计算机科学学院,四川成都610101 [2]四川师范大学物理与电子工程学院,四川成都610101

出　　处：《软件导刊》2022年第8期120-125,共6页Software Guide

摘　　要：针对当前传统布隆过滤器元素删除困难及难以消除误判率等问题,提出一种新型的基于位标识的可擦写高效过滤器算法。该算法采用改进后的前缀树构造可擦写高效过滤器,利用其结构特点解决传统布隆过滤器中元素删除困难问题及实现0误判率。根据性能优化策略,基于位标识改进传统的R向前缀树,极大降低了内存消耗。实验结果表明,该算法能够高效完成字符串的检索及过滤,在保证时间复杂度的前提下,减少内存空间消耗,且能够删除过滤器元素,实现0误判率,适用于高并发场景下的系统应用。Aiming at the problems of the current traditional Bloom filter element deletion difficulty and the difficulty of eliminating the false judgment rate,a new type of erasable high-efficiency filter algorithm based on bit identification is proposed.The algorithm uses an improved prefix tree to construct an erasable high-efficiency filter,and uses its structural characteristics to solve the problem of difficult element dele⁃tion in the traditional Bloom filter and achieve zero misjudgment rate.According to the performance optimization strategy,the traditional R-di⁃rection prefix tree is improved based on the bit mark,which greatly reduces the memory consumption.Experimental results show that this algo⁃rithm can efficiently complete the retrieval and filtering of strings,reduce the consumption of memory space under the premise of ensuring time complexity,and can delete filter elements to achieve zero false positive rate,which is suitable for high concurrency scenarios system applica⁃tions.

关 键 词：位标识 前缀树 布隆过滤器 可擦写过滤器 字符串检索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]