| « | November 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | | | | | | |
|
公告 |
| 暂无公告... |
| Blog信息 |
|
blog名称:
日志总数:14
评论数量:24
留言数量:0
访问次数:54873
建立时间:2007年12月28日 |
| |
|
 [论文]基于BF的大规模网页去重策略研究1
原创空间, 软件技术, 科学研究
bg1011 发表于 2007/12/28 21:51:15 |
|
基于Bloom Filter的大规模网页去重策略研究
【摘要】Bloom Filter是一种空间高效的集合查找和表示算法。针对大规模信息采集，运用Bloom Filter及其改进算法，在误差允许的条件下，通过URL散列运算可以有效地对同源网页进行去重。实验证明通过对其参数进行合理的调整，可以达到满意的结果。
【关键词】布隆过滤器，散列函数，URL，网页去重
【分类号】 TP391.3
The Research of large-scale URL Filter Based on Bloom Filter
【Abstract】Bloom Filter is a space-saving set search and represent algorithm for large-scale information collection. The Bloom Filter and its improvement algorithm, on the condition of error allowing, can be used to the homology URL page filter through URL Hashing. Experiment has proved that it can achieve satisfactory results through reasonable adjustments of its parameter.
【Keywords】 Bloom Filter，Hash Function，URL，URL Filter
1引言
Web信息的采集，通常是利用网络爬虫等工具去遍历WWW，它把WWW看作一个以网页为节点，网页间链接为边的超大规模有向图，然后利用图的遍历算法对WWW进行遍历。在网络遍历的过程中，需要判断待采集的页面是否已经采集过了，这就需要把已经采集的网页地址记录下来，组成已采集网页地址集合（记为：visited-set），当新的采集开始之前，首先判断其地址是否在visited-set中，如在其中，表示网页已经采集，否则采集网页，把网页地址放visited-set中，从而避免网页的重复采集，浪费资源。为了实现集合中数据的快速查找，需要把URL映射为集合中的地址，这就需要设计一种高效且冲突率低的散列算法；同时由于WWW上网页数据的巨大（一份报告指出，截止2005年1月份其网页数量至少达到115亿[1]），普通的Hash算法已经不能满足空间的要求，所以又需要一种节约空间的算法。
本文运用Bloom Filter算法设计了一种节省空间的大规模数据表示和查找算法，以应对海量信息采集的需求。文章的组织结构为：第2部分对Bloom Filter算法进行简要的介绍，包括算法思想、误判率计算以及哈希函数选取策略；第3部分给出了Bloom Filter及其改进算法在大规模网页去重策略中的应用；第4部分通过实验对Bloom Filter算法在网页去重中的应用给出了可行性分析；第5部分进行的总结以及进一步的研究工作。
2 Bloom Filter算法
2.1 Bloom Filter算法简介
Bloom Filter是由巴顿布隆于1970年提出的[2]，它实现的基础上是一个很长的二进制位向量和一系列随机散列函数。Bloom Filter是一种基于散列的查找算法，用于查找一个元素是否在集合中，和散列表相比，它的优点是节约空间，可以对海量数据集进行表示和查找操作。由于散列函数的随机性，可能使得某个元素不属于集合而被判定属于集合，在此，称其为误判，其大小为误判率Perr。
Bloom Filter算法的基本思想为：
①设数据集合A={a1,a2,…,an}，含有n个元素，为待操作的集合；
②Bloom Filter用一个长度为m的位向量V来表示集合中的元素，位向量初始化全为0；
③ k个具有均匀分布特性的散列函数h1 h2,,…,hk ，值域均为{ 1 , 2 ,⋯, m} ；
④ 对于元素的加入操作首先通过K个散列函数产生K个随机数h1,h2,…,hk，使位串V的相应h1,h2,…,hk位均置为1；同理，元素的查找为判定相应位是否全为1。
2.2 Bloom Filter误差分析
Bloom Filter算法在进行集合的元素表示时，由于通过k个散列函数使位向量相应位置1，经过多次集合元素增加操作后，使得位向量若干位被重复置为1。当新的元素加入集合之前，首先通过集合查找运算判定元素是否在集合中，同样，通过k个散列函数的映射到相应的位，如果相应位都为1，则判定元素在集合中，否则判定元素不在集合中。对于已经映射到集合中的元素，显然通过集合查找运算一定可以判定其中集合中，但对于尚未映射到集合中的元素，可能存在误判，即不在集合中的元素误判为在集合中。
下面我们对误判率进行分析：
在Bloom Filter表示方法中，某一位被置为1个概率为 ，为0的概率为1- ,散列函数共执行了kn次，所以在运算结束时，某位仍为0的概率为：
P0=（1- ）kn e-kn/m (式1)
所以误判的概率为：
Perr=(1- P0)k=(1-(（1- ）kn))k (1- e-kn/m)k (式2)
当给定k和n时，由式（2）可知随着m的增大Perr减小；对于给定的n和m，下面求 Perr的最小值，对式（2）两端求导，令 =0，可求得当k= ln2 0.7 时， Perr_min 0.6185m/n为最小的误判率。
2.3 散列函数考虑
散列(Hashing)是信息表示和查找所用的一项基本技术[3]，其优化性能在很大程度上取决于输入键的结构，本文所研究散列的键是用于访问网页的URL。在运用Bloom Filter算法进行集合的表示和元素的查找过程中，需要对待查找（或表示）的数据进行k次散列操作，所以散列函数的选取成为了影响系统性能的关键因素。针对web信息的采集，文献[4]评价比较了五种Hash函数，并对它们在URL映射的性能进行了比较分析，结果显示Strhash和Tianlhash的性能较佳。文献[5] 给出了两种针对URL散列性能很好的函数，并通过2000万URL的实验进行了评价，结果表明,HfIp 都是很可靠的,可以首选使用，并在北大天网搜索引擎系统中得到工程性的检验。 |
|
|
回复:基于BF的大规模网页去重策略研究1
原创空间, 软件技术, 科学研究
cs7011(游客)发表评论于2009/9/6 22:59:11 |
| 同感,这篇文章很好,想看看后续内容,你能告诉我密码吗，如果可以，请发到我的邮箱cs7011@163.com，谢谢 |
|
|
回复:基于BF的大规模网页去重策略研究1
原创空间, 软件技术, 科学研究
网页游戏(游客)发表评论于2008/6/12 23:39:53 |
| http://www.douzhua.com 我也在做，去重不好弄呀.. |
|
|
回复:基于BF的大规模网页去重策略研究1
原创空间, 软件技术, 科学研究
茶叶蛋(游客)发表评论于2008/6/12 21:56:45 |
| 您好：我最近一直想找有关网页去重的文章，您能不能告诉我剩余几篇博客的密码，不胜感激。我电子邮箱是：yangren5320@163.com |
|
|
回复:基于BF的大规模网页去重策略研究1
原创空间, 软件技术, 科学研究
wangmingongan发表评论于2008/6/12 15:14:33 |
| 这篇文章很好，我想看看其他部分的内容，你能告诉我密码吗，如果可以，请发到我的邮箱，wangmingongan@qq.com，谢谢 |
|
» 1 »
|