Web信息采集中的哈希函数比较.doc

Web信息采集中的哈希函数比较本课题得到973项目“大规模文本内容计算”(2004CB3181096)基金资助。吴丽辉1,2, 白硕1, 张刚1,2 , 张凯1(1. 中国科学院计算技术研究所软件研究室，北京 100080；2.中国科学院研究生院，北京 100039)Email: Phn:717摘 要:在Web信息采集的过程中,需要判断待采页面是否在已采页面集合中.为了实现快速采集,采用哈希函数来实现.基于一个含有2000多万个URL的序列,通过大规模的实验性评测,比较了函数Tianlhash、ELFhash、HfIp、hf和Strhash的一阶和二阶哈希冲突率.实验结果表明,Strhash和Tianlhash的性能较佳,值得推荐.并且,ELFhash的测试性能要优于HfIp和hf.采用二阶哈希后的天罗Web信息采集系统,占用几兆的内存空间,大大提高了采集速度,并降低了数据库的负荷. 关键词:Web信息采集; 哈希函数; URL 中图法分类号:TP314文献标识码: A Hashing Comparison in Web CrawlingWu Lihui1,2, Bai Shuo1, Zhang Gang1,2+ , Zhang Kai(1.Software Division, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)(2.Graduate School of the Chinese Academy of Sciences, Beijing 100039)Abstract:During the course of Web crawling, it is needed to judge if the coming URLs are in the collection of crawled pages. In order to achieve fast crawling, hashing is adopted. Through a large scale experiment, five hash functions are compared in this paper. The finding is that Strhash and Tianlhash functions are better and thus recommended. And, ELFhash function is better than HfIp and hf. The crawling speed is fast advanced after using second-hash in Tianluo Web crawling system, and the database load is depressed.Key words:Web crawling; hashing; URL1 引言Internet尤其是WWW的飞速发展,给人们带来了前所未有的信息共享与交流.网络已发展成为我们经济、社会、文化、教育以及娱乐等几乎各个方面的重要组成部分.到2004年11月,Google搜索引擎索引的网页数已经超过80亿1.随着互联网的迅速发展,各项基于Web的服务也日益繁荣起来.作为这些信息服务的基础和重要组成部分,基于Web的信息采集正应用于搜索引擎、站点结构分析、页面有效性分析、Web图进化、用户兴趣挖掘以及个性化信息获取等多种应用和研究中.Web信息采集2,主要是指通过Web页面之间的链接关系,从Web上自动获取页面信息,并且随着链接不断向所需要的Web页面扩展的过程.粗略的说,它主要是指这样一个程序,从一个初始的URL集出发,将这些URL全部放入到一个有序的待采集队列里.而采集器从这个队列里按顺序取出URL,通过Web协议,获取URL所指向的页面,然后从这些已获取的页面中提取出新的URL,并将他们继续放入到待采队列里,然后重复上面的过程,直到采集器根据自己的策略停止采集.在Web信息采集的过程中,为了实现快速采集,需要记住已经采集过的页面（记做集合visited-urls）.采集中凡遇到一个页面,需要用它和visited-urls对比,判断该页面的URL是否已在visited-urls中.若在其中,则表示该网页已采集；否则将它放入visited-urls,继续沿其含有的URL向下采集.显然,将visited-urls组织成一个哈希表是很自然的,哈希的对象是用于访问网页的URL,即形如“”之类的字符串3.为了设计高效的URL哈希算法,测试不同的哈希函数对相同的URL列表的冲突率. 2 实验的设计和执行2.1 实验评价标准为了比较不同的哈希函数,需要有和应用背景相关的实验评价标准.假设我们已经有了全国网页的集合,记做P = p1, p2, p3, .对应地,有所有URL的集合,记做URL = url1, url2, url3, .作为研究Web页面采集,我们关心：给定相同的URL列表, 不同函数的哈希冲突率.我们追求的是查询效率,希望冲突率尽可能的少.设有N个URL字符串待处理,将这些字符串用哈希函数F哈希到M个槽中.哈希槽数可能很大.对于千万量级的URL列表,槽数可能大到百万量级.对i（1iM）号槽,哈希到其中的URL个数为Ni.当Ni1时,我们认为其哈希值发生了冲突.统计所有发生哈希值冲突的次数,我们定义该哈希函数的冲突率为冲突次数与N的比值,把哈希函数F的冲突率作为该哈希函数的实验评价标准.统计被哈希在到i号槽中的所有url的数目Ni,可以得到发生哈希值冲突的次数为（Ni1）.考虑所有的槽,我们可用下面的平均冲突次数来表示哈希函数F的冲突率,越小越好., 其中 （1）2.2 实验数据源我们以天网搜索引擎搜集的2000多万个URL序列为实验数据源,燕穹产品号YQ-URLLIST-2002-034.由于URL是不区分大小写的,对这些URL序列不区分大小写去重后,得到19993890个不同的URL列表.2.3 待评价的哈希函数我们考虑五个哈希函数.第一个是在我们天罗Web信息采集系统中采用的Tianlhash函数.unsigned long Tianlhash(char *Url)unsigned long ulHashValue=0;int iLength=strlen(Url);if(!iLength)return 0;if(iLength=256)ulHashValue=16777216*(iLength-1);elseulHashValue=4278190080; int i; unsigned char ucChar;if(iLength=96)for(i=1;i=iLength;i+)ucChar=Urli-1;if(ucChar=A) ucChar=ucChar+32; ulHashValue+=(3*i*ucChar*ucChar+5*i*ucChar+7*i+11*ucChar)%16777216;elsefor(i=1;i=96;i+)ucChar=Urli+iLength-96-1;if(ucChar=A) ucChar=ucChar+32; ulHashValue+=(3*i*ucChar*ucChar+5*i*ucChar+7*i+11*ucChar)%16777216;return ulHashValue; 第二个是在许多文献中推荐的对字符串哈希效果很好的ELFhash函数,取自文献5,源于UNIX System V,号称实际生活哈希函数中的典型魔术.int ELFhash(char* url,int size)unsigned int h=0;while (*url)h=(h24;h&=g;return h%size;第三个和第四个是在文献6中推荐使用的对URL哈希效果很好的HfIp函数和hf函数,一直用在天网搜索引擎中.unsigned int HfIp(char* url,int size)unsigned int n=0;char* b=(char*)&n;for (int i=0;istrlen(url);i+)bi%4=urli;return n%size;int _hf(char* url,int size)int result=0; char* ptr=url;int c;for (int i=1; c=*ptr+; i+)result += c*3*i;if (result0)result = -result;return result%size;第五个是来自文献7的一个经验字符串函数Strhash.unsigned int Strhash(char *str) register unsigned int h; register unsigned char *p; for(h=0, p = (unsigned char *)str; *p ; p+) h = 31 * h + *p; return h; 2.4 实验结果2.4.1 一阶哈希我们以天网搜索引擎搜集的19993890个不同的URL序列为实验数据源,用上述五个函数分别实验,考察在相同的URL序列输入情况下,不同函数的冲突率.以50万URL序列为间隔,以N = 50万,100万,19993890个URL为输入执行函数,统计得到发生哈希值冲突的次数.由公式（1）,我们可得到各个函数的哈希冲突率.测试结果如图1所示,其中横轴表示输入的URL序列数目,纵轴表示各个函数的哈希冲突率.Fig.1 Collision ration comparison图1 冲突率比较由于hf的冲突率要远远大于其它四个函数,图1中其它四个函数的性能比较不明显.为了更好的比较各个函数的性能,我们仅比较函数Strhash、Tianlhash、ELFhash和HfIp.测试结果如图2所示,其中横轴表示输入的URL序列数目,纵轴表示各个函数的哈希冲突率.Fig.2 Collision ration comparison 图2 冲突率比较2.4.2 二阶哈希再哈希法8是指 (2) RHi 均是不同的哈希函数.即在同义词产生地址冲突时计算另一个哈希函数地址,直到冲突不再发生.这种方法不易产生聚集,但增加了计算的时间. 这里,我们比较了二阶哈希.针对上面介绍的五个函数,分别选择某个函数作为一阶哈希,当发生一阶哈希冲突时,再分别选用其它四个函数做二阶哈希测试.当二阶哈希结果冲突时,我们认为发生了二阶哈希冲突.以天网搜索引擎采集的19993890个不同的URL序列为输入源,统计得到发生二阶哈希值冲突的次数.由公式（1）,我们可得到各个函数的二阶哈希冲突率.测试结果如表1所示,其中,纵坐标函数为一阶,横坐标函数为二阶.StrhashTianlhashELFhashHfIphfStrhash7.1229E-100000Tianlhash09.76667E-092.19134E-124.77292E-121.77108E-12ELFhash03.18194E-121.44802E-075.94323E-102.25138E-13HfIp01.87915E-111.75373E-091.4854E-072.17633E-12hf1.50092E-147.71096E-103.17294E-111.97366E-106.79243E-06Table 1 Second hashing collision ration comparison表1 二阶哈希冲突率比较3 实验的结论观察图1和图2,我们有：l 随着输入URL序列数目的增加,各函数的冲突率随之减少.l hf的性能表现最差.而Strhash的性能要优于Tianlhash；Tianlhash的性能要优于ELFhash；ELFhash的性能要优于HfIp.l Tianlhash和Strhash的哈希冲突率比较接近.这两个函数的冲突率比较低,且非常稳定.对比在文献6中得到的结论：比较ELFhash、HfIp和hf,对于URL的哈希,（1）无论出于信息查询还是负载平衡的需求,HfIp都是很可靠的,可以首选使用；（2）Hf在有些情况下对负载平衡很好,但它对槽数的敏感性是一个值得注意的缺陷,有时可能效果很不好,需要小心；（3）不推荐使用ELFhash.这里,针对与文献6相同的URL数据源,在Web信息采集的测试中,我们发现Strhash和Tianlhash的测试性能要优于HfIp、hf和ELFhash,且性能非常稳定,值得推荐.并且,ELFhash的测试性能要优于于HfIp和hf.观察表1,我们有：l 各函数的二阶哈希冲突率已经非常低了,远低于一阶哈希的冲突率.l 表中对角线上的数值表示一阶哈希和二阶哈希采用的是同一哈希函数,其结果和采用一阶哈希的结果相同.l Strhash作为一阶哈希函数的性能非常理想.在我们天罗Web信息采集系统中,原来采用的是一阶哈希,采用的哈希函数是Tianlhash,所有的操作都是基于MySQL数据库的.基于上面的测试,我们在天罗Web信息采集系统中采用了二阶哈希.一阶采用的是Strhash,二阶采用的是Tianlhash.首先我们假定二阶哈希值相等,URL就一定相等.由于二阶哈希的冲突率是非常低的,我们认为这样的处理是合适的.若一阶Strhash哈希值不等,则采集该网页；否则再比较二阶Tianlhash哈希值是否相等.若二阶Tianlhash哈希值不等,则采集该网页；否则认为该网页已经采集过了.改进过后的天罗Web信息采集系统,占用几兆的内存空间,大大提高了采集速度,并降低了数据库的负荷.致谢 感谢北大天网免费提供了URL数据源,燕穹产品号YQ-URLLIST-2002-03.感谢周昭涛对实验实现的帮助. 参考文献1 Google. .2 Junghoo Cho, Hector Garcia-Moli