基于動態布隆姆過濾器的海量信息臺賬數據消重算法

鄒岳琳 張龍軍 劉昆

摘要：文章從電網發展和企業實際需求出發，應用海量數據去重算法，分析研究了動態布隆姆過濾器的海量信息臺賬數據消重算法。

關鍵詞：布隆姆過濾器;海量臺賬;數據去重

中圖分類號：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