今天給大家分享的是,Python爬蟲裡url去重策略及實現。
二、url去重及策略簡介1.url去重從字面上理解,url去重即去除重複的url,在爬蟲中就是去除已經爬取過的url,避免重複爬取,既影響爬蟲效率,又產生冗餘數據。
2.url去重策略從表面上看,url去重策略就是消除url重複的方法,常見的url去重策略有五種,如下:
1
2
3
4
5
6
實現起來最簡單,但效率最低。
其核心思想是,把頁面上爬取到的每個url存儲到資料庫,為了避免重複,每次存儲前都要遍歷查詢資料庫中是否已經存在當前url(即是否已經爬取過了),若存在,則不保存,否則,保存當前url,繼續保存下一條,直至結束。
將訪問過的ur保存到set中,只需要o(1)的代價就可以查詢url,取url方便快速,基本不用查詢,但是隨著存儲的url越來越多,佔用內存會越來越大。
1
2
3
4
5如果是2億個url,那麼佔用內存將達18G,也不是特別方便,適合小型爬蟲。
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
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'''
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
學完這一期,我覺得,是時候拿起高數書,線代書,概率論,離散數學…好好學習數學了,哈哈哈!
附贈:七夕快樂大家。
邊敲邊學邊做,堅持學習分享。