基于 B loom Filte r的大规模网页去重策略研究.pdfVIP

总第 162 期 　2008年 　第 3期 基于 B loom Filter的大规模网页去重策略研究 1 2 2 丁振国 　吴宝贵 　辛友强 1 (西安电子科技大学网络教育学院　西安 7 1007 1) 2 (西安电子科技大学经济管理学院　西安 7 1007 1) 【摘要 】针对大规模信息采集 ,运用 B loom Filter及其改进算法 ,在误差允许的条件下 ,通过 URL 散列运算可以有 效地对同源网页进行去重 。实践证明,通过对其参数进行合理的调整 ,可以达到满意的结果 。 【关键词 】布隆过滤器 　散列函数 　URL 　网页去重 【分类号 】TP391. 3 Research of Large - sca le URL F ilter Ba sed on Bloom F ilter 1 2 2 D ing Zhenguo 　W u B aogu i 　X in Youqiang 1 ( College of N etwork ing Education , X idian Un iversity, X i ’an 7 1007 1, Ch ina) 2 ( Collegel of Econom ics and M anagem ent, X idian Un iversity, X i ’an 7 1007 1, Ch ina) 【Ab stract 】On the condition of error allow ing, the B loom Filter and its imp rovab le algorithm , can be u sed to filter the ho mology URL p age s through URL H a sh ing. Exp erim ent show s that it can ach ieve satisfactory resu lts through reasonab le ad ju stm ents of its p aram eter. 【Keywords】B loom filter　H a sh function　URL 　URL filter 1　引　言 　　W eb 信息的采集 ,通常是利用网络爬虫等工具去遍历万维网,它把万维网看作一个以网页为节点 , 网页间链 接为边的超大规模有向图,然后利用图的遍历算法对万维网进行遍历 。在网络遍历的过程中, 需要判断待采集的 ( 页面是否已经采集过了,这就需要把已经采集的网页地址记录下来 , 组成已采集网页地址集合 记为 : visited - set) ,当新的采集开始之前 ,首先判断其地址是否在 visited - set 中,如在其中,表示网页已经采集 ,否则采集网页 , 把网页地址放在 visited - set 中,从而避免网页的重复采集 ,浪费资源 。为了实现集合中数据的快速查找 , 需要把 URL 映射为集合中的地址 ,这就需要设计一种高效且冲突率低的散列算法 ; 同时由于万维网上网页数据的巨大 (一份报告指出,截至 2005 年 1月 , 网页数量至少达到 115 亿 [ 1 ] ) ,普通的 Ha sh 算法已经不能满足空间的要求 ,所 以更需要一种节约空间的算法 。 　　本文运用 B loom Filter算法设计了一种节省空间的大规模数据表示和查找算法 , 以应对海量信息采集的需求 。 2　B loom F ilter算法 2. 1　Bloom F ilter算法简介 　　B loom F ilter是由巴顿布隆于 1970 年提出的[ 2 ] ,它实现的基础是一个很长的二进制位向量和一系列随机散