【摘要】 针对当前传统布隆过滤器元素删除困难及难以消除误判率等问题，提出一种新型的基于位标识的可擦写高效过滤器算法。该算法采用改进后的前缀树构造可擦写高效过滤器，利用其结构特点解决传统布隆过滤器中元素删除困难问题及实现0误判率。根据性能优化策略，基于位标识改进传统的R向前缀树，极大降低了内存消耗。实验结果表明，该算法能够高效完成字符串的检索及过滤，在保证时间复杂度的前提下，减少内存空间消耗，且能够删除过滤器元素，实现0误判率，适用于高并发场景下的系统应用。更多还原

【Abstract】 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 deletion in the traditional Bloom filter and achieve zero misjudgment rate. According to the performance optimization strategy,the traditional R-direction prefix tree is improved based on the bit mark,which greatly reduces the memory consumption. Experimental results show that this algorithm 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 applications.更多还原