Ｈｉｄｄｅｎ Ｗｅｂ信息獲取

摘要：如今Web上越來(lái)越多的信息可以通過(guò)查詢接口獲得，但為了獲取某Hidden Web站點(diǎn)的頁(yè)面，用戶不得不鍵入一系列的關(guān)鍵詞。由于沒(méi)有直接指向Hidden Web頁(yè)面的靜態(tài)鏈接，當(dāng)前大多搜索引擎不能發(fā)現(xiàn)和索引這些頁(yè)面。然而，研究表明，由Hidden Web站點(diǎn)提供的高質(zhì)量的信息對(duì)許多用戶來(lái)說(shuō)非常有價(jià)值。文章通過(guò)研究針對(duì)特定類型的表單，建立一個(gè)有效的Hidden Web爬蟲(chóng)，以便獲取Hidden Web后臺(tái)數(shù)據(jù)庫(kù)信息。

關(guān)鍵詞：Hidden Web；Hidden Web爬蟲(chóng)；靜態(tài)鏈接；搜索引擎；采樣策略

0 引言

網(wǎng)絡(luò)上大部分內(nèi)容是不能通過(guò)靜態(tài)鏈接獲取的，特別是大部分隱藏在搜索表單之后的頁(yè)面只有通過(guò)用戶鍵入一系列關(guān)鍵詞才可以獲得。這些頁(yè)面被稱為Hidden Web。由于當(dāng)前的搜索引擎不能索引到或不能在它們的返回結(jié)果中顯示這些頁(yè)面，因此對(duì)用戶來(lái)說(shuō)這部分頁(yè)面是隱藏的。Hidden Web最初由Dr．Jill Ellsworth于1994年提出，指那些由普通搜索引擎難以發(fā)現(xiàn)其信息內(nèi)容的Web頁(yè)面。2001年，Christ Sherman、GaryPrice對(duì)Hidden Web定義為：雖然通過(guò)互聯(lián)網(wǎng)可以獲取，但普通搜索引擎由于受技術(shù)限制而不能或不作索引的那些文本頁(yè)、文件或其它通常是高質(zhì)量、權(quán)威的信息。根據(jù)最近對(duì)HiddenWeb的調(diào)查文獻(xiàn)得到了如下有意義的發(fā)現(xiàn)：

(1)Hidden Web大約有307，000個(gè)站點(diǎn)，450，000個(gè)后臺(tái)數(shù)據(jù)庫(kù)和1，258，000個(gè)查詢接口。它仍在迅速增長(zhǎng)，從2000年到2004年，它增長(zhǎng)了3～7倍。

(2)Hidden Web內(nèi)容分布于多種不同的主題領(lǐng)域，電子商務(wù)是主要的驅(qū)動(dòng)力量，但非商業(yè)領(lǐng)域相對(duì)占更大比重。

(3)當(dāng)今的爬蟲(chóng)并非完全爬行不到Hidden Web后臺(tái)數(shù)據(jù)庫(kù)內(nèi)，一些主要的搜索引擎已經(jīng)覆蓋Hidden Web大約三分之一的內(nèi)容。然而，在覆蓋率上當(dāng)前搜索引擎存在技術(shù)上的本質(zhì)缺陷。

(4)Hidden Web中的后臺(tái)數(shù)據(jù)庫(kù)大多是結(jié)構(gòu)化的，其中結(jié)構(gòu)化的是非結(jié)構(gòu)化的3．4倍之多。

(5)雖然一些Hidden Web目錄服務(wù)已經(jīng)開(kāi)始索引Web數(shù)據(jù)庫(kù)，但是它們的覆蓋率比較小，僅為0．2％～15．6％。

(6)Web數(shù)據(jù)庫(kù)往往位于站點(diǎn)淺層，多達(dá)94％的Web數(shù)據(jù)庫(kù)可以在站點(diǎn)前3層發(fā)現(xiàn)。

可以看出Hidden Web中信息量要比Surface Web信息量多得多，同時(shí)由于Hidden Web頁(yè)面信息是由后臺(tái)數(shù)據(jù)庫(kù)動(dòng)態(tài)產(chǎn)生的，數(shù)據(jù)庫(kù)大多是結(jié)構(gòu)化的關(guān)系數(shù)據(jù)庫(kù)，因此信息的質(zhì)量比非結(jié)構(gòu)化的頁(yè)面要高。

本文以不含或含有少量的文本元素，其它類型元素都具有值的表單作為研究對(duì)象，提出了Hidden Web爬蟲(chóng)沒(méi)設(shè)計(jì)的—種框架。

1 Hidden Web爬蟲(chóng)

為實(shí)現(xiàn)自動(dòng)獲取Hidden Web頁(yè)面的任務(wù)，此爬蟲(chóng)必須能自動(dòng)尋找表單，填寫表單，然后獲取和識(shí)別結(jié)果頁(yè)面。HiddenWeb爬蟲(chóng)系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 Hidden Web爬蟲(chóng)系統(tǒng)框架

1．1尋找Hidden Web入口頁(yè)面

Web上存在多種多樣的表單，同時(shí)表單上含有各種各樣的元素，如單選按鈕、下拉列表框、文本框等，有些還是用戶自定義的，因此處理所有的表單是比較困難的。為此，需要先解析HTML頁(yè)面，獲取要研究的表單類型，同時(shí)從中抽取有用信息。本文要研究的是不含或含有少量的文本框元素，其它類型元素都具有默認(rèn)值的表單。這很容易通過(guò)解析HTML表單來(lái)完成，如可以使用標(biāo)記序列樹(shù)或DOM(文檔對(duì)象模型)來(lái)過(guò)濾出要研究的表單。

1．2自動(dòng)提交表單

當(dāng)搜索表單提供了每一表單元素所有可能的值時(shí)，直接的方法是對(duì)具有少量的文本框元素使用空串作為默認(rèn)值，窮盡表單其他元素所有可能值的組合來(lái)填寫表單，獲取后臺(tái)數(shù)據(jù)庫(kù)全部的數(shù)據(jù)。此方法存在兩個(gè)問(wèn)題：①處理過(guò)程非常耗時(shí)；②在窮盡所有可能值組合之前，也許已經(jīng)獲取了所有或大部分的后臺(tái)數(shù)據(jù)庫(kù)數(shù)據(jù)，從而出現(xiàn)了重復(fù)提交；③多個(gè)字段組合可能存在語(yǔ)義上的沖突。Hidden Web爬蟲(chóng)設(shè)計(jì)的目標(biāo)是使用最少的資源(如提交時(shí)間或次數(shù)等)獲取特定Hidden Web站點(diǎn)內(nèi)最大量的數(shù)據(jù)，然而不能保證對(duì)所有表單使用有限次的提交可以獲取后臺(tái)數(shù)據(jù)庫(kù)的全部數(shù)據(jù)，因此有必要再次發(fā)送查詢來(lái)確定是否已獲取了全部數(shù)據(jù)。本文提出一種兩階段采樣爬行策略以充分獲取Hidden Web數(shù)據(jù)，它分為如下兩個(gè)步驟：

(1)首先使用表單提供的默認(rèn)值來(lái)提交；

(2)然后對(duì)表單元素值組合進(jìn)行采樣以確定默認(rèn)值提交是否返回了后臺(tái)數(shù)據(jù)庫(kù)的所有數(shù)據(jù)，若返回了后臺(tái)數(shù)據(jù)庫(kù)所有或大部分?jǐn)?shù)據(jù)則可以結(jié)束提交過(guò)程。否則，在爬蟲(chóng)所具有資源限制范圍內(nèi)窮盡所有可能值的組合。

1．2．1采樣查詢后臺(tái)數(shù)據(jù)庫(kù)

下面介紹采樣階段以確定默認(rèn)值提交是否返回了后臺(tái)數(shù)據(jù)庫(kù)的全部數(shù)據(jù)。一種方法是從表單元素所有可能值的組合中隨機(jī)采樣來(lái)提交表單。然而隨機(jī)采樣提交不能覆蓋表單元素每種取值，造成所有可能值的不均勻使用，如表1所示。這里形式化定義表單的第i個(gè)元素為因子L_i。集合L₁，L₂，…，L_n是對(duì)應(yīng)于表單上具有有限值的所有元素，| L_i|表示第i個(gè)因子可能取值的個(gè)數(shù)，則表單元素所有可能值組合的個(gè)數(shù)為：

這里考慮了表單具有多個(gè)元素而勢(shì)很小的情況。其中「log₂N」的選擇參見(jiàn)文獻(xiàn)。

對(duì)表單元素所有可能值組合采樣C次后若沒(méi)有新的數(shù)據(jù)記錄返回則表明已經(jīng)獲取了所有數(shù)據(jù)。舉例來(lái)說(shuō)，假設(shè)一個(gè)含有兩個(gè)元素的表單，它們都具有有限的值域，每個(gè)元素可能取值個(gè)數(shù)為7和4，則上述N=28，C=6。

表1 隨機(jī)采樣

從表1中可以看到，對(duì)于元素A的可能值a₆和a₇，元素B的可能值b₃在采樣提交中一次都沒(méi)有使用，同時(shí)元素B的可能值b1在6次采樣提交中就使用了3次。這說(shuō)明使用隨機(jī)采樣來(lái)提交表單可能造成表單元素某些值可能過(guò)分使用，而漏用其它一些值的情況。解決這個(gè)問(wèn)題的一種方法是記錄采樣因子已經(jīng)使用的值的次數(shù)，擴(kuò)大采樣值的范圍，即“分層采樣”的方法。使用此方法采樣提交模式如表2所示。

表2 使用規(guī)則模式的“分層采樣”

表2使用了一個(gè)規(guī)則的模式“分層采樣”來(lái)覆蓋每個(gè)因子的所有可能值。根據(jù)上述規(guī)則下次將使用(a₇，b₄)來(lái)填寫表單元素。可以看到此方法覆蓋了元素B的所有可能值，這種規(guī)則的模式必然會(huì)對(duì)某些元素有所偏重。為了覆蓋所有元素的可能值，表3使用了一個(gè)隨機(jī)的“分層采樣”方法。

對(duì)上述處理含有兩個(gè)因子的表單的方法加以擴(kuò)展，可用于含有兩個(gè)以上元素的表單。

在C次采樣提交的過(guò)程中，系統(tǒng)處理返回的頁(yè)面來(lái)確定是否已返回了后臺(tái)數(shù)據(jù)庫(kù)的所有記錄。若返回了所有記錄則結(jié)束提交過(guò)程，否則進(jìn)入窮盡階段。用來(lái)確定一個(gè)查詢提交是否返回了新的數(shù)據(jù)記錄的方法很多。一種方法是使用Web信息抽取工具抽取返回頁(yè)面中的記錄，把記錄存儲(chǔ)到數(shù)據(jù)庫(kù)中，然后通過(guò)數(shù)據(jù)庫(kù)記錄比較來(lái)確定是否有新的記錄加入。這里使用改進(jìn)后的復(fù)本檢測(cè)系統(tǒng)來(lái)判斷記錄是否重復(fù)。它主要是計(jì)算每個(gè)候選記錄的哈希值，視具有相同哈希值的為重復(fù)記錄。

表3 使用隨機(jī)模式的“分層采樣”

1．2．2窮盡后臺(tái)數(shù)據(jù)庫(kù)信息

如果C次采樣提交每次都產(chǎn)生了新的記錄，則窮盡表單元素其它可能值組合來(lái)提交表單，直到滿足特定的結(jié)束條件。然而在繼續(xù)提交表單前，先要估計(jì)完成這樣的操作所需的最大剩余時(shí)間和用于存儲(chǔ)所有結(jié)果記錄所需的最大空間?？梢灾付ㄈ缦聨讉€(gè)參數(shù)來(lái)完成此階段的任務(wù)：最大查詢提交次數(shù)、最大存儲(chǔ)空間和最大剩余時(shí)間等。

可以通過(guò)疊加每次查詢所返回的數(shù)據(jù)量來(lái)估計(jì)所需最大存儲(chǔ)空間S。類似地可以估計(jì)最大剩余時(shí)間T。

在窮盡階段，可以使用幾個(gè)參數(shù)閥值來(lái)提前結(jié)束提交過(guò)程。包括：

(1)獲取Web數(shù)據(jù)庫(kù)數(shù)據(jù)的百分比：通過(guò)估計(jì)Web數(shù)據(jù)庫(kù)百分比以確定獲取了多少數(shù)據(jù)以后可以結(jié)束提交過(guò)程。

(2)查詢提交次數(shù)：通過(guò)確定查詢提交次數(shù)來(lái)減輕站點(diǎn)的負(fù)擔(dān)。

(3)獲取數(shù)據(jù)的數(shù)量：即獲取了多少惟一性的Web數(shù)據(jù)庫(kù)信息。

(4)提交時(shí)間：爬行某特定站點(diǎn)需要多長(zhǎng)時(shí)間。

上述每一個(gè)閥值或其組合都可以在窮盡階段提前結(jié)束爬蟲(chóng)爬行。

1．3識(shí)別和存取查詢結(jié)果

對(duì)表單提交操作產(chǎn)生的響應(yīng)主要有如下幾種情況：響應(yīng)頁(yè)含有后臺(tái)數(shù)據(jù)庫(kù)部分或所有數(shù)據(jù)；響應(yīng)頁(yè)不僅包含有數(shù)據(jù)還包含鏈接；響應(yīng)頁(yè)含有數(shù)據(jù)和原始表單結(jié)構(gòu)；響應(yīng)頁(yè)可能是另一張需要進(jìn)一步填寫的表單；錯(cuò)誤頁(yè)面通知；無(wú)記錄通知或需要缺失字段。這一步主要是針對(duì)這些可能出現(xiàn)的情況進(jìn)行處理。然后從含有豐富數(shù)據(jù)的頁(yè)面中使用信息抽取工具抽取結(jié)構(gòu)化的數(shù)據(jù)構(gòu)建數(shù)據(jù)，以進(jìn)一步提供信息檢索服務(wù)。

2 結(jié)束語(yǔ)

本文提出一種針對(duì)特定類型表單獲取Hidden Web頁(yè)面的爬蟲(chóng)設(shè)計(jì)原型系統(tǒng)，它首先使用默認(rèn)值來(lái)提交表單，以兩階段采樣策略確定是否充分獲取了后臺(tái)數(shù)據(jù)庫(kù)數(shù)據(jù)，然后從響應(yīng)頁(yè)中抽取出用戶感興趣的信息。此爬蟲(chóng)可以獲取一部分Hidden Web頁(yè)面，它彌補(bǔ)了當(dāng)前爬蟲(chóng)只能索引靜態(tài)頁(yè)面的不足。下一步需要做的工作是，在真實(shí)Hidden Web站點(diǎn)進(jìn)行大量實(shí)驗(yàn)及解決自動(dòng)發(fā)現(xiàn)搜索接口等問(wèn)題以完善此系統(tǒng)。畢竟存在很多需要填寫文本元素的表單，這就需要擴(kuò)展此系統(tǒng)使其能自動(dòng)填寫文本域元素。如使用HiWE系統(tǒng)中的屬性標(biāo)簽值對(duì)表或使用領(lǐng)域本體知識(shí)庫(kù)來(lái)自動(dòng)學(xué)習(xí)填寫表單以處理更多類型的表單，從而從Hidden Web中獲取更多的用戶感興趣的高質(zhì)量信息。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。