浅析网页中ＷＥＢ预取的特点及方法

许　崇　陶　宁　徐　力　刘冬莉　赵升彬

[摘要]介绍WEB预取的分类和WEB预取采用的主要算法,并对比总结三种预取方法的优缺点。WEB预取算法可分为基于历史的预取、基于链接的预取和基于内容的预取,三种预取方法中以网页内容为基础的预取算法的命中率最高。

[关键词]WEB预取 技术分析 预取算法

中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)0920085-01

一、预取技术研究的可行性

Web的整体性能由构成Web的各个构件的性能确定:即客户、服务器、代理、网络、通信协议等。缓存技术已经应用于提高Web的性能,由于缓存的存在,能够以更快的速度获取经常访问的文件,因此能够减少等待时间。缓存技术被认为是减轻服务器负载、减少网络拥塞、降低客户访问延迟的有效途径之一。研究表明:不管采用何种缓存方案,Cache命中率大约只有30%～50%,作用有限。所以在Web研究中引入了预取(prefetching)或预推(pre-push)方法。

预取技术不但利用客户访问的时间局部性(Temporal Locality)原理,更主要是利用客户访问的空间局部性原理。Web客户访问时间局部性和空间局部性的客观存在,为预取技术研究提供了直接依据。体现两个方面:一是群体客户访问内容上的局部性;二是同一个客户在同一网站连续访问的页面往往具有较紧密的链接关系。

二、预取的分类

预取技术可以分为两大类:透明预取技术和非透明预取技术。Web预取必须在高速缓存上实现,而Web环境下的高速缓存存在于客户端、代理服务器端和服务器端。在服务器、代理、客户三者组成的简化结构中[2],有三种预取方式:客户与服务器之间、客户与代理之间、代理与服务器之间。

(一)客户(浏览器)端预取。客户端的预取是步开展最早、研究成果最多的一个领域。最初的客户端预取一般通过修改浏览器代码或在浏览器中嵌入一插件程序来实现。后来,也有使用专门的浏览器软件,或者在浏览器上运行一个具有预取功能的智能代理软件或加速软件,从而达到为网络加速的目的。客户端可以从多个服务器进行预取,但它的服务对象仅是单用户,所以实现起来较容易,可以运行得很快;另外,预取命中时,因为用户请求的对象就放在本地,所以几乎没有时延。

(二)代理服务器端预取。代理服务器位于Internet网络基础架构的中间层,代理服务器端预取的优点是它可以从多个服务器中预取信息,而这些信息又可以为一个局域网内的所有用户使用。但是,同客户端预取一样,要维护代理服务器端高速缓存的一致性,同样需要消耗网络带宽,增加服务器的工作负担,并月这种代价有时是巨大的。

(三)服务器端预取。服务器端的预取实际上就是位于服务器前面的反向代理服务器上的预取,很少指原始服务器本机上的预取。反向代理上的预取可以缓解原始服务器的负载。但从用户的角度来看,它就是服务器端的预取。服务器端的预取不会增加网络带宽,因为它预取时没有向Internet上发送任何信息;而且在服务器端维护高速缓存的一致性也比较容易。1.统计概率模型。Azer提出基于概率模型的预取方法。根据服务器Log数据,服务器计算出在一定时间间隔内,网页间被连续访问的概率,并建立条件概率矩阵,以此,服务器预测用户的访问请求。这种模型多数建立在用户访问序列中各网页的时序关系基础上。典型的统计概率模型就是关系图DG(Dependency Graph)。2.PPM(Prediction by Partial Match)模型。PPM模型利用访问序列的前后相关性,采用高阶的马尔可夫预测链来提高预测的准确性。

三、预取算法分析

预取算法是Web预取的核心,准确的或比较准确的预测算法将能够明显改善缓存的性能。如何减少用户上网浏览时所感觉到的时间延迟是Web研究中的一个重要方而。现有的预取方法大致有以下3种:基于历史(History Based)的预取、基于链接(link Based)的预取和基于兴趣(interest Based)的预取。

(一)基于历史(History Based)的预取。基于历史的预取利用了相邻请求之间的时序相关性。这类方法先根据用户访问的历史记录建立一阶或高阶Markov模型,再根据用户的当前浏览路径在该模型中寻找匹配项集合,最后以一该集合中概率最高的那个请求作为预取对象。基于访问历史的预测方法通过研究用户的Web访问历史,建立预测模型。根据预测模型所使用的历史信息的不同,访问历史的预测模型可分为三类:基于某个客户(Web客户)访问历史的预测模型;基于某个群体(Web代理)访问历史的预测模型;基于条件概率的预测。

(二)基于链接(link Based)的预取。基于链接的预取利用了相邻请求之间的结构相关性。这类方法将用户当前浏览的网页上的全部或部分链接作为预取对象。但是,如果当前网页中的超链接数太多时,往往难以决定应该预取哪些网页更合适。从用户角度考虑,一种好的预取方法应当符合预测准确和运行决策速度快的要求。

(三)基于兴趣(interest based)的预取。该类预取模型通过分词技术对客户的历史访问信息进行处理,建立客户兴趣知识库,当对客户的当前请求进行预取时,对当前请求页面上的链接的文本进行分词,利用兴趣知识库中的词条与当前请求页面上链接的词条的匹配度或关联度来确定对哪个链接页面进行预取。

与其它的顶取方法相比,基于Markov模型的预取能够更加准确地反映用户的访问模式,从而取得更好的预取性能和效果。如果在代理服务器端实现基于Markov模型的预取,无疑会取得最佳的效果。基于历史网页的预取只能预取用户访问过的页面,而且需要海量分析用户的历史数据;基于链接的预取将用户当前浏览的网页上的全部或部分链接作为预取对象,是一种海量预取,这对于目前拥挤的网络是不可取的;基于兴趣的预取不能做到实时的、自适应的预取;基于内容的预取方法命中率较高,而超链和超链文本时网页内容的重要组成部分,本文研究的基于网页结构相关性预取方法综合基于历史的预取和基于链接的预取的优点,分析用户的访问日志得到用户的会话集,基于会话集,利用隐马尔可夫模型分析超链的语义,找出下一个观察序列的概率,观察序列的概率越大,下一步被访问的权值也越大,由此确定预取对象。这样既克服了基于历史的预取要海量分析历史网页的缺点,又克服了基于链接预取的全部预取的缺点。所以预取准确性相对较高。

参考文献:

[1]班志杰、古志民、金瑜,Web预取技术综述[J].计算机研究与发展,2009,02.

[2]牛伟、张延园,Web预取技术的研究[J].微计算机应用,2008,07.

作者简介:

许崇(1982-),女,汉族,本科学历,助理工程师,就职于沈阳建筑大学。