资源描述：
《we 信息采集中的哈希函数比较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Web信息采集中的哈希函数比较本课题得到973项目“大规模文本内容计算”(2004CB3181096)基金资助。吴丽辉1,2,白硕1,张刚1,2,张凯1(1.中国科学院计算技术研究所软件研究室，北京100080；2.中国科学院研究生院，北京100039)Email:wulh@ict.ac.cnPhn:010-88449181-717摘要:在Web信息采集的过程中,需要判断待采页面是否在已采页面集合中.为了实现快速采集,采用哈希函数来实现.基于一个含有2000多万个URL的序列,通过大规模的实验性评测,比较了函数Tianlhash、ELFhash
2、、HfIp、hf和Strhash的一阶和二阶哈希冲突率.实验结果表明,Strhash和Tianlhash的性能较佳,值得推荐.并且,ELFhash的测试性能要优于HfIp和hf.采用二阶哈希后的天罗Web信息采集系统,占用几兆的内存空间,大大提高了采集速度,并降低了数据库的负荷.关键词:Web信息采集;哈希函数;URL中图法分类号:TP314 文献标识码:AHashingComparisoninWebCrawlingWuLihui1,2,BaiShuo1,ZhangGang1,2+,ZhangKai(1.SoftwareDivision,I
3、nstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100080)(2.GraduateSchooloftheChineseAcademyofSciences,Beijing100039)Abstract:DuringthecourseofWebcrawling,itisneededtojudgeifthecomingURLsareinthecollectionofcrawledpages.Inordertoachievefastcrawling,hashingisadop
4、ted.Throughalargescaleexperiment,fivehashfunctionsarecomparedinthispaper.ThefindingisthatStrhashandTianlhashfunctionsarebetterandthusrecommended.And,ELFhashfunctionisbetterthanHfIpandhf.Thecrawlingspeedisfastadvancedafterusingsecond-hashinTianluoWebcrawlingsystem,andthedatab
5、aseloadisdepressed.Keywords:Webcrawling;hashing;URL1引言Internet尤其是WWW的飞速发展,给人们带来了前所未有的信息共享与交流.网络已发展成为我们经济、社会、文化、教育以及娱乐等几乎各个方面的重要组成部分.到2004年11月,Google搜索引擎索引的网页数已经超过80亿[1].随着互联网的迅速发展,各项基于Web的服务也日益繁荣起来.作为这些信息服务的基础和重要组成部分,基于Web的信息采集正应用于搜索引擎、站点结构分析、页面有效性分析、Web图进化、用户兴趣挖掘以及个性化信息获取等多
6、种应用和研究中.Web信息采集[2],主要是指通过Web页面之间的链接关系,从Web上自动获取页面信息,并且随着链接不断向所需要的Web页面扩展的过程.粗略的说,它主要是指这样一个程序,从一个初始的URL集出发,将这些URL全部放入到一个有序的待采集队列里.而采集器从这个队列里按顺序取出URL,通过Web协议,获取URL所指向的页面,然后从这些已获取的页面中提取出新的URL,并将他们继续放入到待采队列里,然后重复上面的过程,直到采集器根据自己的策略停止采集.在Web信息采集的过程中,为了实现快速采集,需要记住已经采集过的页面（记做集合visit
7、ed-urls）.采集中凡遇到一个页面,需要用它和visited-urls对比,判断该页面的URL是否已在visited-urls中.若在其中,则表示该网页已采集；否则将它放入visited-urls,继续沿其含有的URL向下采集.显然,将visited-urls组织成一个哈希表是很自然的,哈希的对象是用于访问网页的URL,即形如“http://www.ict.ac.cn”之类的字符串[3].为了设计高效的URL哈希算法,测试不同的哈希函数对相同的URL列表的冲突率.1实验的设计和执行1.1实验评价标准为了比较不同的哈希函数,需要有和应用背景相
8、关的实验评价标准.假设我们已经有了全国网页的集合,记做P={p1,p2,p3,…}.对应地,有所有URL的集合,记做URL={url1,url2,ur
