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 cmath
from BitVector import BitVector

class 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本身的二進制操作看起來很麻煩，這個就簡單多了