淺析網頁中ＷＥＢ預取的特點及方法

許　崇　陶　寧　徐　力　劉冬莉　趙升彬

[摘要]介紹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-),女,漢族,本科學歷,助理工程師,就職于沈陽建筑大學。