在爬蟲中霉旗，我們經(jīng)常遇到這樣的問題澄步。一是希望抓取過的URL不再重復(fù)抓取械媒，節(jié)省資源目锭；二是希望下載過的數(shù)據(jù)不再重復(fù)下載（一般情況下保證了第一條可以差不多滿足第二條）。
爬蟲去重一般是對(duì)URL去重纷捞，訪問過的頁面不在訪問去重可以避免網(wǎng)絡(luò)之間的環(huán)路痢虹，并且增加爬取效率。
今天我們介紹幾個(gè)去重策略
一主儡、像十萬以下URL的抓取可以簡(jiǎn)單的用set來實(shí)現(xiàn)去重世分，可以在O(1)的時(shí)間內(nèi)查詢到一個(gè)URL是否存在于set中。
缺點(diǎn)：占用內(nèi)存大缀辩，比如有1億條URL臭埋，占用的內(nèi)存是：1000000000*2byte*50字符/1024/1024/1024 = 9G(假設(shè)字符使用的是unicode編碼冯乘，每一個(gè)字符占2字節(jié)务漩，每一個(gè)URL有50個(gè)字符)。
二垒拢、如果是百萬或者千萬量級(jí)的話健无，考慮到性能荣恐，我們應(yīng)該使用基于hash的set實(shí)現(xiàn)去重。哈希使得我們并不需要對(duì)比超長(zhǎng)的URL以及params，只需要對(duì)比其哈希值叠穆。
缺點(diǎn)：如果檢測(cè)結(jié)果為是少漆，該元素不一定在集合中；但如果檢測(cè)結(jié)果為否硼被，該元素一定不在集合中示损。這樣每個(gè)檢測(cè)請(qǐng)求返回有“在集合內(nèi)（可能錯(cuò)誤）”和“不在集合內(nèi)（絕對(duì)不在集合內(nèi)）”兩種情況，可見 Bloom filter 是犧牲了正確率和時(shí)間以節(jié)省空間嚷硫。
三检访、URL經(jīng)過MD5或SHA-1等哈希算法生成摘要，再存到HashSet中仔掸。MD5處理后摘要長(zhǎng)度128位脆贵，SHA-1摘要長(zhǎng)度160位，這樣占用內(nèi)存比直接存小很多起暮。（scrapy使用的就是類似的方法）
四卖氨、使用bitmap方法，將訪問過的URL通過hash函數(shù)映射到某一位上负懦，這種方法可以大大壓縮URL的存儲(chǔ)空間筒捺，但是缺點(diǎn)是，會(huì)有很多的映射沖突密似，即多個(gè)不同的URL映射到一個(gè)位上。
五葫盼、如果數(shù)據(jù)量上億或者幾十億時(shí)使用?Bloom Filter（中文：布隆過濾器）算法残腌。布隆過濾器原理是這樣的，一個(gè)URL過來贫导，通過M個(gè)特別的哈希函數(shù)對(duì)其進(jìn)行運(yùn)算抛猫，映射成一個(gè)M維位數(shù)組的M個(gè)維度。新的URL誕生時(shí)孩灯，進(jìn)行同樣操作并逐個(gè)與set中的位數(shù)組做“與”運(yùn)算闺金，若結(jié)果改變則說明URL一定沒有被抓取過，若結(jié)果一致則說明URL有一定概率被抓取過因?yàn)橛幸欢ǖ牡湾e(cuò)誤率峰档。布隆過濾器的插入和查詢效率都是O(M)败匹，遠(yuǎn)低于其他一般策略。使用Bloom Filter方法對(duì)bitmap進(jìn)行改進(jìn)讥巡，多重哈希函數(shù)降低沖突掀亩，是對(duì)（四：bitmap方法）的改進(jìn)，既能降低沖突欢顷，又能大大壓縮內(nèi)存
六槽棍、像MySQL這種關(guān)系型數(shù)據(jù)庫(kù)，我們可以設(shè)置主鍵或者唯一索引來保證數(shù)據(jù)的唯一性。查詢導(dǎo)致效率低炼七，不推薦缆巧。
七、像MongoDB這種Schema free的非關(guān)系型數(shù)據(jù)庫(kù)豌拙，我們可以用先檢索再插入或者是upsert的方式保證數(shù)據(jù)的唯一性陕悬。（相對(duì)于MySQL數(shù)據(jù)庫(kù)的性能有了很大的提升）
八、緩存數(shù)據(jù)庫(kù)去重： 如Redis數(shù)據(jù)庫(kù)其高速的讀寫姆蘸，使用其中的Set數(shù)據(jù)類型墩莫，并可將內(nèi)存中的數(shù)據(jù)持久化，應(yīng)用廣泛逞敷，推薦狂秦。
比較好的方式為：URL經(jīng)過MD5或SHA-1等哈希算法生成摘要，再存到?Redis的HashSet中
歡迎留言糾錯(cuò)補(bǔ)充推捐，QQ：2223136131
