基于动态布隆姆过滤器的海量信息台账数据消重算法

邹岳琳 张龙军 刘昆

摘要：文章从电网发展和企业实际需求出发，应用海量数据去重算法，分析研究了动态布隆姆过滤器的海量信息台账数据消重算法。

关键词：布隆姆过滤器;海量台账;数据去重

中图分类号：TH71    文献标识码：A    文章编号：1007-9416（2018）10-0000-00

1 引言

公司营销业务长期存在计量装置更换时表计止度录入不准确、一年内换表频繁、计量装置更换后长期未采集到电量、增减容电量异常、销户用户欠费、电价与电压不匹配等情况，影响了用电客户满意度，同时也影响公司的合理利益，但由于相关业务牵扯系统众多，数据量庞大，传统的系统架构受到存储及计算能力的限制，无法开展有效的监测;随着公司大数据平台及全业务统一数据中心分析域的推广，提供了海量存储及高效计算能力，为了不断增强营销业务监测的广度、深度、准度及有效度，防范公司电费回收风险，保障公司合理收益。

2 布隆姆过滤器研究

布隆姆过滤器是1970年由Burton Howard Bloom提出的。该算法也是一种数据结构，用于判断一个元素是否存在一个集合中，其优点是能够快速检索，检索时间和空间效率都超过一般算法，非常适合海量信息台账数据的重复数据查找。最初布隆姆过滤被用在数据库检索系统、拼写检查等应用领域，后期随着信息技术高速发展，也应用于垃圾邮件过滤等，应用领域更加专业化。

2.1 静态布隆姆过滤器

静态布隆姆过滤器，其设置了数据集合A，A={a_1，a_2，a_3…a_n}，集合A为待操作的集合，在集合A加入新元素时，首先检索集合A，判断新元素是否存在集合A中，如果相应位置1，可判断元素存在集合A中，否则判定不在集合A中。在这种情况下，可能存在尚未映射到集合A中的元素，也就是不在集合A中元素被判定存在集合A。因此通过布隆姆过滤器计算后，某位为0的概率：P_0=〖（1-1/m）〗^kn≈e^（-kn/m），同时存在误判的概率：P=（1-P_0 ）^k=〖（1-e^（-kn/m））〗^k。

2.2 动态布隆姆过滤器

由于静态布隆姆过滤器没有考虑动态数据集合，因为在2006年又有学者提出了动态布隆姆过滤器。这种数据结构将动态数据集合A表示为一个m行n列的位矩阵，而这个矩阵的每一行都可以看成是一个静态布隆姆过滤器，其中m0=1。n0动态布隆姆过滤器的位结构图1所示。

3 海量信息台账数据消重算法的实现

3.1 应用背景

随着信息化在企业经营中受到越来越多的重视，信息系统设备数量急剧增加，信息设备台账形成海量数据规模，设备监管任务也随之加重。这就对信息设备基础台账维护提出了更高的要求，需要海量台账数据维护具有完整性、及时性，高效性，以便准确实现信息设备的实时监控。这也使得对信息台账维护人员提出了更高要求，一是需要维护人员具有一定专业知识，二是需要维护人员能够及时、准确的开展维护工作。但目前运维人员数量明显跟不上信息设备的增长速度，且运维人员专业素质不高，导致维护不及时、台账质量不高，信息设备监控率因而不能很好提升。

3.2 基于动态布隆姆的算法改进

本文针对海量信息台账数据消重，为了提高消重效率，兼顾台账动态扩展的需求，提出了改进的动态布隆姆过滤器算法。不同于用s×r個m位来表示静态布隆姆过滤器位串，该算法使用s个r×m的位矩阵，使得其更加适用于海量动态增长台账数据集合，极大地降低了重复台账数据查询的平均时间复杂度。

在本算法中，基本思想是将海量台账动态数据集合A表示成s个t×m 的位矩阵，其拥有t行、m列，t的取值范围根据台账数据集合的大小选定。在动态布隆姆过滤器创建初始，s值被置位1，并随着海量台账数据集合的增长而不断的增大.

3.3 海量台账数据消重的主要流程

针对已有的海量台账数据，在发生设备新增、删除、变更时，对台账维护的检索是非常耗时的，特别是批量新增台账时，需逐一核对新增设备是否已经存在设备台账中。尤其是海量台账数据通常索引表比较大，因而基本持久化存储在硬盘中，采取三级查询方式。在三级查询中，首先通过动态布隆姆过滤器检索重复台账数据，这一步骤直接决定了改进算法对于重复台账数据检索的效率。通过改进的布隆姆过滤器，快速判定新增台账条目是否存在已有海量台账集合中，提高检索性能。若新增台账数据被布隆姆过滤器过滤，说明该新增台账条目不存在已有海量台账库中，即可判定为需维护新增项，否则说明该台账条目可能存在。若判定为存在再到哈希缓存中查询，如果找到则说明该台账信息已存在，否则到硬盘中查询。通过三级查询方式，有效的减少对硬盘访问次数，快速实现重复台账去重，提高台账维护效率及质量。

4 实验结论与分析

为了验证改进的动态布隆姆过滤器矩阵集合对于提高重复台账数据识别性能的有效性，将应用了基于动态布隆姆过滤器的海量信息台账数据消重算法与原消重方法性能进行比较，其中测试数据随机选取的地市导出信息设备台账6.7M、7.9M、6.5M。改进的动态布隆姆过滤器能够快速判断需导入信息设备台账是否存在于已有设备台账中，从而删除重复台账信息，减少重复数据处理所需时间，进而提高海量台账重复数据维护的时间性能和消重性能。

5 结语

基于动态布隆过滤器的海量信息台账数据消重算法的实现与应用，是结合企业业务实际，为规范化运维，提高信息设备资源纳管及时率，提升自动化运维水平，解决目前设备台账可信赖度低等实际问题，实现的技术创新。目前已在企业推广应用，实现大批量设备台账快速消重，减少运维人员进行设备维护的重复性工作，利于及时监控信息设备运行状态，提高运维工作效率，降低了信息设备维护成本，有效实现信息设备自动监控率提升。

Based on Dynamic Brom Filter Mass Information Ledger Data Deweighting Algorithm

ZOU Yue-lin， ZHANG Long-jun， LIU Kun

（State Grid Xinjiang Electric Power Co.， Ltd. Information Communication Company ， Urumchi Xinjiang 830000）

Abstract： Starting from the development of power grid and the actual needs of enterprises， this paper applies the algorithm of mass data de-duplication to analyze and study the algorithm of mass information account data de-duplication of dynamic Bloom filter.

Key words： bloom filter; massive ledger; data removal