网页消重中多维布隆过滤器算法的运用

时间:2021-03-11 10:15:32 计算机应用毕业论文 我要投稿

网页消重中多维布隆过滤器算法的运用

  布隆过滤器的原理,通过对原理、实现步骤进行分析,得出此算法在网页消重中的作用以及缺陷,以下是小编搜集整理的一篇探究网页消重中多维布隆过滤器算法运用的论文范文,欢迎阅读查看。

  引言

  进入21世纪以后,随着电子计算机以及相关技术的迅猛发展和网络通信设备的大量普及,互联网的总体规模日益增大,日新月异的互联网技术以及海量的互联网信息也促进了社会、经济和科技的高速发展,增加了人们获取信息的渠道和速度。根据2015年11月的最新数据,互联网上活动网站的数量达到了902,997,800个[1].网站的快速增长同时也意味着互联网中信息的急速膨胀,这些信息有些是有用的、有些是没用的、有些甚至完全是一些垃圾页面。面对由于互联网信息爆炸带来的信息孤岛、信息搜集困难等现象,人们发明了搜索引擎[2-4]以解决人们快速在互联网中找到所求的需求。但是,由于搜索引擎的采集器是由程序自动运行的,所以在抓取网页信息的同时,也会收集到很多重复网页。因此,如果没有一个高效的URL去重模块,用以防止系统对已经抓取过的网页进行重复抓取,浪费宝贵的网络带宽和CPU时间,网络爬虫系统必将不堪重负。

  在众多的URL去重技术中[5-7],布隆过滤器(BloomFilter)[8]是其中优秀的一个,而其主要缺点在于较高的误识别率,但若使用多维布隆过滤器进行识别,可以大大降低误识别率。本文充分利用多维布隆过滤器查询快速、资源占有量少的特点,提出一种基于多维布隆过滤器的网页搜索去重方法,并给出程序设计方案及伪代码描述。

  1布隆过滤器

  在互联网中,要查找一个URL是否己经被抓取过,首先会想到的方法就是建立一个已抓取URL集合,然后查找新的URL是否存在已抓取URL集合中,如果用普通的顺序查找法,效率显然很低。而另一个比较简单的办法是采取传统的hash方法,即把每个URL看成一个元素,这就需要把每个元素存储在hash表中。在每次发现一个新的元素时,首先会通过hash函数计算出这个元素的对应位置,之后使用这个位置的元素与这个新元素进行对比,如果两者相同,就说明这个新元素是重复的,反之则说明这个新元素是还未保存过的。传统的hash方法不会发生错误,而且存在于hash表中的数据也可以随时删除。但是,对于网页去重来说,只需判断一个特定的元素是否存在于集合中。因此,使用hash表保存下整个URL的内容会造成很大的内存浪费,然而内存资源有限,显然传统的hash方法不能很好的满足需求。

  布隆过滤器[9-11]是由HowardBloom在1970年提出的。他仅使用了一系列的bit位来保存数据,就可以检测一个元素是否已经存在于集合内,因此这种算法有着很好的空间利用率。但是为了节约空间,这种算法也存在着一些问题,它会对元素产生错判。不过庆幸的是,这个算法只会对在集合内的元素产生错判,但是并不会对不在集合内的元素产生错判。也就是说,如果布隆过滤器返还的结果如果是false,说明元素确实不在集合内;如果返还的是ture,只能说明元素可能存在于集合中。因此布隆过滤器实际上是一种牺牲了正确率换取时间和空间的算法。

  1.1布隆过滤器介绍

  布隆过滤器的原理如下[12]:一个布隆过滤器由k个相互独立的哈希函数h1,h2,…,hk(k值域为[0,1,2,…,m],是整数)和一个位向量组成,初始时,位向量内全部为0.当需要插入一个新数据时,用k个哈希函数对n个数据对象的集合S={sl,s2,…,sn}(m>n)的某个数据对象计算一个地址序(hi(s1),h2(sl),…,hk(sl)),然后将位向量对应地址序列的位置置为1,称该位向量装入了s1.

  对于查询某个数据对象s2是否存在于集合时,同样先检查表示s2的位向量对应该数据对象地址序列的.位,如果均为1,则该数据对象属于位向量集,否则不属于位向量集。但是,即使是采用均匀的哈希函数,并且使用了多个不同的hash函数,地址冲突也是不能避免的,因此布隆过滤器算法可能对位向量中的同一个位多次置1.所以在进行数据查询时可能出现错判。关于布隆过滤器算法的缺点,会在1.3做详细讨论。

  由以上分析可知,当布隆过滤器算法用于URL去重时,由于每个地址不需要存储URL内容,只需存储1或0.因此,每个地址只需要一个bit的空间。在每次网络爬虫得到一个新的URL的时候,会先判断这个元素是否属于集合,此时会对该元素重新进行多次哈希,当哈希后所得的对应位置都为1时,就判断该元素已经存在于集合中。那么就抛弃这个URL,反之,就保存这个URL,并且更新集合信息。具体原理图如下图1.

  1.2布隆过滤器的优点

  布隆过滤器的优点是空间效率和查询时间都远远超过一般的算法。在占用空间上,布隆过滤器只需要哈希表1/8~1/4的大小就能解决同样的问题[13];更重要的是,在时间复杂度方面,布隆过滤器的查找时间为常数,不随过滤器增大而变慢。

  1.3布隆过滤器的缺点

  由以上分析可知,布隆过滤器算法比起普通算法,在时间和空间利用率上有着明显的优势,但是布隆过滤器算法也并非十全十美的,他存在着以下问题:

  (1)因为利用固定的hash函数,并且得到的存储结果仅仅是某个槽号,因此查找的时间是个常数,但是每个槽中存储的不是实际url,因此,可能会出现某个url映像的几个位置都己经被其他url占据的情况,产生错判。

  (2)因为一个url对应多个槽,而且这些槽是可以重复利用的,因此不用处理冲突。但是正因为如此该算法不能随便删除某个已经存在的url,否则会出错。

  2一种改进布隆过滤器算法

  根据上文提及到的,布隆过滤器的缺点是其误识别率,因此,如何在不降低判别性能的前提下降低布隆过滤器的误识别率就是研究的主要方向,本文基于此目的提出了一种改进的布隆过滤器算法,称为多维布隆过滤器。

  2.1基本思想

  多维布隆过滤器的基本想法是,通过使用S组位向量来表达数据集合,每组位向量对应k个hash函数,每组位向量包含2个位向量,其中一个是N位大小的V1,另一个是N/k位大小的V2,每组hash函数划分到两部分k1和d2,用于V1映射的是k1,用于V2映射的是d2.

  插入元素时,对于每组位向量,k1把该元素映射到V1中并在V1对应位置置1,k2把数据元素映射到V2中并在V2对应位置置1.判定元素时,分别检查经过每组的hash函数k1和k2的映射后,V1和V2的相关位置是否为1,若有一组位向量全为1,则认为该元素属于集合。

  2.2性能分析

  分析上述算法,可以看出来,多维布隆过滤器实际上是由多组基本的布隆过滤器构成的。每个布隆过滤器都作为多维布隆过滤器的一部分,参加整体运算。

  因此,这里可以得到每组两个位向量的误识别率为:

  由公式可知,在s,k,n这些参数一致的情况下,多维布隆过滤器同标准布隆过滤器相比,具有较低的误判率,并且维数越高,误判率越低。

  不同维度的过滤器在搜索去重中处于并行工作的状态,因此,基于此技术应用实现的多维布隆过滤器引擎查询时间和标准布隆过滤器引擎查询时间相等。

  多维布隆过滤器引擎每一维都使用了2个标准的布隆过滤器引擎,参数一致的情况下,占用的存储空间是标准的布隆过滤器引擎的2S倍。

  但是当维数过多时,要让每一个维度都处于并行工作状态对CPU要求较高,而且维数越多,对存储空间的需求也就越大。

  3应用与评价

  对于上面章节讨论的改进布隆过滤器算法-多维布隆过滤器算法的理论研究,我们仍需要进行大量的实验对其进行验证。本论文设计实现程序,从而模拟了两种算法,进而通过实验对两种算法的性能进行比较。

  3.1实验评价标准

  为了能够更加直观的对比试验结果,试验根据重复网页对搜索引擎的影响制定了以下三个主要的比较数据。他们是:

  (1)运行速度:在一定抓取范围内,每种算法完成所用的时间。因为实际运用中网页数量过于庞大,因此这里设定一个固定时间,在这段时间内抓取到非重复URL的数量越多,则算法运行的速度越快。

  速度=非重复URL数量/时间

  (2)重复率:也就是在第二章提到的重要评价指标。

  重复率=重复的URL/抓取到的URL总数

  (3)空间利用率:用于去重的位向量组所占空间。

  用Bit为单位。

  3.2实验步骤

  本实验使用Heritrix作为爬虫,主要抓取一些时事新闻。因此,实验首先抓取几个常用的门户网站页面做基础。本论文中是先抓取的新浪,网易,腾讯,搜狐。之后在百度里搜索某个新闻关键词做为基础。

  开始抓取搜索到的网页。之后分别使用三种不同的算法,在抓取范围相同的前提下,设定时间为1小时。

  并且,为了实验数据更加准确,本实验为每种算法设置不同的可选参数来验证前面的结论,具体如下:

  ●布隆过滤器:hash函数个数k;向量空间大小N

  ●多维布隆过滤器:每组hash函数个数k;向量空间大小N;向量维度S

  3.3结果与分析

  对于实验结果,我们首先对比多维布隆过滤器中,在k=4,N=150时,不同向量维度S下的误识别率变化,如图2所示。

  从图4.5中,我们可以得到结论,误识别率随着S值的增加而减小。S值增加往往意味着,多维布隆过滤器算法所需的空间大小也相应提高,所以,在实际中,我们一般取S的值小于4.

  随后,我们固定S=4,k=4,对比标准布隆过滤器和多维布隆过滤器在位向量空间变化时的误识别率,如图3所示。

  由上图可得,多维布隆过滤器和标准布隆过滤器的误识别率随着位向量空间的增加一直降低,而且多维布隆过滤器误识别率相比标准过滤器一直都要低。

  最后,我们固定S=4,N=150,对比标准布隆过滤器和多维布隆过滤器在hash函数数量k变化时的误识别率,如图4所示。

  从图4中,我们可以得到结论,误识别率随着k值的增加而减小。k值增加往往意味着,hash算法所需的运算时间也相应提高,所以,在实际中,我们一般取k的值小于4.

  综上,通过实验可以得到结论,hash函数数量以及位向量空间大小都可以影响布隆过滤器和多维布隆过滤器的误识别率,向量的维度也可以影响多维布隆过滤器的误识别率。并且,在相同hash函数数量或向量空间大小时,多维布隆过滤器的误识别率均低于布隆过滤器。

  4结语

  本文详细阐述了布隆过滤器的原理,通过对原理、实现步骤进行分析,得出此算法在网页消重中的作用以及缺陷。此后,根据布隆过滤器存在的误识别率的缺点,本文提出了一种改进的布隆过滤器算法--多维布隆过滤器,降低了传统布隆过滤器算法的误识别率。实验结果表明:多维布隆过滤器的误识别率要显着低于传统的布隆过滤器算法,能够显着提高网页消重的性能。

  参考文献

  [1]Netcraft.November2015WebServerSurvey[OL].[2015-11-16].

  [2]阮卫华。搜索引擎优化技术的研究与实现[J].软件,2014,35(7):72-77

  [3]郑晓健。面向领域主题的智能搜索引擎设计[J].软件,2014,35(3):4-5

  [4]郭世龙,王晨升。主题爬虫设计与实现[J].软件,2013,34(12):107-109

  [5]ManberU.Findingsimilarfilesinalargefilesystem[A].ProceedingsoftheUSENIXwinter1994technicalconference[C].1994,1.

【网页消重中多维布隆过滤器算法的运用】相关文章:

网页设计的色彩运用09-20

网页色彩的搭配运用10-03

计算机图像处理在网页设计中的运用论文07-09

艺术设计元素在网页设计中的运用研究论文10-06

案例教学在计算机网页设计中的运用论文07-20

关于多维传播语境中播音主持的论文08-16

网页设计中视觉留白艺术的运用11-12

网页设计中的视觉要素09-21

网页设计中的色彩搭配09-18