Google+ Followers

2009年1月16日 星期五

Bloom filter - 使用 Hash 來判斷元素是否存在於一個集合中

昨天凌晨,老板寄信說要期末聚餐!昨天也是個繁忙的一天,更是放寒假前的序曲。下午除了例行的助教工作外,還蹦出個小插曲,那就是報告者未到的情況!這個情況我還是第一次碰到,所幸最後都有完善的處理啦,過了這堂後,緊接著是資料結構的期末考,取而代之的,我不用監考而是寫報告處理上堂課的狀況啦。晚兒可直接在餐桌上進行了簡短的 Meeting 呢!順道提到了解決 crawler 問題的技術!


在搜尋廣大的網際網路資料時,很容易會碰到一個問題:到底這個網址抓過沒?於是,老師在餐桌上提起了一些實作,我坐在邊角,沒有聽得很清楚,返家後隨意地拼湊,再來 google 一下,發現這東西其實就是很早以前就存在的解法!



我印象中老師提及的用法跟這不太一樣,後來再亂逛一下,發現越來越多變種的應用,哈。無論怎樣,我就記下我依稀記得的情況啦。



  1. 首先,如果你想要的結果是 100 萬個不重複的元素,那實作上可以準備八個 400 萬個 bit 當作 Hash Space 以及八個不一樣的 Hash Function。那八個 400 萬個 bit 初始為 0 ,代表尚未使用。

  2. 接著,每當要將某個元素加入的已挑選的名單中,那就分別透過八個 Hash Function 進行運算,每個 hash function 運算出的結果是 0 ~ 3,999,999 的數值,這個數值代表的是該坐落於第幾個位置,並且依序在八個 hash space 上標記上1 。

  3. 如果在加入的過程中,發現有個 hash function 中所算出的位置,其所在的值非 1 ,那就代表目前這個元素是新成員!而當八個 hash function 算出的位置上,各個皆為 1 ,那就把這個待加入的元素當成已被挑選過了!


整體上,老師提的就這樣而已。細微的分析,那就是一百萬個元素,每個元素只用到 1 bit x 8 = 1 byte 空間來紀錄是否用過;而關於 hash collision 的部分,每個 Hash Space 為四百萬的空間,所以對每個 Hash Function 發生 collision 的機率就是 1/4 啦,然而,連八個 hash functions 都發生 collision 的機率,那就是 (1/4)^8 = 0.0000152587890625!也就是說,機率已被降得很低囉!大約處理一百萬個元素,約 15 個元素可能會被誤判。關於其機率的部分,請參考 Wiki 上的 Probability of false positives ,近似於 ( 1/2 )^(hash function 個數)


對於發生 collision(誤判) 的情況呢?其實,網路上資料那麼那麼多,且重要非隱私性的資料很容易到處都有一份,因此,偶爾損失個小小網頁也是無傷大雅的。當然,若真的很計較的話,就可以改用其他的方式或稍作修改來處理了!


沒有留言:

張貼留言