基于Hash算法实现搜索引擎中重复WEB页面的消除

1、 邮局订阅号:82-946360元/年技术创新软件时空PLC 技术应用200例您的论文得到两院院士关注杨海东:硕士生基于Hash 算法实现搜索引擎中重复WEB 页面的消除Elim inated Duplicate Search WEB pages with Hash algorithm(南京信息工程大学杨海东叶小岭张颖超Yang,Haidong Ye ,Xiaoling Zhang,Yingchao摘要:搜索引擎已经成为互联网用户进入网络的一个重要入口。但目前搜索引擎的结果还存在着许多有待改进的地方。本文从搜索引擎返回结果中存在的重复页面入手,解决如何消除重复页面,并对其将来的发展进行了进一步

2、探讨。关键词:网络蜘蛛;搜索引擎;散列函数;WEB 中图分类号:TP394文献标识码:AAbstract:As an important enterance to Internet,search Engine has also existed some shortcoming in gernal.This article discussedhow to eliminate duplicate web pages with Hash algorithm and described its future.Key words:WEB Crawl,Search Engine,HASH,WEB文章编号:

3、1008-0570(200609-3-0299-031引言Internet 已经成为一所巨大的信息资源宝库。但是如何使用这个包含了一百多亿个WEB 页面的宝库,成为互联网用户面临的一个难题,搜索引擎的出现与发展解决了这一问题。经过十几年的发展,搜索引擎在收集页面的数量及质量都有了很大提高,已经成为众多互联网用户进入网络的一个重要入口。搜索引擎技术也成为最具活力和最有发展前途的技术之一。但同时我们也要注意到,搜索引擎也存在下列有待发展的地方:(1检索的结果集中还存在相当数量的重复页面。这种重复包括两种形式:一是同一站点出于保护自身的原因,在不同的域注册了相同主机名的域名,实际上是指向同一IP 地

4、址。二是大型的网站为了方便不同地区的用户访问,或者缓解大量用户对同一服务器访问造成的压力,在不同的地理位置安装物理服务器,形成镜像站点。(2收集页面的数量有待提高。目前使用量最大的搜索引擎google 收集了40多亿WEB 页面,Yahoo 也称收集了45亿页面。绝对数字虽然庞大,但这在互联网上120多亿的页面中只占40%不到。需要开发更强有力的网络蜘蛛程序,基于链接进行网络遍历的方式还需要改进甚至革新。(3排序的结果还不能让用户非常满意。更合理的排序方法一直是搜索引擎网站努力改进的方向。影响排序结果的因素有两个:排序技术与商业因素。排序技术上,目前传统的排序算法如PageRank 、HITS

5、 等算法都或多或少地存在一些缺陷,新的排序算法和主题相关性检索正在进入到搜索服务领域。由于现在搜索引擎是免费提供给用户使用,要依靠提供广告服务或竞价排名,以维持网站的正常运行,这样在结果页面中会出现相关的广告内容或者购买竞价排名企业的网站。上述(2、(3点,需要有新的技术出现,第一点可以在现有基础上进行改进。本文将讨论基于Hash 算法消除在搜索引擎数据库中的重复链接。2散列(Hash 算法Hash 算法,在中文中又叫散列算法、杂凑算法等,是将任意长度的字符串作为输入生成,经过n 次迭代运算后生成固定长度的字符串的一种算法。Hash 算法是现代密码学的核心,在数字签名、身份认证和口令鉴别等多个

6、安全领域都有应用。在本文中,Hash 算法用来生成每个网页的识别序列,在生成的序列唯一性方面要求很高,但对于安全性考虑较少,因而采用单向的Hash 算法。为了节省空间,同时又满足系统的要求,Hash 结果的位数取128bit 。统计结果表明:如hash(m的长度为128位(bit时,则任意两个分别为M1,M2的输入报文具有完全相同的h(m的概率为10-24,即近于零的重复概率。它较人类指纹的重复概率10-19还要小5个数量级。而当我们取hash(m为384(bit乃至1024(bit时,则更是不大可能重复了。目前Internet 中约有WEB 页130亿个,超级链接约600亿(10111024

7、。因而128bit 的Hash 序列位数在现在及未来的一段时间内完全可以满足要求。299-技术创新中文核心期刊微计算机信息(管控一体化2006年第22卷第9-3期 360元/年邮局订阅号:82-946现场总线技术应用200例软件时空2.1单向Hash 函数的定义及性质映射对所有的,容易计算,但其逆过程,给定要求出在计算上是困难的,该函数称为单向函数。单向的Hash 函数除了具有Hash 函数动态输入、固定输出、碰撞机率低的特点外,还具有下列三个特性:1不可逆性,已知,经过数次非线性运算和迭代运算后,求计算困难。虽然最新文献表明,Hash 算法已经可以进行逆运算求出m 值,但本文使用Hash 函

8、数的目的是为了使序列具有唯一的值,对其安全性不作要求;2防伪造性,已知,求使计算困难,这一特性被应用在数字签名等安全应用中;3初值敏感性,中m 的每一字符都与的每一bit 相关,初值每个字符的变动,都将对结果值c 产生明显影响。2.2Hash 值的构造Hash 函数的构造方法在很多文章和书籍里都有介绍。以MD5算法为例,它以512位作为分组(不满足的条件的需要对信息对行扩充,使得INFO mod 512=448来处理信息,每一分组又分32个子分组,经过四次主循环进行非线性函数运算,加快其雪崩效应,最后得到固定长度的128位Hash 序列。用Hash 函数可以生成MD5加密序列、SHA 序列等多

9、种形式,对于本文来说,序列的作用是进行唯一性验证。因此采用常用的MD5算法生成定长且唯一的Hash 序列,本文中所有的Hash 序列均为MD5序列。2.3初值敏感性验证对于上百亿个WEB 页面来说,为了能唯一标识一个页面,两个URL 有细微的差别,其Hash 序列都应该有大的变化,而且不同的URL 生成的序列应该有极低的碰撞机率。下面构造三个相似的URL 序列,利用Hash 函数将其转化成MD5序列,列表如下:表1三个相似URL Hash 序列的对比表1表明:对于单向散列函数,初始值微小的变化会使Hash 结果以很大的幅度变化,同时128位(32个十六制位不同的排列组合能够产生大的空间来容纳碰

10、撞的产生。3网络蜘蛛对重复记录的消除对于普通的页面重复,解决的方法主要依靠网络蜘蛛的爬行算法在遍历网络结点时解决。这种解决方法类似于数据结构的图的遍历问题,但WEB 中存在着不同于理论上图的问题,主要体现在两个方面,一是同一个IP 地址对应着不同的域名,如有些大型商业网站为了保护自己的知识产权,会在不同的域中注册相同或相似的域名,这样在处理时,网络蜘蛛会把URL 形式不同,但却指向同一主机的路径和文件的链接当成两个不同的页面进行处理,在存在上百亿页面的Internet 上会造成大量的重复。二是把一个网站的镜像(即同一个网站为了提供给不同地区的用户快速访问,分别就近设立了内容完全相同但IP 不同

11、的站点当成不同的网站进行访问,也造成搜索引擎返回页面资源的极大浪费。因此应当设计一个算法或结构以避免出现上述两种情况。3.1网络中异名同址页面结点的消除对异名同址的URL 进行唯一性标识。设有下面URL (以南京信息工程大学为例:(2与前两个URL 也是等效的。上述三个URL 实际上是指向同一链接,在搜索引擎的数据库中没有必要放置三条记录来标识它们。对于这种情况,将域名转化成IP 序列就可以得出唯一的ID 值,得到一个序列:“http:/+IP 地址+路径”D41D8CD98F00B204E9800998ECF8427E (3式经过转换也得到同样结果。3.2对同名异址的网页进行唯一性标识同名(

12、或近似异址的在情况在Interne 中表现为镜像站点的分布。在许多文献中将镜像站点归为不同站点。但在实际应用中,对于镜像站点的访问只要其中一个就行了。对3.1中的例子,需要将IP 转化为域名,得到形如“http:/+域名+路径”00F4CC7599310F795FB4B19B6A13CCA9这样在存储URL 的数据库结构中就增加两个字段:IP_ID 和Name_ID ,对应着IP 和域名的序列,每搜索到一个URL ,都将域名部分和IP 部分进行相互转化,与存放在两个字段中的值进行比较。如果IP 地址相同,并不是简单地丢弃,而是将URL 以增量的方式添加在存放URL 的字段后,相同域名的URL

13、可以直300- 邮局订阅号:82-946360元/年技术创新软件时空PLC 技术应用200例您的论文得到两院院士关注接丢弃。在存储介质容量剧增且价格下降的今天,这种以空间换效率的做法是可以接受的。这两个序列通过一定的算法在遍历网络时生成,每个页面的ID 长度固定且必须唯一。bbs2. 的识别,需要依赖于网络蜘蛛的智能性,即判断URL 的相似程度及其父URL,如果URL 的相似度和内容的相似度都高于设定的阈值,则认为这些站点互为镜像。3.3多线程网络蜘蛛HASH 函数处理单个线程的网络蜘蛛效率很低,在实际应用中很少。为了能快速地收集URL 并进行处理,网络蜘蛛往往采用多线程技术。这就需要线程之间

14、相互协调,实现负载的均衡,同时每个线程遵循上述单线程的规则。一个或几个线程负责一个域的搜索,如让10个线程负责 域的搜索。在搜索的过程中如果链接指向某线程负责域外的其它域,则将任务交给相关线程ID 。这样分配的另外一个好处就是:线程i 在写入数据时不需要锁定整个数据库,只需要锁定部分区域就行了,其它线程可以正常工作。每个线程在将数据写入数据库前,都要检查该值是否已经存在于数据库中。在大型商用搜索引擎中不但使用多线程技术,而且还需要多台计算机并行地抓取WEB 页面,这就要求除了选性能好的Hash 函数外,还要考虑负载的均衡性,这涉及到分布式系统的设计,此处不作论述。4结束语在Internet 还

15、存在着这样一种重复链接:由于相互引用而造成的内容上的重复。它们属于不同的网站,页面的主体部分基本相同。这种重复虽然一定程度上浪费了网络资源,但它还有存在的必要性,因为目前的网络还不稳定,经常有HTTP404(Not found 错误发生,或者有些页面下载过慢,多个相似页面资源可以互相补充,将资源提供给用户。因此这类重复暂时不进行去重操作。搜索引擎经过几代的发展,已经在向更高的智能化迈进,但是在收集页面数量、结果的排序及个性化方面还存在若干有待革新改进的地方,搜索引擎市场的竞争也日趋激烈,搜索引擎的发展还有很长的一段路要走。本文的创新之处在于:利用Hash 结果的固定长度和极低的碰撞机率,提出用

16、IP 地址的Hash 值和URL 的Hash 值来进行页面资源唯一性的确定,并给出了实例进行说明。这种方法在一定规模的模拟系统中取得了良好的效果。参考文献:3Chau,M.,Zeng,D.,and Chen,H.:Personalized Spiders for Web Search and Analysis.In Proceedings of the 1st ACM-IEEE Joint Conference on Digital Libraries,Roanoke,Virginia,USA,Jun 2001.4周先存,侯整风.一种基于ELGaml 签名和零知识证明的身份认证方案.微计算机信

17、息,2004.5:1146闫宏飞,李晓明.关于中国Web 的大小、形状和结构.计算机研究与发展,2002.8:63-727张瀚,王秀峰等.基于时空混沌的单向Hash 函数构造.物理学报,2005.9:40-459李晓明,凤旺森.两种对URL 的散列效果很好的函数.软件学报,2004.2:179-185:48-49作者简介:杨海东(1973-,男,汉族,硕士生,江苏淮安人,主要从事网络算法与技术研究;叶小岭(1964-,女,满族,副教授,硕士生导师,主要从事网络系统安全、研究领域为优化方法与最优控制;张颖超(1960-,男,汉族,江苏徐州人,教授,硕士生导师,研究领域为系统控制和仿真、网络控制技术等。Biography: