以下內(nèi)容學(xué)習(xí)、摘錄自《數(shù)學(xué)之美》
在日常生活或工作中，包括開發(fā)軟件時(shí)，經(jīng)常要判斷一個(gè)元素是否在個(gè)集合中。比如，在字處理軟件中，需要檢查一個(gè)英語單詞是否拼寫正確（也就是要判斷它是否在已知的字典中）；在FBI，需要核實(shí)一個(gè)嫌疑人的名字是否已經(jīng)在嫌疑名單上；在網(wǎng)絡(luò)爬蟲里，需要確認(rèn)一個(gè)網(wǎng)址是否已訪問過，等等。
最直接的方法就是將集合中全部的元素存在計(jì)算機(jī)中，遇到一個(gè)新元素時(shí)，將它和集合中的元素直接比較即可。一般來講，計(jì)算機(jī)中的集合是用散列表（ Hash table，也叫哈希表）來存儲的，優(yōu)點(diǎn)是快速準(zhǔn)確，缺點(diǎn)是耗費(fèi)存儲空間。當(dāng)集合比較小時(shí)，這個(gè)問題不明顯，當(dāng)集合規(guī)模巨大時(shí)，散列表存儲效率低的問題就顯現(xiàn)出來了。
比如像 Yahoo、 Hotmail和 gmail那樣的公眾電子郵件（ Email）提供商，必須設(shè)法過濾來自發(fā)送垃圾郵件的人（ Spacer）的垃圾郵件。一種做法就是記錄下那些發(fā)垃圾郵件的 Email地址。由于那些發(fā)送者會不斷注冊新的地址，全世界少說也有幾十億個(gè)發(fā)垃圾郵件的地址。采用散列表，每存儲一億個(gè)Emai地址，就需要1.6GB的內(nèi)存（用散列表實(shí)現(xiàn)的具體辦法是將每一個(gè) Email地址對應(yīng)成一個(gè)8字節(jié)的信息指紋，然后將這些信息指紋存入散列表，由于散列表的存儲效率一般只有50%，因此一個(gè) Email地址需要占用16個(gè)字節(jié)。一億個(gè)地址大約要1.6GB的內(nèi)存）。因此，存儲幾十億個(gè)郵件地址可能需要上百GB的內(nèi)存。
今天，我們介紹一種稱作布隆過濾器的數(shù)學(xué)工具，它只需要散列表1/8到1/4的大小就能解決同樣的問題。
布隆過濾器（ Bloom Filter）是由伯頓·布?。?Burton bloom）于1970年提出的。它實(shí)際上是一個(gè)很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。接下來用上面的例子來說明其工作原理。
假定存儲一億個(gè)電子郵件地址，先建立一個(gè)16億個(gè)比特位即兩億字節(jié)的向量，然后將這16億個(gè)比特位全部清零。對于每一個(gè)電子郵件地址X，用8個(gè)不同的隨機(jī)數(shù)產(chǎn)生器（F1，F(xiàn)2，…，F(xiàn)8）產(chǎn)生8個(gè)信息指紋（f1，f2，…，f8）。再用一個(gè)隨機(jī)數(shù)產(chǎn)生器G把這8個(gè)信息指紋映射到1-16億中的8個(gè)自然數(shù)g1，g2，…，98?，F(xiàn)在把這8個(gè)位置的比特位全部設(shè)置為1。對這一億個(gè)電子郵件地址都進(jìn)行這樣的處理后，一個(gè)針對這些電子郵件地址的布隆過濾器就建成了，見下圖。
現(xiàn)在，讓我們看看如何用布隆過濾器來檢測一個(gè)可疑的電子郵件地址Y是否在黑名單中。用相同的8個(gè)隨機(jī)數(shù)產(chǎn)生器（F1，F(xiàn)2…，F(xiàn)8）對這個(gè)地址產(chǎn)生8個(gè)信息指紋S1，S2，…，S8，然后將這8個(gè)指紋對應(yīng)到布隆過濾器的8個(gè)比特位，分別是t1，t2…，t8。如果Y在黑名單中，顯然，t1，t2，…，t8對應(yīng)的8個(gè)比特值一定是1。這樣，再遇到任何在黑名單中的電子郵件地址，都能準(zhǔn)確地發(fā)現(xiàn)。
布隆過濾器決不會漏掉黑名單中的任何一個(gè)可疑地址。但是，它也有一個(gè)不足之處：它有極小的可能將一個(gè)不在黑名單中的電子郵件地址也判定為在黑名單中，因?yàn)橛锌赡苣硞€(gè)好的郵件地址在布隆過濾器中對應(yīng)的8個(gè)位置“恰巧”被（其他地址）設(shè)置成1。
布隆過濾器的錯(cuò)判在檢驗(yàn)上被稱為“假陽性”。這個(gè)概率很小，但是究竟有多小，是否可以忽略？估算假陽性的概率并不難，書中介紹了方法。假定一個(gè)元素用16比特，并有8個(gè)散列函數(shù)，那么假陽性的概率是萬分之五，在大多數(shù)應(yīng)用中是可以接受的。
布隆過濾器背后的數(shù)學(xué)原理在于兩個(gè)完全隨機(jī)的數(shù)字相沖突的概率很小，因此，可以在很小的誤識別率條件下，用很少的空間存儲大量信息。補(bǔ)救誤識別的常見辦法是再建立一個(gè)小的白名單，存儲那些可能被別誤判的信息。布隆過濾器中只有簡單的算術(shù)運(yùn)算，因此速度很快，使用方便。
