如何測試搜索引擎的索引量大小

如何測試搜索引擎的索引量大小(前篇)背景知識：搜索引擎的質(zhì)量指標(biāo)一般包括相關(guān)性(Relevance)、時效性(Freshness)、全面性(Comprehensiveness)和可用性(Usability)等四個方面，今天我們要談的索引量就屬于完整性指標(biāo)的范疇。首先需要注意的是，對于搜索引擎，網(wǎng)頁的索引量和抓取量是不同的概念。搜索引擎的網(wǎng)頁抓取數(shù)量一般都要遠(yuǎn)大于索引量，因?yàn)樽ト〉木W(wǎng)頁中包括很多內(nèi)容重復(fù)或者作弊等質(zhì)量不高的網(wǎng)頁。搜索引擎需要根據(jù)算法從抓取的網(wǎng)頁當(dāng)中取其精華，去其糟粕，挑選出有價值的網(wǎng)頁進(jìn)行索引。因此，對用戶而言，搜索引擎的索引量大小才更有意義。其次，無限制增大索引量并不一定能保證搜索質(zhì)量的提升。一方面，在全面性指標(biāo)中，除索引量外，還需要考慮到收錄網(wǎng)頁的質(zhì)量和不同類型網(wǎng)頁的分布。另一方面，搜索引擎的質(zhì)量指標(biāo)體系要保證四方面的均衡發(fā)展，不是依靠單個指標(biāo)的突破就可以改善的。目前包括雅虎中國在內(nèi)的主流中文搜索引擎的網(wǎng)頁索引量都在20億量級，基本上可以滿足用戶的日常查詢需求。然而，由于從外部無法直接測算出搜索引擎網(wǎng)頁索引量的絕對值大小，很多搜索引擎服務(wù)商喜歡對外夸大自己的收錄網(wǎng)頁數(shù)，作為市場噱頭。從1998年開始，KrishnaBharat和AndreiBroder就開始研究，如何通過第三方來客觀比較不同搜索引擎索引量的大小。8年后，在今年5月份的WWW2006大會上，來自以色列的ZivBar-Yossef和MaximGurevich由于這方面的出色研究成果奪得了大會唯一的最佳論文獎。他們的研究算出了主流英文搜索引擎的索引量相對大?。貉呕⑹荊oogle的1.28倍,Google是MSN的1.36倍。他們是如何算出這些數(shù)字的呢？下面我們將為搜索引擎愛好者介紹這個算法，以及探討在中文搜索引擎上是如何應(yīng)用的。概述搜索引擎的索引量或稱覆蓋率對搜索結(jié)果的相關(guān)性、時效性和找到率都具有深遠(yuǎn)的影響。出于市場運(yùn)作的考慮，各大互聯(lián)網(wǎng)搜索引擎不時對外公布自己索引的文檔數(shù)量，然而這些數(shù)據(jù)往往不同程度地被加入了一些水份，可信度上有一個問號。因此，如何通過搜索引擎的公共接口，也就是通常所說的搜索框，比較客觀、準(zhǔn)確地測試它的索引量就成為了一個令人關(guān)注的問題WebTopkresuttsSamplerPublicInterlaceIndexedDoeumeritsOuerlesRandomdocument通常所說的搜索框，比較客觀、準(zhǔn)確地測試它的索引量就成為了一個令人關(guān)注的問題WebTopkresuttsSamplerPublicInterlaceIndexedDoeumeritsOuerlesRandomdocumentX€DIndex:SearchEngine圖1對搜索引擎的索引采樣每一個搜索引擎的索引都覆蓋了互聯(lián)網(wǎng)上全部文檔的一個子集。如果我們把測試作為對這個集合的采樣，那么問題的關(guān)鍵就在于如何實(shí)現(xiàn)一個近似的等概率隨機(jī)采樣(uniform,searchengineurlsampler)，參見圖1。具體地說，假定一個搜索引擎S總共索引了|D|個文檔，那么我們希望采樣得到某一個具體文檔的概率是1/|D|。一旦實(shí)現(xiàn)了通過搜索框?qū)λ饕牡雀怕孰S機(jī)采樣，我們就可以在統(tǒng)計意義上比較有把握地估計搜索引擎索引量的相對大小。如下圖所示：圖2比較搜索引擎索引的相對大小我們先對引擎S1隨機(jī)采樣N1個url。然后，通過url查詢獲知引擎S2索引了其中的N12個url，而沒有索引另外N10個。換句話說，N1=N10+N12。同樣地，如果我們對引擎S2隨機(jī)采樣N2個url，發(fā)現(xiàn)其中N21被S1收錄而N20沒有收錄，N2=N20+N21。那么我們可以估計S1與S2的相對大小為：|D1|/|D2|竺(N12+N10)/(N12+N12N20/N21)=(N1N21)/(N2N12)=N21/N12(如果N1——N2)如何測試搜索引擎的索引量大小(后篇)搜索引擎索引的等概率隨機(jī)采樣：對于搜索引擎等概率隨機(jī)采樣的研究已經(jīng)有了相當(dāng)長的歷史，具體的背景文獻(xiàn)我們不準(zhǔn)備在這里一一探討。我們希望通過對Bar-Yossef等人最近工作的介紹，把一種比較客觀、科學(xué)的測試方法推介給讀者。我們也會探討他們的方法對于中文索引的局限性和一些解決方案。ncoin器艸冷舟wgi巳iom3.DIK.G0.rnaps-vahcM),ccnien-wiki映曲呂ncoin器艸冷舟wgi巳iom3.DIK.G0.rnaps-vahcM),ccnien-wiki映曲呂*i■少Wiki；出石CWWV麗Eip<|L用卑匕網(wǎng)叩Hbgoogle，runewsirnri3p^,r圖3一個簡化的搜索引擎索引圖3給出了一個簡化了的搜索引擎索引示例，假定關(guān)鍵字"news"將返回4個結(jié)果：、、和news.bbc.co.uk。首先我們給出一組定義?關(guān)鍵字搜索結(jié)果集合：results(q)=｛搜索關(guān)鍵字q所返回的全部結(jié)果文檔之集合｝?文檔關(guān)鍵字集合：queries(x)=｛所有能返回文檔x的搜索關(guān)鍵字之集合｝?搜索關(guān)鍵字池P：—組理論上能夠覆蓋所有文檔的搜索關(guān)鍵字集合o例如圖3中P=｛news,bbc,maps,google｝?關(guān)鍵字搜索結(jié)果量：card(q)=|results(q)|，搜索關(guān)鍵字q所返回的全部結(jié)果文檔之?dāng)?shù)量o例如圖3中card(“news”)=4，card(“bbc”)=3?文檔匹配度:deg(x)=|queries(x)|，全體能夠匹配文檔x的搜索關(guān)鍵字?jǐn)?shù)量o例如圖3中deg()=1，deg(HYPERLINKnews.bbc.co.uk)=2當(dāng)我們通過搜索框?qū)λ阉饕娴乃饕M(jìn)行采樣，所獲得的結(jié)果實(shí)際上偏向于匹配度高的文檔。對于圖3所示的搜索引擎，如果我們從搜索關(guān)鍵字池P=｛news,bbc,maps,google｝中任意選取一個關(guān)鍵字，然后在所得搜索結(jié)果中任意選取一個文檔，那么選到某一個具體文檔的概率與它的匹配度成正比，例如，p(HYPERLINKnews.bbc.co.uk)=2/13，p()=1/13因此，通過關(guān)鍵字對搜索引擎的索引進(jìn)行采樣，實(shí)際上是對文檔匹配度概率分布在作隨機(jī)抽樣。具體地說，如果相對于一個給定的搜索關(guān)鍵字池P,該索引的全部文檔匹配度的總和為deg(D)=工xwDdeg(x)，那么通過搜索框?qū)σ娌蓸荧@取具體一個文檔x的概率是deg(x)/deg(D)。如何通過對文檔匹配度分布的隨機(jī)抽樣而獲得我們所期望的等概率隨機(jī)采樣呢？這正是Bar-Yossef等人工作的主要成果所在：他們采用蒙特卡羅仿真(MonteCarloSimulation)算法實(shí)現(xiàn)了這一點(diǎn)?目標(biāo)分布n(x):D上的等概率隨機(jī)分布，n(x)=1/|D|?實(shí)際采樣分布p(x):D上的文檔匹配度隨機(jī)分布，p(x)=deg(x)/》x'gDdeg(x')?偏差權(quán)值:w(x)=n(x)/p(x)*1/deg(x)采樣過程，參見圖4?選定一個搜索關(guān)鍵字池P?隨機(jī)選取qWP?在搜索結(jié)果中隨機(jī)選取一個文檔xwresults(q)?計算該文檔對P的匹配度deg(x)?產(chǎn)生一個0~1的隨機(jī)數(shù)r,如果r<1/deg(x)保留該文檔，否則放棄?重復(fù)上述過程直到獲得N個有效采樣點(diǎn)圖4通過蒙特卡羅仿真(MonteCarloSimulation)算法實(shí)現(xiàn)對索引的等概率隨機(jī)采樣問題和討論上述算法在數(shù)學(xué)上非常嚴(yán)謹(jǐn)優(yōu)美，但是在具體的實(shí)現(xiàn)過程中仍然有相當(dāng)多的困難，尤其是對于中文搜索引擎，有一些特殊的問題需要探討。?搜索關(guān)鍵字池P的選取P選擇的條件是(1)要保證p(x)=0,即索引中文檔不匹配任何一個關(guān)鍵字qWP的概率足夠小。如果這個概率太高，測試只能局限于索引的一小部分，測試的結(jié)果就失去了意義。(2)關(guān)鍵字搜索結(jié)果量card(q)最好要比較小，這樣可以盡可能地避免搜索結(jié)果超過搜索引擎允許返回結(jié)果的上限。作者提出的方案是通過抓取和分析一個大型的網(wǎng)上文庫，例如維基百科全書，選擇其中所有的英文單詞的集合或者所有K個相連單詞的集合作為P。這對于沒有分詞問題的英文而言是容易實(shí)現(xiàn)的，但對于漢語等需要分詞的語種，這個方法似乎并不很合適。我們建議直接采用GBK字庫中的全部字符，或者采用中文分詞標(biāo)準(zhǔn)中所有詞匯的集合。?如何計算文檔對P的匹配度deg(x)?文檔匹配度deg(x)必須離線計算，通過查詢獲得是不現(xiàn)實(shí)的。對英文文檔來說，只要計算文檔中覆蓋了多少個關(guān)鍵字qwP。但是對中文而言，不同引擎包含了不同的搜索邏輯，例如四個漢字以下的搜索通常采取詞組搜索，長搜索詞有些引擎可能采取與或邏輯。不同引擎對于漢語分詞的處理也有較大的差異。在索引文檔時，有些引擎可能考慮了繁簡漢字的轉(zhuǎn)換。所有這些都會對匹配度產(chǎn)生一定程度的影響。實(shí)際上，匹配度deg(x)的計算并不一定要十分精確，一些近似處理是可以接受的，只要誤差不至于太大。我們建議用GBK字庫的單個