基于倒排文件中一種性能模型的研究

摘要：倒排文件作為現代大規模搜索引擎工作的一個核心技術，其原理簡單，具備靈活高效的特點，具體體現在其根據需要可做到適當的變通。本文通過在給定搜索引擎系統內部參數的前提下對其吞吐率的研究，建立一種倒排文件性能模型，該模型有效地提高了倒排文件的運行效率。



關鍵詞：倒排文件；搜索引擎；性能模型；信息檢索

中圖分類號：TP31 文獻標識碼：A



Web Log Mining Based on the Weight of the Technical Analysis Page



CHEN Hao

（Guangdong Technical College of Water Resources and Electric Engineering， Guangzhou510925， China）

Abstract：Inverted file as a core technology of the modern largescale search engine. The principle is simple， with a flexible and efficient features. Reflected in needed to do the appropriate modifications. This article by the premise of the internal parameters of a given search engine system throughput. Establishment of a performance model of the inverted file. The model can effectively improve the operating efficiency of the inverted file.



Key words：inverted file；search engine；performance model；information retrieval



1引言

評價一個大規模信息檢索系統，有兩個方面基本的考慮：效果和效率。效果也稱之為質量，指檢索返回結果集合的準確性、相關性和完整性。效率即為性能，其中最重要的指標就是查詢響應時間和吞吐率。

倒排文件是大型信息檢索中使用最為廣泛的文件索引方法。所謂“倒排”表示依據檢索屬性來列舉相關文件，是計算機科學中基本的信息查詢方法之一，并在數字圖書館和搜索引擎中廣為使用。本文通過對倒排文件算法的深入研究，提出了一種性能模型，為倒排文件及其實現的效果做了詳細的分析研究，倒排文件的性能得以提高。

2倒排文件的概念

所謂倒排文件是描述一個詞項集合元素即TERMS和一個文檔集合元素即DOCS對應關系的數據結構，記為：

DOCS={d1，d2，…dN}，TERMS={t1，t2，…，tM}

在以“文檔”為出發點時，稱之為di中包含哪些tj，也可理解為某一個tj在di文檔中出現了多少次。而“倒排文件”直接給出的是一個tj出現在哪些di中，進而還可以有它在某一個di中出現在哪些位置，包含多少次。用PL（tj）表示tj出現于其中的文檔記錄的集合，稱為對應于tj的倒排表，下面是信息檢索研究中常用的幾個相關量。

N：文檔集合的大小

M：詞項集合的大小

Sj=|PL（tj）|：詞項tj所涉及文檔的個數

DF（tj）=SjN：詞項tj的文檔頻率

IDF（tj）=—lgDF（tj）：倒置文檔頻率；其值越小表示出現頻率越高。

fi，j ：第j個詞項tj在第i個文檔di中出現的次數

TN=∑Ni=1∑Mj=1fi，j：系統所有文檔分解后包含詞項的總量

TF（tj）=∑Ni=1fi，jTN：詞項tj在所有文檔中出現的頻度

ITF（tj）=—lgTF（tj）：倒置詞頻；越小表示出現頻率越高

作為數據結構，倒排文件分為兩部分：第一部分是由不同詞項組成的索引，稱為詞表，第二部分由每個詞項出現過的文檔集合構成，稱為記錄文件，每個詞項的對應部分稱為倒排表，可以通過詞表訪問。具體倒排文件結構圖如下圖1所示：

圖1倒排文件結構圖

其中左邊是詞表，中間是記錄文件。對應于詞表的每一項，記錄文件中有若干個倒排表，一半長度記為sj；統計分布為p（i）。至于PL（tj）的每一項，取決于信息檢索的方式，對應內容則會有不同，在此用d表示其平均數據量，k表示查詢的到達量，r表示響應時間要求，B表示系統的最大輸出能力。

3倒排文件的一種性能模型

所謂性能模型，在此就是要給出關于N、M、p（i）、d、B、r和k的一種關系，從而能夠在給定系統內部參數的條件下對其外部行為即吞吐率進行估計。

在此需要對p（i）和B，以及幾個假設做以下說明：

p（i）代表倒排表長度的統計分布函數，即M×p（i）的長度表示i的記錄表的個數，i∈[0，N]。由此倒排表的平均長度為α=∑Ni=0i×p（i）=1M∑Mj=1Sj

B是支持倒排文件運行的下層系統的瓶頸帶寬。取決于不同的情況，可能是磁盤的I/0帶寬，也可能是網絡帶寬。

計算技術與自動化2012年9月

第31卷第3期陳浩：基于倒排文件中一種性能模型的研究

本文討論性能模塊的依據是根據同時到達的查詢量k，得到一個數據量D，然后看能否得到DB≤r，由此假設q1，q2，…，qk都是單純的，即它們都直接屬于集合TERMS且都是隨機、獨立分布的。通過考察k個查詢所導致的輸出數據量D。每個查詢都可能落到M個詞項中的任何一個中，k個查詢可能涉及M的任何1，2，…，或者k項，于是對應不同的數據量。若能算出涉及i項的概率，記作fM，k（i），i=1，2，…，k，則有D=一個倒排表的平均數據量×k個并發查詢平均涉及的倒排表個數=d×∑Ni=0i×p（i）×∑ki=1i×fM，k（i）=d×α×∑ki=1i×fM，k（i）

下面集中考慮fM，k（i）

首先k個查詢隨機落在M個詞項的所有可能總數，相當于從集合{1，2，…，k}到{1，2，…，M}的映射個數即Mk。

接著對i=1，2，…，k，考察k個查詢恰好落在i個倒排表上的情況，這相當于是考慮集合{1，2，…，k}的i劃分的個數，再加上這個i個倒排表可能落在M中的任意i個上；前者即第二類斯特林數S（k，i）。查詢在不同倒排表之間是可區分的，因此需要考慮排列，于是得到：

fM，k（i）=S（k，i）×PiMMk，i=1，2，…，k

D=d×α×∑ki=1i×S（k，i）×PiMMk

其中，S（k+1，i）=i×S（k，i）+S（k，i—1），S（k，0）=0，S（k，1）=S（k，k）=1，Mk=∑ki=0S（k，i）×PiM由此得到

∑ki=1i×S（k，i）×PiM

=∑ki=1[S（k+1，i）—S（k，i—1）]×PiM

=∑ki=1S（k+1，i）×PiM—∑ki=1S（k，i—1）×PiM

=∑k+1i=1S（k+1，i）×PiM—S（k+1，k+1）×

Pk+1M—M×∑ki=1S（k，i—1）×Pi—1M—1

=Mk+1—Pk+1M—

M∑k+1i=1S（k，i—1）×Pi—1M—1—S（k，k）×PkM—1

=Mk+1—Pk+1M—M×（M—1）k+M×PkM—1

=Mk+1—M×（M—1）k

=M×Mk—（M—1）k

所以

D=d×α×M×Mk—（M—1）kMk

=d×α×M×1—1—1Mk （1）

式1即為我們得到的一種倒排文件性能的基本模型。上式中直接給出的是k個并發查詢所導致的數據量。

4數據在磁盤和內存之間的移動

搜索引擎對文檔信息檢索的支持粒度，可分為“全文索引”和“非全文索引”兩類。非全文索引只需告知哪些文檔含有特定的詞項，而全文索引則還需要給出該詞項在相關文檔中出現的位置等信息，多次出現就多次記錄。上式公式中d的大小在全文索引情況下和詞項在不同文檔中出現的平均次數成比例，即∑Mj=1∑Ni=1fi，jN×M，而在非全文索引情況下則基本上是常數，記做c一般為幾個字節。

這里將d×α一并考慮。對于每一個倒排表對應于一個具體的詞項tj而言，它的數據量在全文索引情況下正比于N×DF（tj）+TN×TF（tj），前一部分是倒排表中文檔號和頻率占用的長度，后一部分是位置信息占用的長度。因為TN要遠大于N，所以系統中每個詞項倒排表的長度主要是由它的詞頻率TF和數據規模TN決定的。非全文索引的情況下則只有N×DF（tj）。在平均情況下：

d×α=c×α非全文索引c×α+TNM全文索引（2）

上式中，c表示為記錄一個詞項在文檔中一次出現位置信息所需的數據量。其中的符號所代表的量的數量級有些具體的概念是有必要的，以部分中文搜索引擎為例，c≈101，α≈105，M≈5×104，N≈3×107，TN≈1010。非全文索引的倒排表數據量在106數量級，而全文索引是它的若干倍。由此估算，作為整個倒排文件的記錄文件，即使非全文索引，內存也是放不下的。

另外，α作為倒排文件中倒排表長度的平均值，也就是和詞表中詞項的文檔頻率相關的一個量，即α=∑Mj=1N×DF（tJ）M。由于TF和DF常常是和應用相關的統計量，可以在具體實現之前進行估計，從而使得在設計倒排表應用時就能根據公式1對查詢導致的數據量有個估算。

在倒排文件查詢處理算法中，系統要將用戶查詢中單詞項對應的倒排表讀到內存中執行集合操作，因此倒排表的長度將首先影響操作執行的時間。當索引網頁量增加時，高頻詞項的倒排表將急劇膨脹，占用大量I/0帶寬、內存空間以及CPU時間，嚴重降低系統效率。理想情況下，所有詞項的頻率應該盡可能低，而且大小相近，使得所有倒排表保持同步增長，系統性能不會因為一部分單詞記錄表的長度快速增長而受損。而實際情況中，詞項的頻率分布和文件的語言有關。

5英語單詞和漢語字符實例分析

本文以CCF中國計算機學會統計出的英語單詞和漢語單字的頻率作為原始數據進行分析，將所有單詞按照它們的ITF（IDF）值從小到大排列，賦予[0，T]的序號x作為坐標圖的橫軸，ITF（IDF）值作為坐標圖的縱軸，即可得到單詞的ITF（IDF）分布圖。兩個統計結果都是按照單詞的出現頻率從高到低排序，如下表1中即是對數據抽樣的結果，表示降低到某一個頻率數值時的單詞序號。

表1英漢詞頻統計排序對照表

頻率

英語單詞

漢語字符

0.1%

103

252

0.07%

148

348

0.05%

220

475

0.02%

632

867

0.01%

1285

1215

0.007%

1780

1400

0.005%

2381

1609

0.002%

5474

2210

0.001%

6713

2676

由此得出使用的漢字比英語單詞要少的多，漢語的高頻字比英語的高頻單詞要多，低頻詞則反之。在萬分之一頻率處，兩者的數量近似。在十萬分之一處，英語有六千多個單詞，漢語單字卻不到三千個。根據表1繪制出的ITF分布如下圖2所示：

圖2英語單詞和漢語字符的ITF分布圖

其中兩條曲線在接近ITF=4處相交，漢語字符的曲線畢英語單詞的曲線要陡峭的多。這種特性決定了索引同樣數量的單詞即TN相等，漢語字符的倒排表平均長度要大于英語單詞，并且伴隨著TN的增長而加速增長。

6結論

在實際的查詢中詞項的頻率決定要讀取的記錄表長度，為了得到它們和搜索引擎吞吐量的關系，必須顧及出搜索引擎運行時查詢詞項的平均頻率。因此，本文公式1中關于D的表達式，只要M相對于k較大，都是很有效的，這個結果和預期值相符。

參考文獻

[1]張志剛.基于網頁的信息系統的一種預處理過程[M].北京：北京大學，2011.

[2]Baldi P，Frasconi P，Smyth P.2010. Modeling the Internet and the Web， probabilistic methods and algorithms. John Wiley.

[3]Persin M，Zobel J，Sacks—Davis R.Filered document retrieval with frequencysorted indexes[J]. Journal of the American Society for Information Science，2010，47：749—764.

[4]Lei M，et al.Improved relevance ranking in WebGather[J].Journal of Computer Science and Technology，2010，16：410—417.

[5]China Internet Network Information Center.2011.（中國互聯網絡信息中心） [EB/OL].http：//www.cnnic.net.cn