基于雙配置文件的深度網(wǎng)搜索

（同濟大學(xué) a.電信學(xué)院 計算機系; b.軟件學(xué)院， 上海 201804）



摘 要：

深度網(wǎng)搜索的核心部分就是深度網(wǎng)數(shù)據(jù)庫接口的抽取和集成，雖然在理論上提出了很多種方案，并且在特定實驗中也有著較好的效果，但是至今仍未將這些方法有效地整合到實際情況中去。首先提出了通過雙配置文件的方式來簡化深度網(wǎng)的實現(xiàn)，其次提出了一種基于編碼方式的接口集成和映射的新方法，最后通過實驗證明該框架和編碼方法具有良好的實用效果。

 關(guān)鍵詞：深度網(wǎng); 配置文件; 編碼; 映射

 中圖分類號：TP39 文獻標志碼： A

文章編號：10013695(2008)12362103



Crawling Deep Web with two configurations

JIANG Xiucaia， MU Binb



(a.Dept.of Computer， College of Electronic Information Engineering， b.College of Software， Tongji University， Shanghai 210804， China)



Abstract:

The core of crawling Deep Web is the extraction and integration of Deep Web database interfaces， although many solutions have been formulated in theory， and even possessed lots of satisfied results in the particular experiments，they can’t be integrated according to the practice successfully. At the beginning， this chapter demonstrated a novel framework with two configurations to simplify the implement of probing the Deep Web. In addition， put forward a novel approach for integrating and mapping those interfaces based on a code algorithm. Finally， used experiments to prove them well.

 Key words：Deep Web; configuration; encode; mapping



深度網(wǎng)又稱隱藏網(wǎng)、不可見網(wǎng)，用來定義那些不能通過靜態(tài)網(wǎng)頁鏈接獲取，而是直接通過填入與數(shù)據(jù)庫相連的表單接口動態(tài)生成的那部分網(wǎng)頁。研究表明，傳統(tǒng)搜索引擎只能搜索到約三分之一的深度網(wǎng)，這就意味著還有大量的深度網(wǎng)內(nèi)容不被察覺。深度網(wǎng)不但含有豐富的內(nèi)容（大約是靜態(tài)網(wǎng)容量的500倍^[1]，約有45萬個數(shù)據(jù)庫和1258萬個查詢接口^[2]），而且所設(shè)計到的信息很具有專業(yè)性，因此發(fā)掘出深度網(wǎng)資源具有很大的現(xiàn)實意義。但是深度網(wǎng)的挖掘不同于靜態(tài)網(wǎng)，這主要是數(shù)據(jù)的存儲方式不同所導(dǎo)致的。在靜態(tài)網(wǎng)中，數(shù)據(jù)大部分存儲在半結(jié)構(gòu)化的網(wǎng)頁中，而在深度網(wǎng)中，數(shù)據(jù)主要存儲在數(shù)據(jù)庫中。研究表明，深度網(wǎng)中的數(shù)據(jù)結(jié)構(gòu)化與非結(jié)構(gòu)化比例大約為34 ： 1，并且約94％的查詢接口隱藏在深度不會超過3的網(wǎng)絡(luò)站點中^[2]，因此對于深度網(wǎng)要采用不同的搜索方法。

搜索深度網(wǎng)可以分為以下幾個方面：a）從網(wǎng)頁上獲取表單;b）對表單進行關(guān)鍵字抽取并集成;c）填充表單并提交;d）分析返回的結(jié)果。當(dāng)然每個部分還可以分成更小的部分，最近的一些研究工作也是基于這些方面的。然而，對于深度網(wǎng)的研究，各個部分的研究成果也各不一致，有些方面已經(jīng)日趨成熟，如表單關(guān)鍵字的抽取和匹配以及表單的集成等；而有些方面只是一些探索和假設(shè)，如語義的分析等。

1 系統(tǒng)的基本結(jié)構(gòu)

11 系統(tǒng)的框架

本文提出的深度網(wǎng)搜索的基本框架如圖1所示。首先，用 戶將自己所要查詢的信息進行歸類集成，選取或輸入與查詢信息所關(guān)聯(lián)的一系列關(guān)鍵詞，然后發(fā)送給控制中心?？刂浦行目刂铺幚砥鞯奶幚恚⒏鶕?jù)配置文件1生成與用戶相符的查詢接口傳遞給用戶進行查詢輸入。用戶輸入查詢語句之后，將結(jié)果再次發(fā)送到控制中心，控制中心又將它發(fā)送到同一處理器。處理器再次讀取配置文件2進行處理，并將得到的結(jié)果返回給頁面處理器進行頁面內(nèi)容抽取篩選，最后內(nèi)容進行重復(fù)處理后返回給用戶。

12 關(guān)鍵詞入口和查詢接口

用戶要查詢信息就要輸入一系列的關(guān)鍵詞作為對查詢信息的描述，如購書，就要選擇書名、作者、ISBN、價格等一些關(guān)鍵詞，當(dāng)然這里的關(guān)鍵詞要與深度網(wǎng)的表單接口屬性相聯(lián)系。一旦你選擇了關(guān)鍵詞后，系統(tǒng)會根據(jù)這些關(guān)鍵詞自動生成查詢接口，然后就可以輸入所要查詢的信息，但是這里生成的查詢接口并不是單個接口，而是某個域中一系列接口的集成。因此選擇好關(guān)鍵詞就意味著選擇了一個集成查詢接口。 

13 控制中心

這個部分在該框架中起著控制和傳遞數(shù)據(jù)的作用。

14 配置文件1

該配置文件是框架中的核心文件之一，主要用來存儲集成接口的關(guān)鍵詞以及這些關(guān)鍵詞的限定域和類型等信息。對于關(guān)鍵詞，它的值域可以分為有限型和無限型。對于有限型值域應(yīng)該完全列舉出來；而對于無限型值域，應(yīng)該將出現(xiàn)頻率高的值作為可能選擇的默認值，這樣就能極大地提高網(wǎng)頁查找率和準確率，降低對關(guān)鍵詞誤用或亂用的可能性。

15 配置文件2

該配置文件是框架中的另一個核心文件，也可以說是整個系統(tǒng)的中心點，因為它全面闡述了集成接口與各個子接口之間的聯(lián)系，雖然只是涉及到接口間的映射關(guān)系，但是仍然需要從子接口的獲取、集成等方面來得到這些映射關(guān)系。下面將探討映射所涉及的方面以及映射關(guān)系的生成。

151 表單接口的獲取

關(guān)于這個接口的獲取，至今并沒有一個行之有效的方法，因為無論是IP窮舉法還是迭代法，其缺點和優(yōu)點均是一樣的明顯。最近，文獻[3，4]提出了采用DynaBot的方法來對深度網(wǎng)進行搜索和聚集，但是在整個DynaBot中主要依靠SCD來進行標準判斷，而SCD的建立又具有不確定性，最后在SourceBiased分析階段不但工作量大，而且效果也很差。 

152 表單接口的融合

將一系列同領(lǐng)域的表單接口抽取出來之后，就要按照它們之間的聯(lián)系進行集成。關(guān)于集成方面的研究，最近一直很熱，也很成熟。其中，文獻[5]闡述了在ecommerce中進行數(shù)據(jù)庫查詢接口的集成策略；文獻[6]提出了相關(guān)屬性的集成方法；文獻[7]論證了通過對深度網(wǎng)接口模式匹配的方法來聚集接口；文獻[8]論述了通過對屬性尋找值的方法來進行匹配；文獻[9]提出了一個MetaQuerier整合模型；文獻[10]又論述了一個WISEintegrator模型，它比MetaQuerier模型更全面，所有這些方法均在某些方面很好地解釋和集成了接口。關(guān)于表單的集成，本文在19節(jié)中提出了一種新的方法。

153 映射關(guān)系

映射關(guān)系體現(xiàn)了信息從集成接口如何分發(fā)到各個子接口，而映射效果的好壞將直接關(guān)系到各個子接口中填充信息的完整性和準確性，19節(jié)將闡述一種高效的映射方法。

16 處理器

處理器是整個系統(tǒng)中真正的執(zhí)行者，而兩個配置文件則是指導(dǎo)處理器應(yīng)該如何進行查詢信息的分發(fā)，如何去搜索那些與接口相連的在線數(shù)據(jù)庫。

17 頁面處理

關(guān)于頁面處理，文獻[11]提出了一種Thor結(jié)構(gòu)；文獻[12]闡述了一種Turbo wrapper框架；文獻[13]論述了一種Testbed模型。雖然它們在有效性方面有待提高，但是均能很好地抽取到一定的結(jié)果，而現(xiàn)在的抽取工作主要也是通過各種分裝器來完成的。

18 重復(fù)處理

該過程屬于系統(tǒng)中的優(yōu)化過程，主要目的就是對抽取的結(jié)果進行去冗余和排序，返回最有可能滿足客戶的信息。

19 基于編碼方式的接口集成和映射

191 樹模型

設(shè)定一個接口模式為η=(ε1，ε2，…，εi)。其中：εi表示接口中所擁有的互不相同的屬性?？紤]一個同域的接口模式集合S＝（η1，η2，…，ηj），那么A=∪ j n=1 ηn則表示集合S中相異的屬性集合。對于集合A中的每一個屬性εt，又可以用δt=∑ j i=1 Nηi來表示集合中該屬性出現(xiàn)的次數(shù)。其中：Nηi∈（0，1），即如果該接口ηi含有屬性εt，那么Nηi為1，否則為0，因此A中每個屬性頻率形成的集合為＝（δ1，δ2，δ3，…，δq）。最后再用φt表示第t個屬性的權(quán)值，即φt=δt/∑ q p=1 δp，表示接口模式中該屬性所占的比重。將這些權(quán)值進行降序排列，得到的集合設(shè)為W＝（φ1，φ2，…，φq），與此順序相對應(yīng)的A中元素序列設(shè)為（A1，A2，…，Aq），當(dāng)?shù)玫竭@些值后就用算法1來構(gòu)造樹。

算法1 

a)如果屬性Ai含有子元素設(shè)為（Ax1，Ax2，…，Axd），那么從屬性集合中去掉這些元素并且修改其父屬性的權(quán)值，φ′ i＝φi+ΔΨ（∑ d i=1 Axi）。其中：ΔΨ為設(shè)定的一個閾值。

b)對剩下的元素再進行一次降序排列，設(shè)為F=（A1，A2，…，Am）構(gòu)成m棵二叉樹T={T1，T2，…，Tm}。其中：每棵Ti二叉樹中只有一個權(quán)值為φi的根節(jié)點，它的左右子樹均為空。

c)在F中選取兩棵根節(jié)點權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹（設(shè)定左子節(jié)點的權(quán)值小于右子節(jié)點的權(quán)值），新二叉樹的根節(jié)點的權(quán)值為其左右子樹的根節(jié)點的權(quán)值之和。 

d)從F中刪除這兩棵樹，并將這棵新的二叉樹加入到集合F中。 

e) 重復(fù)過程b），直到只剩下一棵樹為止，這棵樹就是本文所求的樹。 

f)設(shè)左支路為0，右支路為1，將該樹上的葉子進行編碼，于是便得到了所有屬性的編碼集合M＝（β1，β2，…，βm）。

g)將子元素以冗余碼的方式添加到父屬性的編碼中。 

采用算法1，筆者將所有的屬性均編譯成了一段編碼，根據(jù)本文的理論可知，γ=∑ m i=1 φiLi是最小的。其中：Li表示從根節(jié)點到第i個葉子的分支數(shù)目。

192 譯碼

一旦將屬性編碼之后，剩下的工作就是對用戶輸入的編碼進行編譯得到屬性，可以由算法2來進行。

算法2 

輸入：編碼φ；

輸出：=，屬性編碼集合M＝（β1，β2，…，βm），與之對應(yīng)的屬性集合為F=（A1，A2，…，Am），子元素的降序排列集合L＝（Ax1，Ax2，…，Axd）

n=0;

當(dāng)用戶從統(tǒng)一接口輸入編碼φ后，經(jīng)過解析生成屬性序列，再生成查詢接口。該方法是根據(jù)用戶的選擇動態(tài)生成集成接口，不必拘束于某一個集成接口，因此具有很大的優(yōu)越性。當(dāng)然仍可以對算法的匹配進行改進：設(shè)由屬性F=（A1，A2，…，Am）組成的樹為Tf，然后再對Tf樹進行高度為=(1，2，…，q）的商劃分，形成深度為q的索引，而對于屬性中的子元素，以冗余碼的形式放在主屬性的后面，這樣就能最大限度地減少比較的次數(shù)。

193 接口的映射

統(tǒng)一接口動態(tài)形成后，從統(tǒng)一接口映射到各個接口便是本文討論的重點。本文設(shè)所有接口模式的相異屬性集合為F=（A1，A2，…，Aq），對于每一個接口模式用二進制代碼來表示。其形成和映射如算法3所示。

算法3 

a）將集合F按照屬性權(quán)值降序排列，如果該屬性含有子元素，則從中去除子元素，并以降序排列的方式添加到另一個與對應(yīng)父屬性相連的集合中，變化后的F′＝（A1，A2，…，Am)，子元素的排列為（Ax1，Ax2，…，Axd）。

b）對每一個接口模式設(shè)為ηt=(ε1，ε2，…，εi)，對于F′中每個元素采用以下規(guī)則進行編碼：

 τi= 1 Ai∈ηt0 Aiηt (1≤i≤m)

因此該接口模式的編碼為  t=(τ1，τ2，…，τm)。對于子元素采用同樣方式以冗余碼的形式添加到接口模式的編碼中。

c）設(shè)集合 R ＝（  1，  2，…，  j）表示所有接口模式編碼的集合，然后進行卡諾圖化簡。對于父元素的集成要加上子元素的限制條件。

d）對集成的編碼采用索引相連，運行從集成接口到子接口的映射時，將客戶選擇的屬性采用以上的方式進行編碼后與索引中元素相與，再對結(jié)果異或，值為0，則繼續(xù)匹配下去；否則搜索另一元素，直至找到相關(guān)子接口。

e） 去重復(fù)，得到相異子接口，這些子接口便是映射的結(jié)果。 

2 實驗結(jié)果

這次實驗主要是關(guān)于book這個域的研究，然后用召回率和準確率來驗證框架和編碼方法的實效性。關(guān)于實驗中查詢接口模式的抽取，可以使用文獻[6，7，9，10]來得到；為了實驗的簡化，實驗中所用的接口模式直接采用文獻[4]所提供的數(shù)據(jù)，總共有55個接口和247個屬性。根據(jù)對各個屬性統(tǒng)計，其結(jié)果如表1所示。

因為first name和last name是author屬性的子元素，本文將first name、 last name進行刪除，并且修改author的ratio。設(shè)Δψ＝075，則δ′＝0186＋075×（0.025＋0.032）＝0229。以下用A、B、C、D、E、F、G、H、I、J、K、L來代替這些排序后的屬性，按照算法1來構(gòu)造樹模型，其最終結(jié)果如圖2所示。

根據(jù)圖2可以給屬性編碼，如下所示：A:11，B:10，C:001，D:011，E:0000，F(xiàn):00011，G:01011，H:01010，I:01001，J:01000，K:000101，L:000100。又因為A含有子元素，需要給A加上一段冗余碼，（00）表示無子元素，（10）表示只含有first name，(01)表示只含有l(wèi)ast name，而（11）表示兩個子元素均含有。對于算法匹配的改進，可以設(shè)定＝{3}，那么可以分為兩部分，第一部分為（10，11，001，000*，011，010*）;第二部分為（0，100，101，11）、（00，01，10，11）。

利用算法3可以對每個接口生成以下編碼（只選取其中的10個來解釋），如表2所示。

由上面的編碼可知，屬性G、H、I、J、K、L可以不予考慮，只需關(guān)心剩下的那些屬性。根據(jù)卡諾圖化簡可以得到如下的集合類:0（11）以上集合便是本文所求的一級映射索引，當(dāng)屬性很多不好集成時，可以采用部分編碼集成的辦法，即有選擇地集成部分編碼。編程后，用戶界面如圖3所示。在最后的結(jié)果抽取中，使用分裝器來抽取，得到的召回率和準確率分別為80%和91%，達到了筆者預(yù)期的效果。

通過以上的實驗驗證，雖然召回率不高，且部分工程是由手工來完成的，但該深度網(wǎng)搜索框架還能夠較好地完成筆者所期望的效果。文獻[15]闡述了一個HIWE模型，但在本文所提出的框架中只需要兩個簡單的配置文件就可以完成所有的功能。不僅如此，該框架將查詢實現(xiàn)與接口的實現(xiàn)通過兩個配置文件相分離，這樣有助于更好地完善接口的發(fā)現(xiàn)、集成等問題。另外對新增加的接口很容易融合到以前的集成接口中，更重要的是，本文所提出的基于編碼的接口集成有利于接口自動化集成的實現(xiàn)。當(dāng)然，該框架中的某些環(huán)節(jié)還有很大的優(yōu)化空間，關(guān)于框架的進一步改進也在筆者下一步研究之中。

4 結(jié)束語

Scirus和Google Scholar無疑是當(dāng)前最有影響力的兩個專業(yè)的搜索引擎，它們都是致力于對某一領(lǐng)域的信息進行深層的挖掘，并且對網(wǎng)頁信息采用了結(jié)構(gòu)化信息抽取。毫無疑問，它們都是深度網(wǎng)的實例化，它們的成功也正預(yù)示著深度網(wǎng)遠大的前景。

 參考文獻：

[1] BERGMAN M K. The Deep web: surfacing hidden value[J].Journalof Electronic Publishing，2002， 7 (1):89128914.

[2] HE Bin， MITESH P， ZHANG Zhen， et al. Accessing the Deep Web: a survey[J].Communication of the ACM，2007， 50 (5):94101.

[3] ROCOO D， CAVERLEE J， LIU Ling，et al. Exploiting the Deep Web with DynaBot: matching， Probing， and ranking[C]//Proc of the 14th International Conference on World Wide Web. New York: ACM Press， 2005:11741175.

[4] ROCOO D， LIU Ling， CRITCHLOW T. Focused crawling of the Deep Web using service class descriptions[D]. Carrollton: University of West Georgia， 2005.

[5] HE Hai， MENG Weiyi， YU C， et al. WISEintegrator: an automatic integrator of Web search interfaces for ecommerce[C]//Proc of the 29th International Conference on Very Large Databases. [S.l.]: VLDB Endowment， 2003:503505.

[6] KABRA G， LI Chengkai， CHANG K C C. Query routing: finding ways in the maze of the Deep Web[C]//Proc of International Workshop on Challenges in Web Informational Retrieval and Intergration. 2005:6473.

[7] WU Wensheng， DOAN A H， YU C. Merging interface schemes on the Deep Web via clustering aggregation[C]//Proc of the 5th IEEE International Conference on Data Mining. Washington DC: IEEE Computer Society， 2005:801804.

[8] WU Wensheng， DOAN A H， YU C. WebIQ:learning from the Web to match Deep Web query interfaces[C]//Proc of the 22nd International Conference on Data Engineering. 2006:44.

[9] HE Bin， ZHANG Zhen， CHANG K C C. Knocking the door to the Deep Web: integrating Web query interfaces[EB/OL].(200709).http://metaquerier.cs.uiuc.edu/.

[10] HE Hai， MENG Weiyi， YU C， et al. WISEintegrator: a system for extracting and integrating complex Web search interfaces of the Deep Web[C]//Proc of the 31st International Conference on Very Large Databases.[S.l.]: VLDB Endowment， 2005:13141317.

[11] CAVERLEE J， LIU Ling， BUTTLER D. Probe， cluster and discover: focused extraction of QApagelets from the Deep Web[C]//Proc of the 20th International Conference on Data Engineering New York: ACM Press， 2004:103114.

[12] CHUANG S L， CHANG K C C， ZHAI C X. Collaborative wrapping: a turbo framework for Web data extraction[C]//Proc of the 23rd International Conference on Data Engineering. 2007:12611262.

[13] YAMADA Y， CRASWELL N. Testbed for information extraction from Deep Web[C]//Proc of the 13th International World Wide Web Conference on Alternate Track Papers Posters. New York: ACM Press， 2004:346347.

[14] The UIUC Web integration repository[EB/OL].(2003).http://metaquerier.cs.uiuc.edu/repository.

[15] RAGHAVAN S， GARICAMOLINA H. Crawling the hidden Web， 200036[R].Stanford: Stanford University，2000.