布隆过滤器

平日的判重做法是如何呢?Bloom Filter. 简单讲它仍然是一种hash的办法，然则它的特点是，它可以应用固定的内存(不随url的数量而增长)以O(1)的效力剖断url是否已经在set中。可惜世界没有白吃的午餐，它的独一问题在于，如不雅这个url不在set中，BF可以100%肯定则个url没有看过。然则如不雅这个url在set中，它会告诉你：这个url应当已经出现过，不过我有2%的不肯定性。留意这里的不肯定性在你分派的内存足够大年夜的时刻，可以变得很小很少。

# bloom_filter.py 
 
BIT_SIZE = 5000000 
 
class BloomFilter: 
     
    def __init__(self): 
        # Initialize bloom filter, set size and all bits to 0 
        bit_array = bitarray(BIT_SIZE) 
        bit_array.setall(0) 
 
        self.bit_array = bit_array 
         
    def add(self, url): 
        # Add a url, and set points in bitarray to 1 (Points count is equal to hash funcs count.) 
        # Here use 7 hash functions. 
        point_list = self.get_postions(url) 
 
        for b in point_list: 
            self.bit_array[b] = 1 
 
    def contains(self, url): 
        # Check if a url is in a collection 
        point_list = self.get_postions(url) 
 
        result = True 
        for b in point_list: 
            result = result and self.bit_array[b] 
     
        return result 
 
    def get_postions(self, url): 
        # Get points positions in bit vector. 
        point1 = mmh3.hash(url, 41) % BIT_SIZE 	
			
 2/6   首页 上一页 1 2 3 4 5 6 下一页 尾页
	
			

　　推荐阅读
　　Python源码理解: +=和 xx = xx + xx的区别
            
            前菜在我们应用Python的过程, 很多时刻会用到 + 运算, 例如:先来看看字节码:a = 1 + 2  print a  # 输出  3  不但在加法中应用, 在字符串的拼接也同样发挥这重要的感化, 例如:a = 'abc' +>>>详细阅读


本文标题：Python编写知乎爬虫实践
地址：http://www.17bianji.com/lsqh/35819.html
 1/2    1