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

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

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

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

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

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

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

二、預(yù)取的分類(lèi)

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn):

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

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

作者簡(jiǎn)介:

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