【Python | 邊學邊敲邊記】第三次:URL去重策略

2021-02-24 簡說Python

一、前言

今天給大家分享的是,Python爬蟲裡url去重策略及實現。

二、url去重及策略簡介1.url去重

    從字面上理解,url去重即去除重複的url,在爬蟲中就是去除已經爬取過的url,避免重複爬取,既影響爬蟲效率,又產生冗餘數據。

2.url去重策略

    從表面上看,url去重策略就是消除url重複的方法,常見的url去重策略有五種,如下:

1
2
3
4
5
6

三、看代碼,邊學邊敲邊記url去重策略1.將訪問過的ur保存到資料庫中(初學使用)

實現起來最簡單,但效率最低。
其核心思想是,把頁面上爬取到的每個url存儲到資料庫,為了避免重複,每次存儲前都要遍歷查詢資料庫中是否已經存在當前url(即是否已經爬取過了),若存在,則不保存,否則,保存當前url,繼續保存下一條,直至結束。

2.將訪問過的ur保存到set內存中

將訪問過的ur保存到set中,只需要o(1)的代價就可以查詢url,取url方便快速,基本不用查詢,但是隨著存儲的url越來越多,佔用內存會越來越大。

1
2
3
4
5如果是2億個url,那麼佔用內存將達18G,也不是特別方便,適合小型爬蟲。

3.url經過md5縮減到固定長度

1'''
2簡單計算:一個url經MD5轉換,變成一個128bit(位)的字符串,佔16byte(字節),方法二中一個url保守
3估計佔50個字符 x 2 = 100byte(字節),
4計算式: 這樣一比較,MD5的空間節省率為:(100-16)/100 = 84%(相比於方法二)
5(Scrapy框架url去重就是採用的類似方法)
6'''
7
8'''
9MD5概述
10設計者 : 羅納德·李維斯特
11首次發布 : 1992年4月
12系列 : MD, MD2, MD3, MD4, MD5
13編碼長度 : 128位
14結構 : Merkle–Damgård construction
15    MD5消息摘要算法(英語:MD5 Message-Digest Algorithm),一種被廣泛使用的密碼散列函數,可
16以產生出一個128位(16位元組)的散列值(hash value),用於確保信息傳輸完整一致。MD5由美國密碼學家
17羅納德·李維斯特(Ronald Linn Rivest)設計,於1992年公開,用以取代MD4算法。這套算法的程序在 
18RFC 1321 中被加以規範。
19將數據(如一段文字)運算變為另一固定長度值,是散列算法的基礎原理。
20'''

MD5使用實例:

1
2import hashlib
3
4
5str01 = 'This is your md5 password!'
6
7md5_obj = hashlib.md5()
8
9
10md5_obj.update(str01.encode(encoding='utf-8'))
11
12print('XksA的原話為 :' + str01)
13print('MD5加密後為 :' + md5_obj.hexdigest())
14
15
16
17

4.用 bitmap方法,將訪問過的ur通過hash函數映射到某一位

1'''
2實現原理:通過hash函數,將每個url映射到一個hash位置中,一個hash位可以只佔用一個bit(位)大小,那
3麼相對於方法三:一個url佔128bit(位),hash函數法的空間節省成百倍增長。
4計算式:這樣一比較,bitmap方法的空間節省率為:
5(128-1)/128= 99.2%(相比於方法三)
6(100 * 8 - 1)/(100*8)= 99.88%(相比於方法一)
7                       ##   (缺點:容易產生衝突)  ##
8'''
9
10'''
11hash函數:
12散列函數(英語:Hash function)又稱散列算法、哈希函數,是一種從任何一種數據中創建小的數字「指紋」
13的方法。散列函數把消息或數據壓縮成摘要,使得數據量變小,將數據的格式固定下來。該函數將數據打亂混
14合,重新創建一個叫做散列值(hash values,hash codes,hash sums,或hashes)的指紋。散列值通常
15用一個短的隨機字母和數字組成的字符串來代表。好的散列函數在輸入域中很少出現散列衝突。在散列表和數
16據處理中,不抑制衝突來區別數據,會使得資料庫記錄更難找到。
17'''

5.bloomfilter方法對 bitmap進行改進,多重hash函數降低衝突

1
2'''
3# 基本概述
4   如果想判斷一個元素是不是在一個集合裡,一般想到的是將集合中所有元素保存起來,然後通過比較確定。
5鍊表、樹、散列表(又叫哈希表,Hash table)等等數據結構都是這種思路。但是隨著集合中元素的增加,
6我們需要的存儲空間越來越大。同時檢索速度也越來越慢,上述三種結構的檢索時間複雜度分別為:
7                            O(n),O(log n),O(n/k)
8# 原理概述
9   布隆過濾器的原理是,當一個元素被加入集合時,通過K個散列函數將這個元素映射成一個位數組中的K個
10點,把它們置為1。檢索時,我們只要看看這些點是不是都是1就(大約)知道集合中有沒有它了:如果這些點
11有任何一個0,則被檢元素一定不在;如果都是1,則被檢元素很可能在。這就是布隆過濾器的基本思想。
12# 優缺點
13    布隆過濾器可以用於檢索一個元素是否在一個集合中。
14    優點是空間效率和查詢時間都遠遠超過一般的算法。
15    缺點是有一定的誤識別率和刪除困難。
16'''
17

Bloomfilter底層實現:

1
2import math
3import logging
4import functools
5
6import pyhash
7
8from bitset import MmapBitSet
9from hash_tools import hashes
10
11
12class BloomFilter(object):
13    """
14    A bloom filter implementation,
15    which use Murmur hash and Spooky hash
16    """
17    def __init__(self, capacity, error_rate=0.0001, fname=None,
18                 h1=pyhash.murmur3_x64_128(), h2=pyhash.spooky_128()):
19        """
20        :param capacity: size of possible input elements
21        :param error_rate: posi
22        :param fname:
23        :param h1:
24        :param h2:
25        """
26        
27        self.capacity = capacity
28        self.error_rate = error_rate
29        self.num_of_bits, self.num_of_hashes = self._adjust_param(4096 * 8,
30                                                                  error_rate)
31        self._fname = fname
32        self._data_store = MmapBitSet(self.num_of_bits)
33        self._size = len(self._data_store)
34        self._hashes = functools.partial(hashes, h1=h1, h2=h2, number=self.num_of_hashes)
35
36    def _adjust_param(self, bits_size, expected_error_rate):
37        """
38        adjust k & m through 4 steps:
39        1. Choose a ballpark value for n
40        2. Choose a value for m
41        3. Calculate the optimal value of k
42        4. Calculate the error rate for our chosen values of n, m, and k.
43           If it's unacceptable, return to step 2 and change m;
44           otherwise we're done.
45        in every loop, m = m * 2
46        :param bits_size:
47        :param expected_error_rate:
48        :return:
49        """
50        n, estimated_m, estimated_k, error_rate = self.capacity, int(bits_size / 2), None, 1
51        weight, e = math.log(2), math.exp(1)
52        while error_rate > expected_error_rate:
53            estimated_m *= 2
54            estimated_k = int((float(estimated_m) / n) * weight) + 1
55            error_rate = (1 - math.exp(- (estimated_k * n) / estimated_m)) ** estimated_k
56            logging.info(estimated_m, estimated_k, error_rate)
57        return estimated_m, estimated_k
58
59    def add(self, msg):
60        """
61        add a string to bloomfilter
62        :param msg:
63        :return:
64        """
65        if not isinstance(msg, str):
66            msg = str(msg)
67        positions = []
68        for _hash_value in self._hashes(msg):
69            positions.append(_hash_value % self.num_of_bits)
70        for pos in sorted(positions):
71            self._data_store.set(int(pos))
72
73    @staticmethod
74    def open(self, fname):
75        with open(fname) as fp:
76            raise NotImplementedError
77
78    def __str__(self):
79        """
80        output bitset directly
81        :return:
82        """
83        pass
84
85    def __contains__(self, msg):
86        if not isinstance(msg, str):
87            msg = str(msg)
88        positions = []
89        for _hash_value in self._hashes(msg):
90            positions.append(_hash_value % self.num_of_bits)
91        for position in sorted(positions):
92            if not self._data_store.test(position):
93                return False
94        return True
95
96    def __len__(self):
97        return self._size

四、後言

    學完這一期,我覺得,是時候拿起高數書,線代書,概率論,離散數學…好好學習數學了,哈哈哈!

附贈:七夕快樂大家。

邊敲邊學邊做,堅持學習分享。

相關焦點

  • Scrapy實戰3:URL去重策略
    一、前言今天給大家分享的是,Python爬蟲裡url去重策略及實現。二、url去重及策略簡介1.url去重    從字面上理解,url去重即去除重複的url,在爬蟲中就是去除已經爬取過的url,避免重複爬取,既影響爬蟲效率,又產生冗餘數據。
  • 中學生邊玩邊學python編程(1)
    許多人把python比作DOS時代的BASIC,可見python是比較適合沒有編程基礎的學生學習的。本教學採用的編程軟體是python 3.6版本。具體下載大家百度一下就會很容易找到,這裡就不給出下載地址了。.
  • 看日劇學日語,邊娛樂邊學習
    看日劇學日語,邊娛樂邊學習想必有很多愛學日語的小夥伴是因為愛上了看日劇才學習日語的吧,那你知道怎樣去看日劇能更好地吸收到日語的學習嗎,今天大瑄哥就帶大家了解娛樂學習方法,從此讓你輕鬆聽懂日語啦。第三步,擋住漢語字幕,第二遍邊聽邊看走起擋住漢語字幕的目的是,已經了解了劇情,所以在邊聽日語和邊看字幕來吸收更多的日語,慢慢刺激耳朵,同時也會帶動我們的口語。到這裡還沒有結束,還有下一步行動。
  • 免費領:140首幼兒畫圖古詩(邊畫邊記),列印給孩子學習
    邊畫邊記 學古詩1畫什麼樣的圖形符號、畫得像不像並不重要,重要的是,在這個過程中孩子充分理解了詩句的含義只不過在充分理解古詩含義的基礎上,通過二次創作將一字一句印到了腦海裡。邊畫邊記 學古詩2思維導圖又叫心智導圖,是表達發散一性思維的有效的圖形思維工具
  • 《集合啦動物森友會》怎麼在懸崖邊種樹 懸崖邊種樹方法介紹
    再來就是用特殊方法來敲掉懸崖,把懸崖敲成菱形就可讓樹木只留一格。 完成的的懸崖樹加個圍欄讓他好看一點,這樣就不用怕被壞人偷走錢。 以上就是動物之森懸崖邊種樹方法介紹的相關內容了,看過的玩家可以去遊戲內試一試哦。
  • 成語腦筋急轉彎:用孩子喜歡的方式記成語,有趣又高效,邊玩邊學
    今天,啟小達跟大家分享成語腦筋急轉彎,用腦筋急轉彎的形式記成語,有趣又好記,收藏起來,和孩子一起邊玩邊學!
  • 邊聽邊記:四六級聽力長對話必備技能
    長對話由於篇幅較長,想要聽一遍就將主要內容都記清楚,幾乎是不可能的。考生只有聽一遍的機會,邊聽邊記是聽力中一項非常重要的技能,但是做筆記並不是要把聽到的每一個單詞都記下來,筆記無非是幫助記憶的手段,只要能把重要的信息用可識別的符號記錄下來,就算達到了目的。因此為了提高聽與記的效率,應注意把握一定的技巧和原則。
  • 推薦5個邊玩python邊學習的網站!
    今天永恆君就來給給大家推薦一些Python的編程挑戰和練習題,讓學習python更輕鬆和快樂。 注意:難易程度依次由低到高向大家介紹! 1、PythonTip http://www.pythontip.com/coding/code_oj 一個中文網站,裡面的練習題要偏Python基礎算法,非常適合新手的入門練習。練習題還標明了難易程度,可自行選擇合適的難度。
  • 分享15個邊玩遊戲邊學編程的網站
    今天分享15個邊玩遊戲邊學編程的網站。本文作者創客星辰,首發於辰語學習筆記。經常聽到有朋友說,學習編程是一件非常枯燥無味的事情。其實,大家有沒有認真想過,可能是我們的學習方法不對?比方說,你有沒有想過,可以通過打遊戲來學編程?今天我想跟大家分享幾個網站,教你如何通過邊打遊戲邊學編程!
  • 邊看邊學幼兒英語Flash:紅綠燈
    新東方網>英語>英語學習>少兒英語>英語故事>正文邊看邊學幼兒英語Flash:紅綠燈 2012-11-21 22:46 來源:可可英語 作者:
  • 王一博把《街舞》當成了學校,和隊員學舞蹈,邊吃香蕉邊記動作
    王一博把《街舞》當成了學校,和隊員學舞蹈,邊吃香蕉邊記動作 最近一期播出之後,很多網友對王一博徹底產生了改觀,也許之前他的人設一直是高冷的,屬於那種不善言談的類型,因為在這個節目剛剛官宣的時候網友們就說過,這一期的4位隊長真的各有各的特色,一個說不清楚,一個說不利索,一個不說話,一個說不明白
  • 邊看邊學幼兒英語Flash:起立與坐下
    新東方網>英語>英語學習>少兒英語>英語故事>正文邊看邊學幼兒英語Flash:起立與坐下 2012-11-21 22:50 來源:可可英語 作者:
  • 邊看邊學幼兒英語Flash:整理床鋪
    新東方網>英語>英語學習>少兒英語>英語故事>正文邊看邊學幼兒英語Flash:整理床鋪 2012-11-21 22:50 來源:可可英語 作者:
  • 邊看邊學幼兒英語Flash:十字路口
    新東方網>英語>英語學習>少兒英語>英語故事>正文邊看邊學幼兒英語Flash:十字路口 2012-11-21 22:50 來源:可可英語 作者:
  • 邊學邊看幼兒英語Flash:整理房間
    新東方網>英語>英語學習>少兒英語>英語故事>正文邊學邊看幼兒英語Flash:整理房間 2012-11-21 23:04 來源:可可英語 作者:
  • 邊看邊學幼兒英語Flash:青蛙吃蒼蠅
    新東方網>英語>英語學習>少兒英語>英語故事>正文邊看邊學幼兒英語Flash:青蛙吃蒼蠅 2012-11-21 22:45 來源:可可英語 作者:
  • 邊玩遊戲邊學英語單詞:創新還是噱頭?
    如果有一天,孩子抱著手機或者iPad正開心地玩著遊戲,他卻告訴你他是在學英語單詞,你相信還是不相信?家住北京市海澱區的老李就碰到了這個問題。  最近兩個星期,17歲正在讀高二的兒子小李每天放學回家除了玩手機,就是抱著iPad,不像往常那樣在書房寫作業。
  • 要不要邊工作邊考研?
    比如,我之前在大學時教過的一個學生,也是學會計專業的,個人專業素質很強,本科畢業後就去了一家會計事務所,然後邊實習邊準備註冊會計師的考試,兩年後就通過了所有考試,拿到了註冊會計師證書。後來,她跳槽去了更好的會計師事務所,工資也翻了幾倍。如果你屬於能力不夠強悍的,建議選擇繼續考研,這樣最起碼能在校園裡多學點本領。
  • 初中文言文重點詞彙總結,含詳細解釋,暑假邊玩邊學!
    比如說,廣東省2019年初中學業水平考試的文言文閱讀文段就是範仲淹的《嶽陽樓記》,這篇文言文出自人教版語文教材八年級下冊。與課內閱讀相對應,課外閱讀就是指試卷中的文言文選自課本之外的材料。但不管是課內閱讀還是課外閱讀,所考的東西都是差不多的,其中對於文言文的那些詞彙的理解也是會經常考到的。
  • 大學畢業生發明「英語撲克」 製作者介紹,可以邊玩邊記單詞
    2006-11-106:39:59近日,在大連部分高校裡喜好打撲克的大學生中開始流行一種特殊撲克,大學生可以邊打滾子邊潛移默化地記英語單詞。  昨日,「英語撲克」的製作者——去年剛從大連某高校畢業的25歲的盧書林,講述了製作「英語撲克」的經過。據其介紹,他已經於10月9日向國家知識產權局申請了專利。