Python布隆过滤器实现代码,python布隆过滤器,之前用python写了一


之前用python写了一个网络爬虫,里面url去重用的就是布隆过滤器,不过那个是用c++写的,在windows下用boost编译成 python模块之后再python里面调用,现在用纯python重新写一个,这样爬虫在linux和windows下都可以运行了,下面是代码:

#!/usr/local/bin/python2.7#coding=gbk'''Created on 2012-11-7@author: palydawn'''import cmathfrom BitVector import BitVectorclass BloomFilter(object):    def __init__(self, error_rate, elementNum):        #计算所需要的bit数        self.bit_num = -1 * elementNum * cmath.log(error_rate) / (cmath.log(2.0) * cmath.log(2.0))        #四字节对齐        self.bit_num = self.align_4byte(self.bit_num.real)        #分配内存        self.bit_array = BitVector(size=self.bit_num)        #计算hash函数个数        self.hash_num = cmath.log(2) * self.bit_num / elementNum        self.hash_num = self.hash_num.real        #向上取整        self.hash_num = int(self.hash_num) + 1        #产生hash函数种子        self.hash_seeds = self.generate_hashseeds(self.hash_num)    def insert_element(self, element):        for seed in self.hash_seeds:            hash_val = self.hash_element(element, seed)            #取绝对值            hash_val = abs(hash_val)            #取模,防越界            hash_val = hash_val % self.bit_num            #设置相应的比特位            self.bit_array[hash_val] = 1    #检查元素是否存在,存在返回true,否则返回false     def is_element_exist(self, element):        for seed in self.hash_seeds:            hash_val = self.hash_element(element, seed)            #取绝对值            hash_val = abs(hash_val)            #取模,防越界            hash_val = hash_val % self.bit_num            #查看值            if self.bit_array[hash_val] == 0:                return False        return True    #内存对齐        def align_4byte(self, bit_num):        num = int(bit_num / 32)        num = 32 * (num + 1)        return num    #产生hash函数种子,hash_num个素数    def generate_hashseeds(self, hash_num):        count = 0        #连续两个种子的最小差值        gap = 50        #初始化hash种子为0        hash_seeds = []        for index in xrange(hash_num):            hash_seeds.append(0)        for index in xrange(10, 10000):            max_num = int(cmath.sqrt(1.0 * index).real)            flag = 1            for num in xrange(2, max_num):                if index % num == 0:                    flag = 0                    break            if flag == 1:                #连续两个hash种子的差值要大才行                if count > 0 and (index - hash_seeds[count - 1]) < gap:                    continue                hash_seeds[count] = index                count = count + 1            if count == hash_num:                break        return hash_seeds    def hash_element(self, element, seed):        hash_val = 1        for ch in str(element):            chval = ord(ch)            hash_val = hash_val * seed + chval        return hash_val

测试代码:

#测试代码bf = BloomFilter(0.001, 1000000)element = 'palydawn'bf.insert_element(element)print bf.is_element_exist('palydawn')'''

其中使用了BitVector库,python本身的二进制操作看起来很麻烦,这个就简单多了

评论关闭