鄒岳琳 張龍軍 劉昆

摘要：文章從電網(wǎng)發(fā)展和企業(yè)實(shí)際需求出發(fā)，應(yīng)用海量數(shù)據(jù)去重算法，分析研究了動(dòng)態(tài)布隆姆過(guò)濾器的海量信息臺(tái)賬數(shù)據(jù)消重算法。

關(guān)鍵詞：布隆姆過(guò)濾器;海量臺(tái)賬;數(shù)據(jù)去重

中圖分類號(hào)：TH71? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? 文章編號(hào)：1007-9416（2018）10-0000-00

1 引言

公司營(yíng)銷業(yè)務(wù)長(zhǎng)期存在計(jì)量裝置更換時(shí)表計(jì)止度錄入不準(zhǔn)確、一年內(nèi)換表頻繁、計(jì)量裝置更換后長(zhǎng)期未采集到電量、增減容電量異常、銷戶用戶欠費(fèi)、電價(jià)與電壓不匹配等情況，影響了用電客戶滿意度，同時(shí)也影響公司的合理利益，但由于相關(guān)業(yè)務(wù)牽扯系統(tǒng)眾多，數(shù)據(jù)量龐大，傳統(tǒng)的系統(tǒng)架構(gòu)受到存儲(chǔ)及計(jì)算能力的限制，無(wú)法開(kāi)展有效的監(jiān)測(cè);隨著公司大數(shù)據(jù)平臺(tái)及全業(yè)務(wù)統(tǒng)一數(shù)據(jù)中心分析域的推廣，提供了海量存儲(chǔ)及高效計(jì)算能力，為了不斷增強(qiáng)營(yíng)銷業(yè)務(wù)監(jiān)測(cè)的廣度、深度、準(zhǔn)度及有效度，防范公司電費(fèi)回收風(fēng)險(xiǎn)，保障公司合理收益。

2 布隆姆過(guò)濾器研究

布隆姆過(guò)濾器是1970年由Burton Howard Bloom提出的。該算法也是一種數(shù)據(jù)結(jié)構(gòu)，用于判斷一個(gè)元素是否存在一個(gè)集合中，其優(yōu)點(diǎn)是能夠快速檢索，檢索時(shí)間和空間效率都超過(guò)一般算法，非常適合海量信息臺(tái)賬數(shù)據(jù)的重復(fù)數(shù)據(jù)查找。最初布隆姆過(guò)濾被用在數(shù)據(jù)庫(kù)檢索系統(tǒng)、拼寫檢查等應(yīng)用領(lǐng)域，后期隨著信息技術(shù)高速發(fā)展，也應(yīng)用于垃圾郵件過(guò)濾等，應(yīng)用領(lǐng)域更加專業(yè)化。

2.1 靜態(tài)布隆姆過(guò)濾器

靜態(tài)布隆姆過(guò)濾器，其設(shè)置了數(shù)據(jù)集合A，A={a_1，a_2，a_3…a_n}，集合A為待操作的集合，在集合A加入新元素時(shí)，首先檢索集合A，判斷新元素是否存在集合A中，如果相應(yīng)位置1，可判斷元素存在集合A中，否則判定不在集合A中。在這種情況下，可能存在尚未映射到集合A中的元素，也就是不在集合A中元素被判定存在集合A。因此通過(guò)布隆姆過(guò)濾器計(jì)算后，某位為0的概率：P_0=〖（1-1/m）〗^kn≈e^（-kn/m），同時(shí)存在誤判的概率：P=（1-P_0 ）^k=〖（1-e^（-kn/m））〗^k。

2.2 動(dòng)態(tài)布隆姆過(guò)濾器

由于靜態(tài)布隆姆過(guò)濾器沒(méi)有考慮動(dòng)態(tài)數(shù)據(jù)集合，因?yàn)樵?006年又有學(xué)者提出了動(dòng)態(tài)布隆姆過(guò)濾器。這種數(shù)據(jù)結(jié)構(gòu)將動(dòng)態(tài)數(shù)據(jù)集合A表示為一個(gè)m行n列的位矩陣，而這個(gè)矩陣的每一行都可以看成是一個(gè)靜態(tài)布隆姆過(guò)濾器，其中m0=1。n0動(dòng)態(tài)布隆姆過(guò)濾器的位結(jié)構(gòu)圖1所示。

3 海量信息臺(tái)賬數(shù)據(jù)消重算法的實(shí)現(xiàn)

3.1 應(yīng)用背景

隨著信息化在企業(yè)經(jīng)營(yíng)中受到越來(lái)越多的重視，信息系統(tǒng)設(shè)備數(shù)量急劇增加，信息設(shè)備臺(tái)賬形成海量數(shù)據(jù)規(guī)模，設(shè)備監(jiān)管任務(wù)也隨之加重。這就對(duì)信息設(shè)備基礎(chǔ)臺(tái)賬維護(hù)提出了更高的要求，需要海量臺(tái)賬數(shù)據(jù)維護(hù)具有完整性、及時(shí)性，高效性，以便準(zhǔn)確實(shí)現(xiàn)信息設(shè)備的實(shí)時(shí)監(jiān)控。這也使得對(duì)信息臺(tái)賬維護(hù)人員提出了更高要求，一是需要維護(hù)人員具有一定專業(yè)知識(shí)，二是需要維護(hù)人員能夠及時(shí)、準(zhǔn)確的開(kāi)展維護(hù)工作。但目前運(yùn)維人員數(shù)量明顯跟不上信息設(shè)備的增長(zhǎng)速度，且運(yùn)維人員專業(yè)素質(zhì)不高，導(dǎo)致維護(hù)不及時(shí)、臺(tái)賬質(zhì)量不高，信息設(shè)備監(jiān)控率因而不能很好提升。

3.2 基于動(dòng)態(tài)布隆姆的算法改進(jìn)

本文針對(duì)海量信息臺(tái)賬數(shù)據(jù)消重，為了提高消重效率，兼顧臺(tái)賬動(dòng)態(tài)擴(kuò)展的需求，提出了改進(jìn)的動(dòng)態(tài)布隆姆過(guò)濾器算法。不同于用s×r個(gè)m位來(lái)表示靜態(tài)布隆姆過(guò)濾器位串，該算法使用s個(gè)r×m的位矩陣，使得其更加適用于海量動(dòng)態(tài)增長(zhǎng)臺(tái)賬數(shù)據(jù)集合，極大地降低了重復(fù)臺(tái)賬數(shù)據(jù)查詢的平均時(shí)間復(fù)雜度。

在本算法中，基本思想是將海量臺(tái)賬動(dòng)態(tài)數(shù)據(jù)集合A表示成s個(gè)t×m 的位矩陣，其擁有t行、m列，t的取值范圍根據(jù)臺(tái)賬數(shù)據(jù)集合的大小選定。在動(dòng)態(tài)布隆姆過(guò)濾器創(chuàng)建初始，s值被置位1，并隨著海量臺(tái)賬數(shù)據(jù)集合的增長(zhǎng)而不斷的增大.

3.3 海量臺(tái)賬數(shù)據(jù)消重的主要流程

針對(duì)已有的海量臺(tái)賬數(shù)據(jù)，在發(fā)生設(shè)備新增、刪除、變更時(shí)，對(duì)臺(tái)賬維護(hù)的檢索是非常耗時(shí)的，特別是批量新增臺(tái)賬時(shí)，需逐一核對(duì)新增設(shè)備是否已經(jīng)存在設(shè)備臺(tái)賬中。尤其是海量臺(tái)賬數(shù)據(jù)通常索引表比較大，因而基本持久化存儲(chǔ)在硬盤中，采取三級(jí)查詢方式。在三級(jí)查詢中，首先通過(guò)動(dòng)態(tài)布隆姆過(guò)濾器檢索重復(fù)臺(tái)賬數(shù)據(jù)，這一步驟直接決定了改進(jìn)算法對(duì)于重復(fù)臺(tái)賬數(shù)據(jù)檢索的效率。通過(guò)改進(jìn)的布隆姆過(guò)濾器，快速判定新增臺(tái)賬條目是否存在已有海量臺(tái)賬集合中，提高檢索性能。若新增臺(tái)賬數(shù)據(jù)被布隆姆過(guò)濾器過(guò)濾，說(shuō)明該新增臺(tái)賬條目不存在已有海量臺(tái)賬庫(kù)中，即可判定為需維護(hù)新增項(xiàng)，否則說(shuō)明該臺(tái)賬條目可能存在。若判定為存在再到哈希緩存中查詢，如果找到則說(shuō)明該臺(tái)賬信息已存在，否則到硬盤中查詢。通過(guò)三級(jí)查詢方式，有效的減少對(duì)硬盤訪問(wèn)次數(shù)，快速實(shí)現(xiàn)重復(fù)臺(tái)賬去重，提高臺(tái)賬維護(hù)效率及質(zhì)量。

4 實(shí)驗(yàn)結(jié)論與分析

為了驗(yàn)證改進(jìn)的動(dòng)態(tài)布隆姆過(guò)濾器矩陣集合對(duì)于提高重復(fù)臺(tái)賬數(shù)據(jù)識(shí)別性能的有效性，將應(yīng)用了基于動(dòng)態(tài)布隆姆過(guò)濾器的海量信息臺(tái)賬數(shù)據(jù)消重算法與原消重方法性能進(jìn)行比較，其中測(cè)試數(shù)據(jù)隨機(jī)選取的地市導(dǎo)出信息設(shè)備臺(tái)賬6.7M、7.9M、6.5M。改進(jìn)的動(dòng)態(tài)布隆姆過(guò)濾器能夠快速判斷需導(dǎo)入信息設(shè)備臺(tái)賬是否存在于已有設(shè)備臺(tái)賬中，從而刪除重復(fù)臺(tái)賬信息，減少重復(fù)數(shù)據(jù)處理所需時(shí)間，進(jìn)而提高海量臺(tái)賬重復(fù)數(shù)據(jù)維護(hù)的時(shí)間性能和消重性能。

5 結(jié)語(yǔ)

基于動(dòng)態(tài)布隆過(guò)濾器的海量信息臺(tái)賬數(shù)據(jù)消重算法的實(shí)現(xiàn)與應(yīng)用，是結(jié)合企業(yè)業(yè)務(wù)實(shí)際，為規(guī)范化運(yùn)維，提高信息設(shè)備資源納管及時(shí)率，提升自動(dòng)化運(yùn)維水平，解決目前設(shè)備臺(tái)賬可信賴度低等實(shí)際問(wèn)題，實(shí)現(xiàn)的技術(shù)創(chuàng)新。目前已在企業(yè)推廣應(yīng)用，實(shí)現(xiàn)大批量設(shè)備臺(tái)賬快速消重，減少運(yùn)維人員進(jìn)行設(shè)備維護(hù)的重復(fù)性工作，利于及時(shí)監(jiān)控信息設(shè)備運(yùn)行狀態(tài)，提高運(yùn)維工作效率，降低了信息設(shè)備維護(hù)成本，有效實(shí)現(xiàn)信息設(shè)備自動(dòng)監(jiān)控率提升。

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