張 華,鄭世玨
(1.阜陽(yáng)職業(yè)技術(shù)學(xué)院,安徽阜陽(yáng) 236031;2.華中師范大學(xué),河北武漢 430079)
Bloom Filter在手機(jī)垃圾短信過(guò)濾中的應(yīng)用
張 華1,鄭世玨2
(1.阜陽(yáng)職業(yè)技術(shù)學(xué)院,安徽阜陽(yáng) 236031;2.華中師范大學(xué),河北武漢 430079)
針對(duì)當(dāng)前手機(jī)垃圾短信過(guò)濾系統(tǒng)的不足和手機(jī)資源緊張的特點(diǎn),構(gòu)建了基于獨(dú)立空間布隆過(guò)濾器的手機(jī)垃圾短信過(guò)濾系統(tǒng),具體給出了系統(tǒng)結(jié)構(gòu)、工作流程及其算法。實(shí)驗(yàn)分析結(jié)果表明,在允許一定“假陽(yáng)性”誤報(bào)率的條件下,該系統(tǒng)可以有效節(jié)省手機(jī)資源。
手機(jī);垃圾短信;Bloom Filter;獨(dú)立空間布隆過(guò)濾器
垃圾短信指沒(méi)有經(jīng)過(guò)接收者同意接收的、含有詐騙、色情、營(yíng)銷廣告等用戶不想看到的信息[1]。中國(guó)互聯(lián)網(wǎng)協(xié)會(huì)2010至2013年手機(jī)短信狀況調(diào)查報(bào)告顯示,每個(gè)用戶平均每周收到垃圾短信息11-13條[2],占比22%~28%,每人平均每年收到624條垃圾短信。垃圾短信占用手機(jī)的存儲(chǔ)空間,干擾正常短信的接收與閱讀,消耗接收者時(shí)間,因此設(shè)計(jì)和開(kāi)發(fā)垃圾短信過(guò)濾系統(tǒng)具有重要意義。
目前垃圾短信過(guò)濾主要有兩種方法。一種是在SMSC中心進(jìn)行過(guò)濾。由于不同用戶對(duì)垃圾短信的判定不同,因此不能做到個(gè)性化過(guò)濾。另一種是在手機(jī)端進(jìn)行過(guò)濾[3]。中國(guó)互聯(lián)網(wǎng)協(xié)會(huì)在2013年用戶認(rèn)為“有效的治理垃圾短信息的方法”調(diào)查顯示,為手機(jī)安裝反垃圾短信的過(guò)濾軟件占比19.5%,同比提升14%。因此手機(jī)端過(guò)濾越來(lái)越受用戶的喜愛(ài)。手機(jī)端過(guò)濾主要采用黑名單和基于內(nèi)容的過(guò)濾,基于關(guān)鍵詞的內(nèi)容過(guò)濾需要引入語(yǔ)料庫(kù)和中文分詞詞典,對(duì)資源有限的移動(dòng)手機(jī),將會(huì)嚴(yán)重影響系統(tǒng)性能。針對(duì)以上問(wèn)題,文章提出基于獨(dú)立空間布隆過(guò)濾器的手機(jī)垃圾短信過(guò)濾,在實(shí)現(xiàn)個(gè)性化過(guò)濾的同時(shí),可以有效降低手機(jī)端內(nèi)存資源消耗,提高系統(tǒng)運(yùn)行速度。
Bloom Filter是采用位串向量表示數(shù)據(jù)集合,能夠?qū)崿F(xiàn)高效壓縮存儲(chǔ)與集合查詢的數(shù)據(jù)結(jié)構(gòu)[4],一個(gè)布隆過(guò)濾器由以下幾部分組成[5]:
(1)Bloom Filter用一個(gè)長(zhǎng)度為m的位向量V表示集合中的元素,每個(gè)位的初始值都設(shè)為0。
(2)k個(gè)相互獨(dú)立均勻分布的哈希函數(shù)組成的集合H。
(3)n個(gè)元素組成的集合S。
布隆過(guò)濾器的工作原理分為兩步:
第一步,數(shù)據(jù)裝入。k個(gè)相互獨(dú)立的哈希函數(shù)分別將集合S中的n個(gè)元素映射到向量V中相應(yīng)位置,將V中相應(yīng)位置為1,如圖1所示。
圖1 Bloom Filter工作原理圖
第二步,數(shù)據(jù)判斷。當(dāng)新元素x到來(lái)時(shí),對(duì)x進(jìn)行k次哈希運(yùn)算,檢查所有的h1(x),h2(x),…,hk(x)對(duì)應(yīng)向量V中的位是否全部為1,如果是,則元素x屬于集合S,否則,認(rèn)為x不屬于集合S。
布隆過(guò)濾器判斷某個(gè)數(shù)據(jù)對(duì)象x是否屬于集合S時(shí),即使是采用均勻且不同的哈希函數(shù),地址沖突也是不可能完全避免的,因此布隆過(guò)濾器算法可能對(duì)位向量中的同一個(gè)位多次置1,所以在進(jìn)行數(shù)據(jù)判斷時(shí)可能出現(xiàn)錯(cuò)判,把不屬于這個(gè)集合的元素誤判為屬于這個(gè)集合(False Positive)[6],但是,不會(huì)把屬于這個(gè)集合的元素誤判為不屬于這個(gè)集合。下面通過(guò)計(jì)算來(lái)估計(jì)發(fā)生“假陽(yáng)性”錯(cuò)誤率P的大小。
當(dāng)集合S中所有元素都被映射到過(guò)濾器后,任一位仍為0的概率是(1-1/m)kn,因此任一位為1的概率是1-(1-1/m)kn。當(dāng)不屬于集合S的元素x被誤判為屬于集合S時(shí),則必須滿足x在V向量的k個(gè)映射位的值都為1,則錯(cuò)誤率
由此式可得,當(dāng)哈希函數(shù)取最優(yōu)個(gè)數(shù)時(shí),錯(cuò)誤率P和集合中元素個(gè)數(shù)n和向量大小m相關(guān)。
2.1 移動(dòng)短信業(yè)務(wù)網(wǎng)的基本結(jié)構(gòu)
隨著短信的廣泛應(yīng)用,短信業(yè)務(wù)被應(yīng)用到很多領(lǐng)域,移動(dòng)短信業(yè)務(wù)的短信發(fā)送方式主要有兩種:一種是從手機(jī)到手機(jī),另一種是從網(wǎng)絡(luò)平臺(tái)到手機(jī)。由于短信資費(fèi)的下降和手機(jī)入網(wǎng)的非實(shí)名制,垃圾短信也由此產(chǎn)生。垃圾短信來(lái)源途徑主要有3種:一種是從網(wǎng)絡(luò)平臺(tái)到手機(jī),如CP或SP為了推銷自己的業(yè)務(wù),向用戶發(fā)送大量的宣傳廣告。第二種是從手機(jī)到手機(jī),通過(guò)手機(jī)向手機(jī)發(fā)送詐騙、騷擾短信等;第三種是手機(jī)結(jié)合短信貓實(shí)現(xiàn)快速批量的短信發(fā)送。
2.2 手機(jī)垃圾短信過(guò)濾系統(tǒng)結(jié)構(gòu)
手機(jī)性能主要決定于CPU和運(yùn)行內(nèi)存,CPU的核心越多、主頻越高、架構(gòu)越新,手機(jī)處理器性能就越強(qiáng)。目前手機(jī)運(yùn)行內(nèi)存主流為1 G,除去系統(tǒng)開(kāi)銷,可用空間只有800 M左右,隨著APP應(yīng)用越來(lái)越多,每開(kāi)一個(gè)程序就要消耗手機(jī)運(yùn)行空間。用戶對(duì)垃圾信息攔截產(chǎn)品性能指標(biāo)關(guān)注情況調(diào)查顯示,軟件占用手機(jī)空間大小達(dá)到56%,而且同比增長(zhǎng)17.9%。如何最大限度降低軟件內(nèi)存消耗是手機(jī)應(yīng)用軟件的關(guān)鍵。
針對(duì)手機(jī)特點(diǎn)和垃圾短信來(lái)源途徑,設(shè)計(jì)SMSC中心和手機(jī)端相結(jié)合的垃圾短信過(guò)濾系統(tǒng)[7],系統(tǒng)結(jié)構(gòu)如圖2所示。系統(tǒng)包括兩個(gè)部分,第一部分是SMSC子系統(tǒng),實(shí)現(xiàn)基于內(nèi)容的短信過(guò)濾,主要針對(duì)國(guó)家公共層面內(nèi)容的過(guò)濾,如色情、暴力、詐騙、謠言等信息,作為下一步的研究?jī)?nèi)容;第二部分是手機(jī)端子系統(tǒng),主要實(shí)現(xiàn)個(gè)性化過(guò)濾。這部分主要實(shí)現(xiàn)黑名單數(shù)據(jù)庫(kù)導(dǎo)入、添加黑名單、數(shù)據(jù)查找以及數(shù)據(jù)清空功能。
圖2 手機(jī)垃圾短信過(guò)濾系統(tǒng)結(jié)構(gòu)圖
2.3 獨(dú)立空間布隆過(guò)濾器
Bloom fitler通過(guò)k個(gè)哈希函數(shù)將n個(gè)元素映射到m個(gè)向量空間V中,其中每個(gè)哈希函數(shù)的映射空間都是{0,1,…,m-2,m-1},因此也稱為共享空間布隆過(guò)濾器。不同關(guān)鍵字被同一哈希函數(shù)映射到哈希空間的同一位置,即對(duì)任何ki≠kj存在h(ki)=h(kj),把它稱為內(nèi)部沖突。對(duì)不同關(guān)鍵字被不同哈希函數(shù)映射到同一哈希空間,即對(duì)任何ki≠kj存在hm(ki)=hn(kj),稱為外部沖突。對(duì)應(yīng)內(nèi)部沖突,可以通過(guò)選擇哈希函數(shù)來(lái)解決;對(duì)于外部沖突,采用將每個(gè)哈希函數(shù)的映射空間區(qū)分開(kāi),即獨(dú)立哈??臻g布隆過(guò)濾器。我們采用長(zhǎng)為m的位串向量V表示垃圾短信地址集合S={x1,x2,…,xn}。首先將向量空間V平均分成連續(xù)的k段,每段m/k位,取k個(gè)獨(dú)立且均勻分布的哈希函數(shù)集合h,對(duì)每一段只進(jìn)行一次哈希操作,當(dāng)1≤i≤n,1≤j≤k時(shí)有
則每個(gè)哈希函數(shù)的映射空間如圖3所示。
圖3 獨(dú)立空間布隆過(guò)濾器圖
系統(tǒng)工作流程如下
1)首先,SMSC端子系統(tǒng)獲取短信地址,將它和黑名單中的號(hào)碼進(jìn)行比較,如果有,則刪除該短信。
2)否則,獲取短信內(nèi)容,調(diào)用分類程序?qū)Χ绦艃?nèi)容進(jìn)行識(shí)別,判斷它是不是色情、暴力、謠言等垃圾短信,如果是直接刪除,并將該短信地址加入垃圾短信黑名單數(shù)據(jù)庫(kù)。
3)否則,發(fā)送到手機(jī)端子系統(tǒng)。
4)手機(jī)端子系統(tǒng)獲取短信地址,將短信地址經(jīng)過(guò)哈希映射和向量V中對(duì)應(yīng)位的值比較,如果有一次對(duì)應(yīng)位的值為0,則顯示該短信,轉(zhuǎn)5)。如果k次映射位的值都為1,則刪除該短信。
5)用戶閱讀短信。如果發(fā)現(xiàn)是垃圾短信,則將該短信地址加入黑名單中。
2.4關(guān)鍵模塊算法[8]針對(duì)以上流程,手機(jī)端子系統(tǒng)工作步驟如下:1)初始數(shù)據(jù)裝入。將移動(dòng)公司的垃圾短信黑名單裝入過(guò)濾器。算法如下:
2)增添數(shù)據(jù)。用戶將各自認(rèn)定的垃圾短信地址加入過(guò)濾器。算法如下
3)數(shù)據(jù)過(guò)濾。當(dāng)短信到達(dá)時(shí),將它的地址進(jìn)行哈希運(yùn)算,計(jì)算相應(yīng)位的值,如果有一個(gè)對(duì)應(yīng)位值為0,就中止后續(xù)哈希運(yùn)算,返回0;如果全部哈希映射位值均為1,則返回1,刪除該短信。算法為
手機(jī)垃圾短信過(guò)濾系統(tǒng)的評(píng)價(jià)指標(biāo)主要包括實(shí)時(shí)性、誤報(bào)率、維護(hù)開(kāi)銷、識(shí)別率、實(shí)現(xiàn)復(fù)雜度、用戶隱私保護(hù)[9]。
實(shí)時(shí)性:系統(tǒng)采用bloom filter數(shù)據(jù)結(jié)構(gòu),布隆過(guò)濾器是基于哈希表的算法,對(duì)每個(gè)短信地址的過(guò)濾需要進(jìn)行至多k次哈希運(yùn)算,它的時(shí)間復(fù)雜度為O(k),相比其他數(shù)據(jù)結(jié)構(gòu)具有很大優(yōu)勢(shì)。
誤報(bào)率和維護(hù)開(kāi)銷:在獨(dú)立空間布隆過(guò)濾器中,對(duì)于一個(gè)短信地址在每段m/k位中,被映射為1的概率是k/m,被映射為0的概率是1-k/m,則n個(gè)地址都被映射為0的概率為(1-k/m)n。也就是,當(dāng)集合中所有地址都映射完畢,向量V中m/k段中任意一位值為0的概率為(1-k/m)n,它的對(duì)立事件,當(dāng)集合中所有地址都映射完畢,向量中m/k段任意一位值為1的概率為1-(1-k/m)n。當(dāng)不屬于集合S的地址x誤判為屬于該集合時(shí),則必須滿足x在向量k段映射位的值都必須為1。設(shè)誤報(bào)率為P2,則
由公式(1)知當(dāng)bloom filter取到最優(yōu)哈希函數(shù)「(m/n)ln2?時(shí),誤報(bào)率最小。由公式(3)可推出
由統(tǒng)計(jì)知,手機(jī)平均使用年限為3~5年,5年平均收到垃圾短信約為3 120條,每條短信地址占用8字節(jié),共需24.96 kB。設(shè)定P<=0.01,由公式(5)可得m為29 905 Byte即3.74 kB,至少節(jié)省85%內(nèi)存空間,若設(shè)定P為0.02則可以節(jié)省87%內(nèi)存,實(shí)驗(yàn)如圖4所示??梢?jiàn)在能夠取最優(yōu)哈希函數(shù)前提下,誤報(bào)率和空間成反比,即誤報(bào)率越低,則所需空間越大。所以布隆過(guò)濾器系統(tǒng)犧牲正確率換取空間,但是系統(tǒng)可能會(huì)將不是垃圾短信誤報(bào)為垃圾短信,而不會(huì)將正常短信誤報(bào)為垃圾短信刪除而造成損失,對(duì)于資源有限的手機(jī)系統(tǒng)具有很大意義。
又由于(1-k/m)n≤(1-1/m)kn[10],因此P2略微大于標(biāo)準(zhǔn)布隆過(guò)濾器的誤報(bào)率(設(shè)為P1)。下面通過(guò)實(shí)驗(yàn)比較分析P1和P2關(guān)系,由仿真實(shí)驗(yàn)如圖5所示,當(dāng)m較小時(shí),如m=120時(shí),隨著n的增加,P2漸漸大于P1;當(dāng)m=29 905時(shí),P2≈P1,所以當(dāng)m?n時(shí),P2和P1相等。由此,獨(dú)立空間布隆過(guò)濾器在元素個(gè)數(shù)和存儲(chǔ)空間相差較大時(shí),在誤報(bào)率不增大的條件下,使k個(gè)哈希函數(shù)可以并行訪問(wèn)位數(shù)組,從而提高程序性能。
圖4 Bloom Filter誤報(bào)率與向量空間關(guān)系圖
圖5 性能分析對(duì)比圖
綜上所述,本文對(duì)Bloom Filter及獨(dú)立空間布隆過(guò)濾器進(jìn)行了分析研究,構(gòu)建了基于獨(dú)立空間布隆過(guò)濾器的手機(jī)垃圾短信過(guò)濾系統(tǒng),仿真分析結(jié)果表明,在允許一定誤報(bào)率的條件下,可以有效節(jié)省手機(jī)資源,提高系統(tǒng)性能。下一步研究重點(diǎn)是SMSC端子系統(tǒng)基于短信內(nèi)容的識(shí)別與過(guò)濾。
[1]張燕,傅建明.垃圾短信的識(shí)別與追蹤[J].計(jì)算機(jī)應(yīng)用研究,2006(03):245-247.
[2]中國(guó)互聯(lián)網(wǎng)協(xié)會(huì).2013年上半年手機(jī)短信狀況調(diào)查報(bào)告[EB/OL].http://www.12321.cn,[2013-11-05].
[3]徐英慧,劉梅彥.基于內(nèi)容的手機(jī)端垃圾短信過(guò)濾策略研究[J].北京信息科技大學(xué)學(xué)報(bào),2012,28(01):51-54.
Application of Bloom Filter in Mobile Phone Spam Message Filtering
ZHANG Hua1,ZHENG Shi-jue2
(1.Fuyang Vocationaland Technical College,F(xiàn)uyang 236031,China;2.Deptof Computer Science,Huazhong Normal University,Wuhan 430079,China)
This paper analyzes theoperating principleof Bloom Filter and presents independencesspacebloom filter.Then,itbuilds the system ofmobile phone spam message based on independences space bloom filter and gives operating principle、algorithm.Last,experiments show that the system has a good performancewith acceptable sufficiently small false positives.
mobile phone,spam message,bloom filter,independence space bloom filter
TP301
A
1007-4260(2014)03-0066-04
時(shí)間:2014-9-15 16:07 網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/doi/10.13757/j.cnki.cn34-1150/n.2014.03.016.html
2014-03-14
國(guó)家自然科學(xué)基金項(xiàng)目(61370108)資助。
張華,女,安徽六安人,碩士,阜陽(yáng)職業(yè)技術(shù)學(xué)院副教授,主要研究方向?yàn)橹悄苡?jì)算、數(shù)據(jù)挖掘等;鄭世玨,男,湖北武漢人,博士,華中師范大學(xué)教授,主要研究方向?yàn)楦咝阅苡?jì)算、數(shù)據(jù)挖掘等。