算法解析1. 基于黑名單的過濾器1，維護(hù)一個(gè)騷擾電話號碼和垃圾短信發(fā)送號碼的黑名單孕锄。①：如果黑名單中的電話號碼不多吮廉，可以使用散列表、二叉樹等動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)來存儲畸肆，對內(nèi)存的消耗并不會很大 每個(gè)號碼看作一個(gè)字符串宦芦，并且假設(shè)平均長度是 16 個(gè)字節(jié)，那存儲 50 萬個(gè)電話號碼恼除，大約需要 10MB 的內(nèi)存空間踪旷，但當(dāng)號碼超過500萬個(gè)時(shí)，使用散列表就需要100MB空間豁辉，這個(gè)對用戶的手機(jī)而言是不可接受的。②：布隆過濾器最大的特點(diǎn)就是比較省存儲空間舀患，所以徽级，用它來解決這個(gè)問題很合適 存儲 500 萬個(gè)手機(jī)號碼，把位圖大小設(shè)置為 10 倍數(shù)據(jù)大小聊浅，也只需要5000 萬 bits餐抢，換算成字節(jié)不到 7MB 的存儲空間③：還有一種時(shí)間換空間的方法，可以將內(nèi)存的消耗優(yōu)化到極致 把黑名單存儲在服務(wù)器端上低匙，服務(wù)器端來做過濾和攔截的核心工作旷痕。手機(jī)端只將要檢查的號碼發(fā)送給服務(wù)器端，服務(wù)器端將判斷結(jié)果返回給手機(jī)端顽冶，但網(wǎng)絡(luò)通信通常比較慢2. 基于規(guī)則的過濾器
1欺抗，基于規(guī)則的過濾方式
①：預(yù)先設(shè)定一些規(guī)則，如果某條短信符合這些規(guī)則强重，我們就可以判定它是垃圾短信
②：但如果短信只是滿足其中一條規(guī)則绞呈，如果就判定為垃圾短信，會存在比較大的誤判的情況间景。所以可以綜合多條規(guī)則進(jìn)行判斷
③：或每條規(guī)則對應(yīng)一個(gè)不同的得分佃声，滿足哪條規(guī)則，就累加對應(yīng)的分?jǐn)?shù)倘要，某短信的總得分超過閾值圾亏，才會被判定為垃圾短信
2，難點(diǎn)問題
過濾規(guī)則要實(shí)到執(zhí)行層面，其實(shí)還有很大的距離志鹃，還有很多細(xì)節(jié)需要處理父晶，如第一條規(guī)則中，我們該如何定義特殊單詞弄跌；第二條規(guī)則中甲喝，我們該如何定義什么樣的號碼是群發(fā)號碼等等
3，具體細(xì)節(jié)
我們該如何定義特殊單詞
雖然可以基于概率統(tǒng)計(jì)的方法铛只，借助計(jì)算機(jī)強(qiáng)大的計(jì)算能力埠胖，找出哪些單詞最常出現(xiàn)在垃圾短信中，將這些最常出現(xiàn)的單詞淳玩，作為特殊單詞直撤，用來過濾短信。
不過這種方法的前提是蜕着，要有大量的樣本數(shù)據(jù)谋竖，并且每條短信都做好了標(biāo)記，它是垃圾短信還是非垃圾短信承匣。
如對 1000 萬條短信蓖乘，
①，進(jìn)行分詞處理（借助中文或者英文分詞算法）韧骗，去掉“的嘉抒、和、是”等沒有意義的停用詞（Stop words）袍暴，得到 n 個(gè)不同的單詞
②些侍，針對每個(gè)單詞，統(tǒng)計(jì)有多少個(gè)垃圾短信出現(xiàn)了這個(gè)單詞政模，有多少個(gè)非垃圾短信會出現(xiàn)這個(gè)單詞岗宣，進(jìn)而求出每個(gè)單詞分別出現(xiàn)在垃圾短信，非垃圾短信中的概率淋样。
③耗式，如果某個(gè)單詞出現(xiàn)在垃圾短信中的概率，遠(yuǎn)大于出現(xiàn)在非垃圾短信中的概率习蓬，則可這個(gè)單詞作為特殊單詞纽什，用來過濾垃圾短信
4，缺點(diǎn)問題
一方面躲叼，這些規(guī)則受人的思維方式局限芦缰，規(guī)則未免太過簡單；
另一方面枫慷，垃圾短信發(fā)送者可能會針對規(guī)則让蕾，精心設(shè)計(jì)短信浪规，繞過這些規(guī)則的攔截
- 基于概率統(tǒng)計(jì)的過濾器
1，理論基礎(chǔ)
①：這種基于概率統(tǒng)計(jì)的過濾方式探孝，基礎(chǔ)理論是基于樸素貝葉斯算法
2笋婿，實(shí)踐方法
①：基于概率統(tǒng)計(jì)的過濾器，是基于短信內(nèi)容來判定是否是垃圾短信
②：需要把短信抽象成一組計(jì)算機(jī)可以理解并且方便計(jì)算的特征項(xiàng)顿颅，用這一組特征項(xiàng)代替短信本身缸濒，來做垃圾短信過濾
③：可以通過分詞算法，把一個(gè)短信分割成 n 個(gè)單詞粱腻。這 n 個(gè)單詞就是一組特征項(xiàng)庇配，全權(quán)代表這個(gè)短信。
④：因此绍些，判定一個(gè)短信是否是垃圾短信的問題捞慌，就變成了，判定同時(shí)包含這幾個(gè)單詞的短信是否是垃圾短信
3柬批，
使用概率啸澡，來表征一個(gè)短信是垃圾短信的可信程度。如果用公式將這個(gè)概率表示出來氮帐，就是下面這個(gè)樣子：
盡管我們有大量的短信樣本嗅虏，但是我們沒法通過樣本數(shù)據(jù)統(tǒng)計(jì)得到這個(gè)概率。沒有樣本揪漩，也就無法計(jì)算概率旋恼。所以這樣的推理方式雖然正確，但是實(shí)踐中并不好用奄容。所以我們需要通過樸素貝葉斯公式，將這個(gè)概率的求解产徊，分解為其他三個(gè)概率的求解昂勒。
基于下面這條著名的概率規(guī)則來計(jì)算。
獨(dú)立事件發(fā)生的概率計(jì)算公式：P(AB) = P(A)P(B)
如果事件 A 和事件 B 是獨(dú)立事件舟铜，兩者的發(fā)生沒有相關(guān)性戈盈，事件 A 發(fā)生的概率 P(A) 等于 p1，事件 B 發(fā)生的概率 P(B) 等于 p2谆刨，那兩個(gè)同時(shí)發(fā)生的概率 P(AB) 就等于 P(A)P(B)塘娶。
基于這條獨(dú)立事件發(fā)生概率的計(jì)算公式，我們可以把 P（W1痊夭，W2刁岸，W3，…她我，Wn 同時(shí)出現(xiàn)在一條短信中 | 短信是垃圾短信）分解為下面這個(gè)公式：
在求解 p1 和 p2 倍數(shù)（p1/p2）的時(shí)候虹曙，我們也就不需要這個(gè)值迫横。
