乐趣区

关于数据结构:特殊的数据结构布隆过滤器的原理和实现及探究

一、布隆过滤器的应用价值

有时候咱们须要判断一个元素是否在一个汇合中。比方,在字处理软件中,须要查看一个单词是否拼写正确(也就是要判断它是否在已知的字典里);在警察零碎中,一个嫌疑人的名字是否呈现在嫌疑名单上;在网络爬虫里,一个网址是否曾经被拜访过,等等。

最间接的办法就是讲汇合中的元素存在计算机中,遇到一个新元素时,将它和汇合中的元素间接比拟即可。一般来讲,计算机中的汇合是用哈希表(Hash Table)来存储的。它的益处是疾速精确,毛病是消耗存储空间。

为什么说消耗存储空间呢?其根本原因是哈希表办法须要把实实在在的具备特定长度(每个 Email 地址对应成一个 8 字节的信息指纹)的元素的信息指纹存储在内存或硬盘中的哈希表中,这个存储量在理论利用中个别是相当大的。比方每存储一亿个 Email 地址,须要 0.8G 大小的数字指纹存储空间,思考到哈希表的存储空间利用率个别只有一半,所以须要 1.6G 的存储空间。如果存储几十亿上百亿的 Email 地址,那就须要百亿字节的内存存储空间。

而布隆过滤器只须要哈希表 1 / 8 到 1 / 4 的大小就能解决同样的问题,它实际上是一个很长的二进制向量和一系列的随机映射函数。

上面以 WEB 页面地址的存储为例来阐明布隆过滤器的工作原理。

假设存储一亿个 WEB 页面地址,先建设一个 16 亿二进制(比特),即 2 亿字节的向量,而后将这 16 亿个二进制位清零。对于每一个 WEB 页面地址 X,用 8 个随机数产生器(f1,f2,…,f8)。再用一个随机数产生器 G 把这 8 个信息指纹映射到 1 -16 亿中的 8 个自然数 g1,g2,…g8。当初把这 8 个地位的二进制位都置为 1。对着一亿个 WEB 页面地址都进行这样的解决后,一个针对 WEB 页面的布隆过滤器就建成了,见下图。

布隆迪过滤器的映射办法

当初,让咱们看看如何用布隆过滤器来检测一个 WEB 网页地址 Y 是否曾经被咱们收录。用雷同的 8 个随机数生成器(f1,f2,…,f8)对这个 WEB 网页地址产生 8 个信息指纹 s1,s2,…s8,而后将这 8 个指纹对应到布隆过滤器的 8 个二进制位,别离是 t1,t2,…,t8。如果 Y 已被收录,显然 t1,t2,…,t8 对应的 8 个二进制位肯定是 1。通过这样的形式咱们可能很快地确定一个 WEB 页面是否已被咱们收录。

二、布隆过滤器的实现

布隆过滤器实现代码:

#encoding=UTF-8 
'''
Created on 2014 年 6 月 21 日
@author: jin
'''
import BitVector  
class MyHash():# 哈希类,依据不同参数初始化后作为不同的哈希函数 
      
    def __init__(self, cap, seed):  
        self.cap = cap  
        self.seed = seed  
      
    def hash(self, value): #计算哈希值得过程 
        ret = 0  
        for i in range(len(value)):  
            ret += self.seed*ret + ord(value[i]) #ord() 函数计算传入的 url 字符串中每一个字符在 ASCII 码表中对应的程序值
        return (self.cap-1) & ret  #返回哈希值,即在比特序列中的地位    
 
class BloomFilter(): 
        
    def __init__(self, BIT_SIZE=1<<31):  
        self.BIT_SIZE = 1 << 31  #不拢过滤器的比特数,
        self.seeds = [5, 7, 11, 13,19, 31, 37, 61]  #8 个种子,用于产生 hash 函数
        self.bitset = BitVector.BitVector(size=self.BIT_SIZE)  
        self.hashFuncList = []           
        for i in range(len(self.seeds)):  
            self.hashFuncList.append(MyHash(self.BIT_SIZE, self.seeds[i]))  #对每个种子,创立一个 MyHash 对象,一共 8 个          
    def insert(self, value):  #插入值,这里并非真正地插入并存储,而是把该值对应的 8 个地位的比特地位为 1
        for function in self.hashFuncList:  
            locationBit = function.hash(value)  #计算应该置为 1 的比特位
            self.bitset[locationBit] = 1  
    def isContaions(self, value):  
        if value == None:  
            return False  
        ret = True  
        for f in self.hashFuncList:  
            locationBit = f.hash(value)  
            ret = ret & self.bitset[locationBit]  #能够看出,对 8 个哈希函数,只有有一个为 0,那么将返回 0,即该值尚未存在
        return ret 
       
def Main(): #主函数
 
    fd = open("urls.txt")  #有反复的网址 http://www.kalsey.com/tools/buttonmaker/
    bloomfilter = BloomFilter()  
    while True:  
        url = fd.readline()  
        if cmp(url, 'exit') == 0:
            print 'complete and exit now'
            break  
        elif bloomfilter.isContaions(url) == False:  
            bloomfilter.insert(url)  
        else:  
            print 'url :%s has exist' % url                 
Main() 

url.txt 外部存储有一系列网址,最初一行是‘exit’,内容如下:

http://sourceforge.net/robots.txt
http://sourceforge.net/
http://sourceforge.net
http://sourceforge.net and https://sourceforge.net
http://sourceforge.net/sitemap.xml
http://sourceforge.net/allura_sitemap/sitemap.xml
http://sourceforge.net/directory_sitemap.xml
http://a.fsdn.com
http://a.fsdn.com/con/img/sftheme/favicon.ico
http://a.fsdn.com/con/js/min/sf.head.js
http://a.fsdn.com/con/js/sftheme/dd_belatedpng.js
http://fonts.googleapis.com
http://fonts.googleapis.com/css
http://a.fsdn.com/con/css/sf.css
http://sourceforge.net/blog/feed/
http://email.playtime.uni.cc/ 
http://services.nexodyne.com/email/ 
http://gizmo967.mgs3.org/Gmail/ 
http://www.hkwebs.net/catalog/tools/gmail/ 
http://sagittarius.dip.jp/~toshi/cgi-bin/designmail/designmail.html 
http://www.eoool.com/
http://sourceforge.netand
https://sourceforge.net
http://a.fsdn.com/con/js/adframe.js
http://sourceforge.net/directory/
http://kalsey.com/tools/buttonmaker/ 
http://www.lucazappa.com/brilliantMaker/buttonImage.php 
http://www.feedforall.com/public/rss-graphic-tool.htm  
http://www.yugatech.com/make.php 
http://www.hkwebs.net/catalog/tools/buttonmaker/index.php
http://phorum.com.tw/Generator.aspx 
http://www.logoyes.com/lc_leftframe.htm 
http://cooltext.com/Default.aspx
exit

运行成果如下,能够看到未产生存储地址抵触:

complete and exit now

往 url.txt 外面再减少一个原来未有的网址:

http://www.kalsey.com/tools/buttonmaker/

再次运行,居然产生了抵触,如下:

url :http://www.kalsey.com/tools/buttonmaker/
 has exist
complete and exit now

这阐明此网址和另外一个网址对应的 8 个信息指纹雷同,尽管它们自身的值是不同的,这就产生了抵触。

能够看到布隆过滤器有肯定的误识别率。上面咱们对其进行剖析。

三、误识别率的问题

假设布隆过滤器有 m 比特,外面有 n 个元素,每个元素对应 k 个信息指纹的哈希函数,当然 m 个比特里有 0 也有 1。咱们假设某个比特为 0, 在这个布隆过滤器里插入一个元素,他的第一个哈希函数会把过滤器中的某个比特置为 1,现实状况下,任一比特位被置 1 的概率是 1 /m,它仍然为 0 的概率则是 1 -1/m。

对于过滤器中的一个特定地位,如果这个元素的 k 个哈希函数都没有把它设置成 1,其概率是

。如果过滤器插入第二个元素,这个特定地位仍不被置 1 的概率是

,相似的,插入 n 个元素其仍为 0 的概率是

。反过来,一个比特在插入 n 个元素后,被置 1 的概率则是

当初假设这 n 个元素都放到布隆过滤器中了,新来的一个不在汇合中的元素,因为它的信息指纹的哈希函数都是随机的,因而,它的第一个哈希函数正好命中某个值为 1 的比特的概率就是上述概率。一个不再汇合中的元素被误辨认为曾经在汇合中,须要所有的哈希函数对应的比特值均为 1,其概率为

咱们上面对简化的误识别率的公式进行钻研。

图 2 误识别率与 m / n 的关系

图 2 的代码:

k=8
r =  np.linspace(1,50,1000)
p = np.power(1-np.exp(-k/r),k)
plt.title('misjudgment & m/n')
plt.plot(r,p)
plt.xlabel('m/n')  
plt.ylabel('misjudgment')  
plt.show() 

图 3 误识别率与 k 的关系

图 3 的代码:

r = 30;
k = np.linspace(1,10,100)
p = np.power(1-np.exp(-k/r),k)
plt.title('misjudgment & k')
plt.xlabel('k')  
plt.ylabel('misjudgment')  
plt.plot(k,p)
plt.show()

首先祝贺您,可能认真的浏览到这里,如果对局部了解不太明确,倡议先将文章珍藏起来,而后对不分明的知识点进行查阅,而后在进行浏览,相应你会有更深的认知。如果您喜爱这篇文章,就点个赞或者【关注我】吧!!

退出移动版