用Ｃａｐｔｕｒｅ Ｒｅｃａｐｔｕｒｅ方法估計(jì)Ｗｅｂ數(shù)據(jù)庫大小

（蘇州大學(xué) 智能信息處理研究所 江蘇 蘇州 215006）

摘 要：為了估計(jì)網(wǎng)絡(luò)數(shù)據(jù)庫的大小，提出了基于CaptureRecapture過濾二字親密、二字排斥的方法。通過在接口文本框提交屬性高頻字，利用返回的結(jié)果集，在兩兩之間作交集，根據(jù)交集中的兩字分布分析采樣的獨(dú)立性，過濾掉其中不獨(dú)立的情況，再利用CaptureRecapture方法估計(jì)網(wǎng)絡(luò)數(shù)據(jù)庫的大小。在模擬和真實(shí)的環(huán)境下進(jìn)行了實(shí)驗(yàn)，該方法偏差度和波動(dòng)度均較小。

關(guān)鍵詞：大小估計(jì)； 深網(wǎng)； 網(wǎng)絡(luò)數(shù)據(jù)庫

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)05-1754-03

Using CaptureRecapture approach estimate size of Web databases

MIAO Zhongyi HU Pengyu CUI Zhiming

(Institute of Intelligent Information Processing Application Suzhou University Suzhou Jiangsu 215006 China)

Abstract:In order to estimate the size of Web database this paper proposed the CaptureRecapture based estimation methods that filtered out two words intimate and rejection cases. Submitting attributed highfrequency words in the text box of query interface using the returned result in the intersection of two results analyzing the independence of two sampling filtering the dependent couples and then using CaptureRecapture method estimated the size of Web database. In the simulated and real environment for the experiment the bias and the volatility of the method are smaller.

Key words： size estimation; Deep Web; Web database



網(wǎng)絡(luò)上出現(xiàn)了越來越多可以在線訪問的數(shù)據(jù)庫，人們通過網(wǎng)頁上特定的查詢接口和后臺(tái)的數(shù)據(jù)庫進(jìn)行動(dòng)態(tài)交互，這種數(shù)據(jù)庫稱做Web database(WDB)，這樣的站點(diǎn)稱做Deep Web站點(diǎn)。文獻(xiàn)[1]在2000年6月對(duì)全球WDB的規(guī)模進(jìn)行了宏觀估計(jì)，稱約有43 000~96 000個(gè)Deep Web站點(diǎn)，Deep Web數(shù)據(jù)量約為靜態(tài)頁面的500倍；2004年4月文獻(xiàn)[2]對(duì)其進(jìn)行重新估計(jì)，稱有307 000個(gè)Deep Web站點(diǎn)，四年間增長(zhǎng)了3~7倍。文獻(xiàn)[3]對(duì)中國(guó)Deep Web的規(guī)模、分布和結(jié)構(gòu)進(jìn)行了研究，稱約有24 000個(gè)Deep Web站點(diǎn)，28 000個(gè)Web數(shù)據(jù)庫，如此龐大的優(yōu)質(zhì)數(shù)據(jù)資源等待挖掘。

WDB隱藏在查詢接口后面，對(duì)它的可用操作極其有限，不能提交類似SELECT COUNT(*) FROM WDB的SQL語句，確定WDB的大小就成了難題。但在很多應(yīng)用中要用到WDB的大小，如在Deep Web數(shù)據(jù)集成過程中，首先要進(jìn)行數(shù)據(jù)源的發(fā)現(xiàn)、數(shù)據(jù)源的選擇，然后集成數(shù)據(jù)。發(fā)現(xiàn)的數(shù)據(jù)源總是數(shù)量眾多且質(zhì)量參差不齊，如何選擇就涉及數(shù)據(jù)源質(zhì)量評(píng)價(jià)。其中大小就是一個(gè)重要的衡量指標(biāo)；Web數(shù)據(jù)庫爬蟲什么時(shí)候結(jié)束對(duì)一個(gè)WDB爬取也要參照其大小；再如Deep Web元搜索引擎，當(dāng)用戶在搜索引擎查詢接口上進(jìn)行查詢時(shí)，搜索引擎負(fù)責(zé)將查詢分發(fā)到具體的WDB查詢接口上，但同領(lǐng)域上也有眾多的WDB，若將查詢分發(fā)到該領(lǐng)域所有的接口上，搜索引擎必須在更大范圍上等待查詢返回延遲，所以搜索引擎必須在查詢時(shí)間和查全率之間作出權(quán)衡，而將查詢分發(fā)到領(lǐng)域內(nèi)幾個(gè)最大的WDB上是一種較聰明的作法；還有，在同一領(lǐng)域的WDB很多情況下是有重疊的，筆者曾試圖估計(jì)過兩個(gè)同領(lǐng)域WDB的重疊率，但要得到兩個(gè)WDB重疊的絕對(duì)數(shù)量，就要知道WDB的大小。

文獻(xiàn)[1]估計(jì)Deep Web數(shù)據(jù)量是靜態(tài)頁面的500倍，此后幾年直到現(xiàn)在靜態(tài)頁面和Deep Web數(shù)據(jù)量都迅速膨脹，那么兩者是否還保持2000年時(shí)的比例呢？對(duì)WDB大小的估計(jì)將有助于人們從宏觀角度理解兩者的發(fā)展速度。雖然有一些技巧可以用于估計(jì)WDB的大小，如中國(guó)圖書網(wǎng)聲稱有58萬本現(xiàn)貨圖書，另有一些網(wǎng)站提供記錄目錄列表或分類列表覆蓋數(shù)據(jù)庫的全部記錄，可用于統(tǒng)計(jì)數(shù)據(jù)庫大小，但不具有通用性。

1 相關(guān)工作

近年來有兩篇文獻(xiàn)介紹了Web數(shù)據(jù)庫的大小估計(jì)，Lu Jianguo在文獻(xiàn)[4]中提出了一種通過多次抽樣，確定惟一元素出現(xiàn)概率及重疊率之間的關(guān)系，進(jìn)而估計(jì)WDB的大小：

n∧=u/p；P=1-OR-1.1

(1)

其中:u為不相同的元素個(gè)數(shù)；P表示其出現(xiàn)的概率；OR(overlapping rate)表示重疊率，OR=t/u，t是總的抽樣數(shù)量。OR-1.1的指數(shù)是通過在英文語料庫上采用回歸分析得到的，但不一定適合其他語言，實(shí)驗(yàn)結(jié)果顯示該方法的穩(wěn)定性較差。

2008年2月凌妍妍等人在文獻(xiàn)[5]中提出一種基于屬性相關(guān)度的WDB大小估算方法，該方法基于下面簡(jiǎn)單的公式：

n∧=α/Pw(2)

其中：α表示抽樣數(shù)量；Pw表示一個(gè)詞在某屬性上出現(xiàn)的概率。通過分析兩個(gè)屬性的相關(guān)度，取其中兩個(gè)相關(guān)度較小的屬性，在一個(gè)屬性上提交查詢，在另一個(gè)屬性上統(tǒng)計(jì)詞頻，以此估計(jì)該屬性上詞的Pw。但該方法有以下兩個(gè)不足：首先，查詢接口中必須要有兩個(gè)或兩個(gè)以上文本框用于計(jì)算它們之間的相關(guān)度，但這樣的條件在很多情況下不能滿足，如查詢接口中只有一個(gè)文本框；其次，分析相關(guān)性計(jì)算代價(jià)較大，而且據(jù)實(shí)驗(yàn)證明，對(duì)于中文環(huán)境而言，基于字的兩個(gè)屬性之間的相關(guān)度大多情況下都很小，對(duì)估計(jì)的實(shí)質(zhì)影響小。

文獻(xiàn)[6]提到了利用CaptureRecapture方法來估計(jì)生物種群大小，若要估計(jì)某一地區(qū)一種野生動(dòng)物種群大小，先隨機(jī)捕捉一些活體，作標(biāo)記后放歸，然后再隨機(jī)捕捉一些，通過下式估計(jì)生物種群大小：

n∧=s1×s2/s(3)

其中：s1、s2表示第一次和第二次捕捉活體的數(shù)量；s表示兩次都被捕捉到的活體的數(shù)量。

本文利用文獻(xiàn)[6]中所提方法估計(jì)WDB大小，并克服文獻(xiàn)[4，5]所提方法的不足，從提高采樣隨機(jī)性、獨(dú)立性角度考慮，提出基于CaptureRecapture過濾二字親密、二字排斥的估計(jì)方法。

2 CaptureRecapture方法介紹及問題定義

2.1 CaptureRecapture方法

設(shè)S是一個(gè)集合，A、B是在S進(jìn)行獨(dú)立隨機(jī)抽樣產(chǎn)生的集合，如圖1所示，|S|、|A|、|B|表示三個(gè)集合的元素個(gè)數(shù)，P(X)表示一個(gè)元素出現(xiàn)在集合X中的概率，則

因?yàn)镻(A∩B)=P(A)×P(B)(4)

所以|A∩B|/|S|≈（|A|/|S|）×（|B|/|S|）(5)

即|S|≈|A|×|B|/|A∩B|(6)

根據(jù)式(6)，要估計(jì)一個(gè)集合的大小，可進(jìn)行兩次隨機(jī)且獨(dú)立的抽樣，通過兩次的抽樣數(shù)量及重疊元素的數(shù)量予以計(jì)算。

2.2 問題定義

由于Web數(shù)據(jù)庫隱藏在頁面查詢接口后，用戶只能通過查詢接口與之交互，可以執(zhí)行的操作很少，而且很多Web數(shù)據(jù)庫的所有者基于商業(yè)的考慮不對(duì)外提供其數(shù)據(jù)庫的大小。

WDB大小估計(jì)就是要通過網(wǎng)頁上的查詢接口對(duì)其進(jìn)行抽樣，根據(jù)樣本來估計(jì)總體的大小。

3 基于CaptureRecapture的估計(jì)方法

CaptureRecapture方法本身比較簡(jiǎn)單，但其隨機(jī)采樣^[7，8]和采樣獨(dú)立性的前提難以保證，本文力圖從這兩個(gè)角度入手解決問題。

3.1 基本概念

本文提出的方法以中文為背景，設(shè)有一串長(zhǎng)度為n的文字，A、B兩字同時(shí)且隨機(jī)出現(xiàn)在這串文字中，出現(xiàn)位置相互獨(dú)立，那么它們相鄰的概率為2/n。但現(xiàn)實(shí)情況下兩個(gè)漢字的出現(xiàn)并不隨機(jī)，有時(shí)兩個(gè)字以詞組形式伴隨出現(xiàn)，而有時(shí)兩個(gè)字是相互排斥的。為論述方便提出以下兩個(gè)概念：

a)二字親密。若A、B為兩個(gè)漢字，在一些長(zhǎng)度為n的字符串中，兩者同時(shí)出現(xiàn)且出現(xiàn)一次，A、B相鄰比率為α，α/(2/n)>1。若兩個(gè)字是二字親密的，那么它們?cè)跐h語中常常前后相伴出現(xiàn)，表現(xiàn)為兩個(gè)字的詞，像“中國(guó)”“女子”“子女”等，中間沒有其他字間隔。

b)二字排斥。若A、B為兩個(gè)漢字，在一些長(zhǎng)度為n的字符串中，兩者同時(shí)出現(xiàn)且出現(xiàn)一次，A、B相鄰比率為α，α/(2/n)<1。若兩個(gè)字是二字排斥的，那么它們較少相鄰出現(xiàn)，當(dāng)它們同處一字符串中時(shí)，兩字中間常有其他字相隔，偶有相鄰情況，兩者也可能分屬不同的詞。

在若干長(zhǎng)度為n的字符串中，當(dāng)A、B兩字相鄰的比率為α，且1/δ≤α/(2/n)≤δ（其中δ為閾值，大于1，具體取值可通過實(shí)驗(yàn)獲得），筆者認(rèn)為A、B的出現(xiàn)比較獨(dú)立，不存在嚴(yán)重親密和排斥問題。

本文的方法基于這樣的假設(shè)，除了二字親密、二字排斥外，在一段文字中任何兩個(gè)字的出現(xiàn)是獨(dú)立的。當(dāng)取一些字在接口上進(jìn)行查詢用于估計(jì)WDB大小時(shí)，排除二字親密、二字排斥的干擾便可得到較準(zhǔn)確的估計(jì)值。

3.2 方法概述

設(shè)有一DWB查詢接口I(xiàn)=〈A1，A2，…，An〉。其中至少有一個(gè)屬性Ai（1≤i≤n）對(duì)應(yīng)一個(gè)文本框，記做T。可以在T中輸入一個(gè)漢字并點(diǎn)擊提交按鈕進(jìn)行查詢，應(yīng)用信息抽取^[9，10]技術(shù)，抽取查詢返回結(jié)果，會(huì)得到一個(gè)結(jié)果集。對(duì)于屬性Ai通過一定的方法可獲得與該屬性相對(duì)應(yīng)WDB字段上出現(xiàn)頻率較高的字，稱之為屬性高頻字，若現(xiàn)有屬性高頻字集合FW = {w1，w2，w3，…，wn}，用FW中的字進(jìn)行查詢可以得到較多的查詢結(jié)果，估計(jì)結(jié)果更穩(wěn)定。在FW上取兩相異字分別在T上查詢，返回結(jié)果可以看做對(duì)數(shù)據(jù)庫的兩次抽樣，因此可以用CaptureRecapture方法估計(jì)數(shù)據(jù)庫的大小，但不同字對(duì)的估計(jì)準(zhǔn)確性不同，有的可能使估計(jì)值遠(yuǎn)遠(yuǎn)大于真實(shí)值，而有的則相反。如何盡可能過濾掉這兩種情況就成為解決問題的關(guān)鍵。本文通過測(cè)試兩字的親密程度進(jìn)行過濾。

設(shè)現(xiàn)有A、B兩個(gè)漢字，先用A在接口的文本框T上查詢，得到結(jié)果集A_RESULT，然后用B查詢得到B_RESULT，AB_RESULT是A_RESULT和B_RESULT的交集，按照CaptureRecapture方法，數(shù)據(jù)庫的大小等于｜A_RESULT｜*｜B_RESULT｜/｜AB_RESULT｜，但當(dāng)A、B二字親密時(shí)，舉個(gè)極端的例子，當(dāng)A出現(xiàn)B一定緊鄰出現(xiàn)，則A_RESULT =B_RESULT=AB_RESULT，那么以此估計(jì)的數(shù)據(jù)庫大小為｜AB_RESULT｜，這顯然在絕大多數(shù)情況下是不成立的；當(dāng)二字排斥時(shí)，A、B相鄰的比率也要比正常情況低得多，用它們來估計(jì)WDB大小時(shí)很有可能得到的結(jié)果要比真實(shí)的大，這兩種情況都是在WDB大小估計(jì)過程中應(yīng)該過濾出去的。

那么如何過濾，首先用AB、BA在文本框T上查詢，統(tǒng)計(jì)返回記錄數(shù)，可以得到二字相鄰的記錄條數(shù)，記做a；然后分別用A和B在文本框T上查詢，取兩者的交集可以得到A、B同時(shí)出現(xiàn)的記錄條數(shù)，記為b，則a/b是A、B實(shí)際相鄰比例，如果滿足1/δ≤(a/b) /(2/n)≤δ筆者認(rèn)為兩者的出現(xiàn)是比較隨機(jī)的可以用于數(shù)據(jù)庫大小估計(jì)，若 (a/b) /(2/n)≥δ認(rèn)為二字親密；(a/b) /(2/n)≤1/δ認(rèn)為二字排斥，應(yīng)將這樣的估計(jì)過濾出去。通過實(shí)驗(yàn)閾值δ在2~3之間比較適合，當(dāng)δ越小過濾出去的估計(jì)情況越多；反之越少。

3.3 具體步驟

獲得查詢接口上和某屬性相對(duì)應(yīng)的屬性高頻字，形成高頻字集合FW = {w1 w2 w3，…，wn}，在查詢接口中與該屬性相對(duì)應(yīng)的文本框T上進(jìn)行查詢，具體估計(jì)步聚如下：

a)FW={w1，w2，w3，…，wn}，n=0。

b)在FW中取兩個(gè)相異的字wi、wj（1≤i，j≤n）。

c)使用wi、wj在接口上查詢，抽取返回結(jié)果，得到記錄集合分別為Ri、Rj。

d)使用wiwj、wjwi在接口上查詢，抽取返回結(jié)果，得到合并的記錄集合為R。

e)在記錄集Ri∩Rj上求和接口文本框T相應(yīng)字段值平均長(zhǎng)度L。

f)當(dāng)1/δ≤ (|R|/|Ri∩Rj|)/ (2/L)≤δ，不是二字親密或二字排斥估計(jì)值可用，計(jì)數(shù)器n增1，估計(jì)值：sizen=|Ri|×|Rj|/|Ri∩Rj|，否則過濾出去。

g)若還有相異字對(duì)，則返回a)。

h)去掉最大、最小估計(jì)值，求均值size：

size=[∑ni=1size-(sizemax+sizemin)]/(n-2)(7)

4 實(shí)驗(yàn)

為了驗(yàn)證方法的有效性，筆者從本地模擬、真實(shí)Web數(shù)據(jù)庫兩個(gè)方面進(jìn)行實(shí)驗(yàn)，提出了兩個(gè)評(píng)估標(biāo)準(zhǔn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析。

4.1 數(shù)據(jù)集及平臺(tái)

實(shí)驗(yàn)的數(shù)據(jù)集分成兩類，即本地?cái)?shù)據(jù)庫和真實(shí)的Web數(shù)據(jù)庫。用本地?cái)?shù)據(jù)庫進(jìn)行驗(yàn)證有以下好處：a)速度快；b)不用進(jìn)行Web數(shù)據(jù)抽取；c)記錄（實(shí)體）識(shí)別方法簡(jiǎn)單；d)知道數(shù)據(jù)庫大小的確切值。但本地?cái)?shù)據(jù)庫并不是該方法真實(shí)的使用場(chǎng)合，所以筆者同時(shí)在真實(shí)的Web數(shù)據(jù)庫上進(jìn)行了驗(yàn)證。中國(guó)圖書網(wǎng)在首頁上說明有58萬冊(cè)現(xiàn)貨圖書，其他三個(gè)可以通過分類列表統(tǒng)計(jì)Web數(shù)據(jù)庫大小，表1是使用的數(shù)據(jù)集。

表1 實(shí)驗(yàn)數(shù)據(jù)集

類型數(shù)據(jù)庫記錄條數(shù)類型數(shù)據(jù)庫記錄條數(shù)

本地?cái)?shù)據(jù)庫BOOK1BOOK2MovieMusic

576 379125 00025 8729 078

WDB新書城網(wǎng)上書店中國(guó)圖書網(wǎng)卓越音樂Vod588電影

258 242580 00030 6224 218

實(shí)驗(yàn)的硬件平臺(tái)：Pentium(R)D CPU 2.66 GHz 512 MB內(nèi)存 160 GB硬盤；軟件平臺(tái)：Windows XP+MySQL5.0+Java1.5+HTML Parser。

4.2 評(píng)估標(biāo)準(zhǔn)

為了從定量的角度來分析該方法，提出了兩個(gè)度量標(biāo)準(zhǔn):偏差度(Δ)和波動(dòng)度(Ω) 。

Δ=[(｜size-size｜)/size]×100(8)

Ω=[(∑ni=1｜sizei-size｜)/(n×size)]×100(9)

其中：size表示真實(shí)的大小；size為平均估計(jì)大小；sizei為第i(1≤i≤n)個(gè)估計(jì)值。當(dāng)方法的偏差度越小，則準(zhǔn)確性越高;反之準(zhǔn)確性越低。當(dāng)方法的波動(dòng)度越小，則穩(wěn)定性越好;反之穩(wěn)定性越差。

4.3 實(shí)驗(yàn)及結(jié)果分析

為了全面驗(yàn)證方法的有效性，設(shè)計(jì)了以下三個(gè)實(shí)驗(yàn)：a)比較提交屬性高頻字和提交字典隨機(jī)取字的CaptureRecapture方法（含過濾）；b)比較過濾和不過濾二字親密、二字排斥；c)應(yīng)用本文方法估計(jì)WDB的大小。三個(gè)實(shí)驗(yàn)都是針對(duì)名稱屬性做的，其他屬性也可能得到類似的結(jié)論。

實(shí)驗(yàn)1 比較提交屬性高頻字和提交字典隨機(jī)取字（含過濾）。在本地模擬時(shí)很容易得到某個(gè)屬性的高頻字。其中BOOK1數(shù)據(jù)庫name字段上的高頻字：{“國(guó)”“中”“的”“學(xué)”“與”“書”“法”“教”“業(yè)”“理”}（其他數(shù)據(jù)庫省略），同時(shí)將隨機(jī)取字兩次采樣交集為空的情

從表2中的結(jié)果可以看出，使用屬性高頻字比隨機(jī)取字估計(jì)的偏差度、波動(dòng)度都要小，主要是因?yàn)殡S機(jī)取字的偶然性大，所以估計(jì)準(zhǔn)確性、穩(wěn)定性差。

實(shí)驗(yàn)2 比較過濾及不過濾二字親密、二字排斥。在提交屬性高頻字的情況下，比較了過濾及不過濾的差異，使用本文提出的過濾方法可以在一定程序上過濾出去嚴(yán)重偏離真實(shí)值的估計(jì)，可以看出，通過過濾可以使準(zhǔn)確性提高4個(gè)百分點(diǎn)以上(表3)，因?yàn)閷⒁恍﹪?yán)重偏離的估計(jì)過濾出去了，使得方法的波動(dòng)度有了較大下降，穩(wěn)定性提高了。而且在實(shí)驗(yàn)中發(fā)現(xiàn)將閾值δ設(shè)在2~3比較適合，太大、太小都不可取。

實(shí)驗(yàn)3 在真實(shí)環(huán)境下利用CaptureRecapture方法估計(jì)大小。實(shí)驗(yàn)的第一步是通過漢語中的高頻字^[11]為起點(diǎn)迭代誘導(dǎo)屬性高頻字，然后根據(jù)文中估計(jì)步驟進(jìn)行估計(jì)，因?yàn)楣P者選擇了一些提交查詢返回list頁面，點(diǎn)擊其中一項(xiàng)會(huì)打開一個(gè)detail頁面的Deep Web站點(diǎn)，這也與大多數(shù)WDB的真實(shí)情況相符，所以Web database中的每一條記錄都會(huì)對(duì)應(yīng)一個(gè)惟一的URL可以作為其實(shí)體識(shí)別標(biāo)志，進(jìn)而使真實(shí)環(huán)境下的實(shí)驗(yàn)幾乎達(dá)到了模擬環(huán)境的準(zhǔn)確性，結(jié)果如表4所示。

為了從橫向?qū)Ρ热N現(xiàn)有的方法，從表5中的幾個(gè)角度進(jìn)行了比較。

表5 三種WDB大小估計(jì)方法的比較

比較項(xiàng)基于CaptureRecapture方法基于屬性相關(guān)度方法基于采樣重疊率方法

固定偏差趨勢(shì)無偏小無

其中：固定偏差趨勢(shì)表示該方法估計(jì)結(jié)果是否總偏大或偏小的趨勢(shì)。本文方法和基于采樣重疊率方法的偏差