昨天凌晨，老板寄信說要期末聚餐！昨天也是個繁忙的一天，更是放寒假前的序曲。下午除了例行的助教工作外，還蹦出個小插曲，那就是報告者未到的情況！這個情況我還是第一次碰到，所幸最後都有完善的處理啦，過了這堂後，緊接著是資料結構的期末考，取而代之的，我不用監考而是寫報告處理上堂課的狀況啦。晚兒可直接在餐桌上進行了簡短的 Meeting 呢！順道提到了解決 crawler 問題的技術！
在搜尋廣大的網際網路資料時，很容易會碰到一個問題：到底這個網址抓過沒？於是，老師在餐桌上提起了一些實作，我坐在邊角，沒有聽得很清楚，返家後隨意地拼湊，再來 google 一下，發現這東西其實就是很早以前就存在的解法！
我印象中老師提及的用法跟這不太一樣，後來再亂逛一下，發現越來越多變種的應用，哈。無論怎樣，我就記下我依稀記得的情況啦。
- 首先，如果你想要的結果是 100 萬個不重複的元素，那實作上可以準備八個 400 萬個 bit 當作 Hash Space 以及八個不一樣的 Hash Function。那八個 400 萬個 bit 初始為 0 ，代表尚未使用。
- 接著，每當要將某個元素加入的已挑選的名單中，那就分別透過八個 Hash Function 進行運算，每個 hash function 運算出的結果是 0 ~ 3,999,999 的數值，這個數值代表的是該坐落於第幾個位置，並且依序在八個 hash space 上標記上1 。
- 如果在加入的過程中，發現有個 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(誤判) 的情況呢？其實，網路上資料那麼那麼多，且重要非隱私性的資料很容易到處都有一份，因此，偶爾損失個小小網頁也是無傷大雅的。當然，若真的很計較的話，就可以改用其他的方式或稍作修改來處理了！
沒有留言:
張貼留言