如何用python写布隆过滤器

Python07

如何用python写布隆过滤器,第1张

下面的是网络上找到的python的布隆过滤器的实现.

#!/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本身的二进制操作看起来很麻烦，这个就简单多了

如果解决了您的问题请采纳！

如果未解决请继续追问

十几万行吧

首先创建了一个容量为10的的布隆过滤器

然后分别加入 ‘dog’，‘fish’，‘cat’三个对象，这时的布隆过滤器的内容如下：

然后加入‘bird’对象，布隆过滤器的内容并没有改变，因为‘bird’和‘fish’恰好拥有相同的哈希。

最后我们检查一堆对象（’dog’, ‘fish’, ‘cat’, ‘bird’, ‘duck’, ’emu’）是不是已经被索引了。结果发现‘duck’返回True，2而‘emu’返回False。因为‘duck’的哈希恰好和‘dog’是一样的。

主要分割

主要分割使用空格来分词，实际的分词逻辑中，还会有其它的分隔符。例如Splunk的缺省分割符包括以下这些，用户也可以定义自己的分割符。

] ( ) { } | ! , ‘ ” *\n\n s\t &amp? + %21 %26 %2526 %3B %7C %20 %2B %3D — %2520 %5D %5B %3A %0A %2C %28 %29

搜索

好了，有个分词和布隆过滤器这两个利器的支撑后，我们就可以来实现搜索的功能了。

上代码：

Splunk代表一个拥有搜索功能的索引集合

每一个集合中包含一个布隆过滤器，一个倒排词表（字典），和一个存储所有事件的数组

当一个事件被加入到索引的时候，会做以下的逻辑

为每一个事件生成一个unqie id，这里就是序号

对事件进行分词，把每一个词加入到倒排词表，也就是每一个词对应的事件的id的映射结构，注意，一个词可能对应多个事件，所以倒排表的的值是一个Set。倒排表是绝大部分搜索引擎的核心功能。

当一个词被搜索的时候，会做以下的逻辑

检查布隆过滤器，如果为假，直接返回

检查词表，如果被搜索单词不在词表中，直接返回

在倒排表中找到所有对应的事件id，然后返回事件的内容

更复杂的搜索

更进一步，在搜索过程中，我们想用And和Or来实现更复杂的搜索逻辑。

上代码：