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

[摘要]介紹WEB預(yù)取的分類和WEB預(yù)取采用的主要算法,并對比總結(jié)三種預(yù)取方法的優(yōu)缺點。WEB預(yù)取算法可分為基于歷史的預(yù)取、基于鏈接的預(yù)取和基于內(nèi)容的預(yù)取,三種預(yù)取方法中以網(wǎng)頁內(nèi)容為基礎(chǔ)的預(yù)取算法的命中率最高。

[關(guān)鍵詞]WEB預(yù)取 技術(shù)分析 預(yù)取算法

中圖分類號:TP3文獻(xiàn)標(biāo)識碼:A文章編號:1671-7597(2009)0920085-01

一、預(yù)取技術(shù)研究的可行性

Web的整體性能由構(gòu)成Web的各個構(gòu)件的性能確定:即客戶、服務(wù)器、代理、網(wǎng)絡(luò)、通信協(xié)議等。緩存技術(shù)已經(jīng)應(yīng)用于提高Web的性能,由于緩存的存在,能夠以更快的速度獲取經(jīng)常訪問的文件,因此能夠減少等待時間。緩存技術(shù)被認(rèn)為是減輕服務(wù)器負(fù)載、減少網(wǎng)絡(luò)擁塞、降低客戶訪問延遲的有效途徑之一。研究表明:不管采用何種緩存方案,Cache命中率大約只有30%～50%,作用有限。所以在Web研究中引入了預(yù)取(prefetching)或預(yù)推(pre-push)方法。

預(yù)取技術(shù)不但利用客戶訪問的時間局部性(Temporal Locality)原理,更主要是利用客戶訪問的空間局部性原理。Web客戶訪問時間局部性和空間局部性的客觀存在,為預(yù)取技術(shù)研究提供了直接依據(jù)。體現(xiàn)兩個方面:一是群體客戶訪問內(nèi)容上的局部性;二是同一個客戶在同一網(wǎng)站連續(xù)訪問的頁面往往具有較緊密的鏈接關(guān)系。

二、預(yù)取的分類

預(yù)取技術(shù)可以分為兩大類:透明預(yù)取技術(shù)和非透明預(yù)取技術(shù)。Web預(yù)取必須在高速緩存上實現(xiàn),而Web環(huán)境下的高速緩存存在于客戶端、代理服務(wù)器端和服務(wù)器端。在服務(wù)器、代理、客戶三者組成的簡化結(jié)構(gòu)中[2],有三種預(yù)取方式:客戶與服務(wù)器之間、客戶與代理之間、代理與服務(wù)器之間。

(一)客戶(瀏覽器)端預(yù)取?？蛻舳说念A(yù)取是步開展最早、研究成果最多的一個領(lǐng)域。最初的客戶端預(yù)取一般通過修改瀏覽器代碼或在瀏覽器中嵌入一插件程序來實現(xiàn)。后來,也有使用專門的瀏覽器軟件,或者在瀏覽器上運行一個具有預(yù)取功能的智能代理軟件或加速軟件,從而達(dá)到為網(wǎng)絡(luò)加速的目的?？蛻舳丝梢詮亩鄠€服務(wù)器進行預(yù)取,但它的服務(wù)對象僅是單用戶,所以實現(xiàn)起來較容易,可以運行得很快;另外,預(yù)取命中時,因為用戶請求的對象就放在本地,所以幾乎沒有時延。

(二)代理服務(wù)器端預(yù)取。代理服務(wù)器位于Internet網(wǎng)絡(luò)基礎(chǔ)架構(gòu)的中間層,代理服務(wù)器端預(yù)取的優(yōu)點是它可以從多個服務(wù)器中預(yù)取信息,而這些信息又可以為一個局域網(wǎng)內(nèi)的所有用戶使用。但是,同客戶端預(yù)取一樣,要維護代理服務(wù)器端高速緩存的一致性,同樣需要消耗網(wǎng)絡(luò)帶寬,增加服務(wù)器的工作負(fù)擔(dān),并月這種代價有時是巨大的。

(三)服務(wù)器端預(yù)取。服務(wù)器端的預(yù)取實際上就是位于服務(wù)器前面的反向代理服務(wù)器上的預(yù)取,很少指原始服務(wù)器本機上的預(yù)取。反向代理上的預(yù)取可以緩解原始服務(wù)器的負(fù)載。但從用戶的角度來看,它就是服務(wù)器端的預(yù)取。服務(wù)器端的預(yù)取不會增加網(wǎng)絡(luò)帶寬,因為它預(yù)取時沒有向Internet上發(fā)送任何信息;而且在服務(wù)器端維護高速緩存的一致性也比較容易。1.統(tǒng)計概率模型。Azer提出基于概率模型的預(yù)取方法。根據(jù)服務(wù)器Log數(shù)據(jù),服務(wù)器計算出在一定時間間隔內(nèi),網(wǎng)頁間被連續(xù)訪問的概率,并建立條件概率矩陣,以此,服務(wù)器預(yù)測用戶的訪問請求。這種模型多數(shù)建立在用戶訪問序列中各網(wǎng)頁的時序關(guān)系基礎(chǔ)上。典型的統(tǒng)計概率模型就是關(guān)系圖DG(Dependency Graph)。2.PPM(Prediction by Partial Match)模型。PPM模型利用訪問序列的前后相關(guān)性,采用高階的馬爾可夫預(yù)測鏈來提高預(yù)測的準(zhǔn)確性。

三、預(yù)取算法分析

預(yù)取算法是Web預(yù)取的核心,準(zhǔn)確的或比較準(zhǔn)確的預(yù)測算法將能夠明顯改善緩存的性能。如何減少用戶上網(wǎng)瀏覽時所感覺到的時間延遲是Web研究中的一個重要方而?，F(xiàn)有的預(yù)取方法大致有以下3種:基于歷史(History Based)的預(yù)取、基于鏈接(link Based)的預(yù)取和基于興趣(interest Based)的預(yù)取。

(一)基于歷史(History Based)的預(yù)取。基于歷史的預(yù)取利用了相鄰請求之間的時序相關(guān)性。這類方法先根據(jù)用戶訪問的歷史記錄建立一階或高階Markov模型,再根據(jù)用戶的當(dāng)前瀏覽路徑在該模型中尋找匹配項集合,最后以一該集合中概率最高的那個請求作為預(yù)取對象?；谠L問歷史的預(yù)測方法通過研究用戶的Web訪問歷史,建立預(yù)測模型。根據(jù)預(yù)測模型所使用的歷史信息的不同,訪問歷史的預(yù)測模型可分為三類:基于某個客戶(Web客戶)訪問歷史的預(yù)測模型;基于某個群體(Web代理)訪問歷史的預(yù)測模型;基于條件概率的預(yù)測。

(二)基于鏈接(link Based)的預(yù)取?；阪溄拥念A(yù)取利用了相鄰請求之間的結(jié)構(gòu)相關(guān)性。這類方法將用戶當(dāng)前瀏覽的網(wǎng)頁上的全部或部分鏈接作為預(yù)取對象。但是,如果當(dāng)前網(wǎng)頁中的超鏈接數(shù)太多時,往往難以決定應(yīng)該預(yù)取哪些網(wǎng)頁更合適。從用戶角度考慮,一種好的預(yù)取方法應(yīng)當(dāng)符合預(yù)測準(zhǔn)確和運行決策速度快的要求。

(三)基于興趣(interest based)的預(yù)取。該類預(yù)取模型通過分詞技術(shù)對客戶的歷史訪問信息進行處理,建立客戶興趣知識庫,當(dāng)對客戶的當(dāng)前請求進行預(yù)取時,對當(dāng)前請求頁面上的鏈接的文本進行分詞,利用興趣知識庫中的詞條與當(dāng)前請求頁面上鏈接的詞條的匹配度或關(guān)聯(lián)度來確定對哪個鏈接頁面進行預(yù)取。

與其它的頂取方法相比,基于Markov模型的預(yù)取能夠更加準(zhǔn)確地反映用戶的訪問模式,從而取得更好的預(yù)取性能和效果。如果在代理服務(wù)器端實現(xiàn)基于Markov模型的預(yù)取,無疑會取得最佳的效果?；跉v史網(wǎng)頁的預(yù)取只能預(yù)取用戶訪問過的頁面,而且需要海量分析用戶的歷史數(shù)據(jù);基于鏈接的預(yù)取將用戶當(dāng)前瀏覽的網(wǎng)頁上的全部或部分鏈接作為預(yù)取對象,是一種海量預(yù)取,這對于目前擁擠的網(wǎng)絡(luò)是不可取的;基于興趣的預(yù)取不能做到實時的、自適應(yīng)的預(yù)取;基于內(nèi)容的預(yù)取方法命中率較高,而超鏈和超鏈文本時網(wǎng)頁內(nèi)容的重要組成部分,本文研究的基于網(wǎng)頁結(jié)構(gòu)相關(guān)性預(yù)取方法綜合基于歷史的預(yù)取和基于鏈接的預(yù)取的優(yōu)點,分析用戶的訪問日志得到用戶的會話集,基于會話集,利用隱馬爾可夫模型分析超鏈的語義,找出下一個觀察序列的概率,觀察序列的概率越大,下一步被訪問的權(quán)值也越大,由此確定預(yù)取對象。這樣既克服了基于歷史的預(yù)取要海量分析歷史網(wǎng)頁的缺點,又克服了基于鏈接預(yù)取的全部預(yù)取的缺點。所以預(yù)取準(zhǔn)確性相對較高。

參考文獻(xiàn):

[1]班志杰、古志民、金瑜,Web預(yù)取技術(shù)綜述[J].計算機研究與發(fā)展,2009,02.

[2]牛偉、張延園,Web預(yù)取技術(shù)的研究[J].微計算機應(yīng)用,2008,07.

作者簡介:

許崇(1982-),女,漢族,本科學(xué)歷,助理工程師,就職于沈陽建筑大學(xué)。