1、信息檢索中效率問題的研究,報告人：趙江華北京大學計算機科學與技術系網(wǎng)絡與分布式系統(tǒng)實驗室2002年4月21日,信息檢索(IR)的基本概念（一）,信息檢索和數(shù)據(jù)庫管理系統(tǒng)(DBMS）的區(qū)別：DBMS處理對象是結構化數(shù)據(jù)，IR處理大量的非結構化數(shù)據(jù)。DBMS只是管理數(shù)據(jù)，IR要管理數(shù)據(jù)的內容——內容管理（content management）。DBMS的每次事務的結果是確定的，IR系統(tǒng)的任務是找到用戶需要的信息，其

2、結果是不精確的。,信息檢索(IR)的基本概念（二）,信息檢索的兩大問題：效率(efficiency)、效果（effectiveness）。效果指標：查準率(precision)和查全率（recall）。效率指標：響應時間(response time)和吞吐量（throughput）。文本信息檢索效果的提高依賴于自然語言處理(NLP)；信息的指數(shù)增長使得檢索效率也成為不可忽略的問題。,信息檢索(IR)的基本概念（三）,信息檢索系統(tǒng)的

3、組成部分：,信息檢索(IR)的基本概念（四）,基本用戶查詢(query):邏輯操作(AND,OR,NOT)。位置鄰近查找(Proximity Search),短語查找(Phrase Search)。對原始信息創(chuàng)建索引加快檢索速度： Inverted file , signature file等。倒排文件是最廣泛使用的技術，它組織結構靈活，可以滿足多種查詢方式。,對文檔的預處理,在英語等語言中做“stem”,索引單詞的“主

4、干”?！?可以提高查全率，降低查準率。漢字之間沒有空格，可以對漢字字符索引，也可以索引做切詞處理后的詞組。 現(xiàn)代漢語中大部分是兩個字的詞組，單個的字符表示的意義很不確定，所以對詞組建索引可以提高查詢的效果。切詞對查詢效率也有重大影響。,倒排文件的組織,將文檔分割成獨立的單詞項(term),按單詞項索引形成倒排文件。單詞tj對應的posting lists是{( di , fi, a*)+( di+k , fi+k, a*

5、)+…}，fi表示tj在di的出現(xiàn)次數(shù)，也是后面a的數(shù)量。這是倒排文件的全文本索引(full-text inverted file)形式,它記錄了每次出現(xiàn)的位置等信息，要占用較多的存儲空間。如果去掉位置信息，僅可以支持邏輯查詢形式。,詞典的組織（一）,索引單詞項的集合構成詞典，系統(tǒng)通過查找詞典定位該單詞對應的posting lists，這是從單詞到指針的映射。有兩種詞典的組織方式：直接用B+樹等方式組織單詞的字符串。用哈希（hash

6、）的方式——速度更快，可以將所有單詞裝入內存中。,詞典的組織（二）,“天網(wǎng)”中用哈希的方法實現(xiàn)從單詞字符串到單詞標識(TermID，整數(shù))的轉換，單詞的標志是在每次創(chuàng)建索引是賦予的（不是固定的），所有單詞的標志是從零開始的連續(xù)整數(shù)。如果維護一個全局穩(wěn)定的詞典（固定單詞的標識，便于維護），系統(tǒng)的TermID可能成為稀疏的整數(shù)，可以組織成B+樹實現(xiàn)從TermID到指針的映射。,數(shù)據(jù)組織（一）,倒排文件中單詞對應的posting lists

7、部分必須存儲在磁盤中，不同單詞的posting lists 長度差別很大，可以區(qū)別對待。存儲管理的方法在DBMS已經有深入研究。在倒排文件中，每個單詞的posting lists的訪問模式是順序掃描（sequential scanning） ，作為一個對象看待最合適。關系數(shù)據(jù)庫管理系統(tǒng)（RDBMS）用于倒排文件的缺點是不太靈活，而且SQL語句的開銷比較大。,數(shù)據(jù)組織（二）,面向對象的概念更能簡潔地描述倒排文件的結構，采用面向對象數(shù)據(jù)庫

8、系統(tǒng)（OODBS）是更好的選擇。下面是兩個被一些IR系統(tǒng)使用的例子：用持久對象存儲（Persistent Object Store）Mneme管理倒排文件，Mneme不但提供基于對象的數(shù)據(jù)緩存和良好的磁盤空間分配策略，還可以用它高度的可擴展性，根據(jù)數(shù)據(jù)的特性定制存儲。ObjectStore是商業(yè)上最成功的面向對象數(shù)據(jù)庫系統(tǒng)之一，它用內存映射技術實現(xiàn)持久對象存儲，和程序語言（C,C++,JAVA）完全集成，既有程序設計語言的靈活，又

9、可以高效的存儲數(shù)據(jù)，是另一個很好的索引管理工具。,數(shù)據(jù)組織（三）,“天網(wǎng)”中用多個文件實現(xiàn)倒排文件的存儲，優(yōu)點是實現(xiàn)簡單，可以利用文件的緩存機制，缺點是靈活性差，效率也有所損失。嵌入式數(shù)據(jù)庫系統(tǒng)Berkeley Database（Berkeley DB）,是一個開放源代碼產品，它提供簡單高效的功能（三種訪問方法 B+tree, hash, recno ），實現(xiàn)key/value的存取，這已完全能滿足索引管理的需求，可以替代OODBS（

10、在WebBase項目中使用）。,實現(xiàn)倒排表的隨機訪問,高頻詞（Term）的Posting lists長度通常1Mbytes以上（隨著文檔數(shù)據(jù)庫規(guī)模增大，它會快速增長），稱作“l(fā)ong Posting lists”。如果對它作順序訪問，從磁盤讀入內存會耗費很長時間，同時占用系統(tǒng)大量的I/O帶寬，從而降低整個系統(tǒng)的吞吐量。解決的方法是將對long Posting lists的順序訪問變成隨機訪問（random access Posting

11、lists）, long Posting lists被按照“文檔號”分割成長度較小的數(shù)據(jù)塊，在“AND”和“Proximity search”操作時可以有選擇地訪問部分數(shù)據(jù)，不可能相關的文檔所在數(shù)據(jù)塊被“跳過”（skip）。它增加了按照“文檔號”索引數(shù)據(jù)，以空間換取時間。,信息檢索的緩沖區(qū)管理（一）,利用文件系統(tǒng)的緩存往往不能得到最佳的性能，根據(jù)Posting lists的順序訪問模式，可以采用基于對象的緩存，對象持久存儲中的雙向緩沖區(qū)

12、將對象和分頁緩存結合起來，是一種更佳的策略。對很高頻的單詞，由于它對查詢準確度的提高很有限（有些系統(tǒng)將它們作為stopword忽略，不建索引），緩存整個它的Posting lists將占用大量內存，少量的高頻詞就可以耗盡所有的內存 ，所以緩存高頻詞的Posting lists將得不償失。采用random access Posting lists算法，可以將大對象分解成小對象，緩存對小對象的索引數(shù)據(jù)，提高內存使用效率。,信息檢索的緩沖區(qū)管

13、理（二）,Jónsson, Björn T., Franklin, Michael J. and Srivastava, Divesh. "Interaction of query evaluation and buffer management for information retrieval."研究了信息檢索中緩存管理和查詢的相互作用關系，作者提出兩種查詢時優(yōu)化利用緩存的策略：bu

14、ffer-aware query evaluation 和 ranking-aware buffer replacement，前者在查詢時優(yōu)先使用在緩存中的數(shù)據(jù)來減少讀磁盤，后一種技術將數(shù)據(jù)的語義引入到緩存的替換中，例如關鍵詞的Posting lists要被順序掃描，每次都必須訪問第一個數(shù)據(jù)頁，最后一頁則未必需要，所以就應該盡量保持它的第一頁在內存中。,查詢處理中的Fast Ranking技術,主要思想：不檢索出全部結果集，只需找出現(xiàn)面

15、K個結果——Retrieve partial document allowing error，要和相關度評價算法（ranking algorithm）結合。對數(shù)據(jù)存儲的要求是在每個單詞的Posting lists中要按照頻率排序（認為單詞在文檔中出現(xiàn)頻率越高，相關度越大）——Filtered Document Retrieval with Frequency-sorted Indexes。由于只需讀取部分數(shù)據(jù)，可以極大提高檢索效率。

16、,倒排文件壓縮（一）,影響倒排文件查詢效率的主要是關鍵詞的Posting lists，所以必須壓縮它的長度。壓縮以后減少了內存、磁盤空間的占用和I/O帶寬的使用，同時要對數(shù)據(jù)編碼和解碼，增加了CPU時間耗用?？紤]到I/O是系統(tǒng)的瓶頸，CPU和I/O之間不斷擴大的性能差距，以時間換取空間是可行的。壓縮不僅能提高查詢時的效率，還能加快創(chuàng)建索引，從各方面提升系統(tǒng)性能。,倒排文件壓縮（二）,關鍵詞對應的Posting lists是整數(shù)的序列，包

17、含文檔號（d）、關鍵詞在文檔中的頻度（f）和關鍵詞在文檔中的一系列出現(xiàn)（a）。壓縮的方法首先基于“游程編碼”（run length coding）,增量整數(shù)序列被變換為差分序列（原來相鄰整數(shù)之間的增量序列）。由于Posting lists中文檔號d和出現(xiàn)位置a，都是遞增排列，故可以做“游程編碼”變換。游程編碼本身并不能實現(xiàn)壓縮，只是較大的整數(shù)被變換成了較小的整數(shù)（頻度f本來就是小整數(shù)）。,倒排文件壓縮（三）,字節(jié)對齊索引壓縮（Byte

18、 Aligned Index Compression） 字節(jié)對齊索引的優(yōu)點是容易編碼和解碼，位操作少，占用CPU時間少，缺點是對很小的整數(shù)壓縮率低，每個整數(shù)最少用一個字節(jié)的空間。變長索引壓縮（Variable Length Index Compression） 一元編碼（unary）、δ編碼和γ編碼 進一步優(yōu)化的方法是根據(jù)整數(shù)序列的平均游程長度（mean run length）,對位向量編碼增加參數(shù)，稱作“局部模式”。比

19、較簡單的一種方法是：一個整數(shù)序列的個數(shù)是pw，則它的平均游程長度是N/ pw，設b=0.69N/ pw，取VG=(b, b, b,…) 作壓縮向量，前綴用一元編碼，后綴是二進制編碼（占用個位）。,倒排文件壓縮（四）,在非全文索引中，Posting lists由文檔號d和文檔中的詞頻f組成，一個（d, f）平均用1個字節(jié)即可表示；單詞t的Posting lists平均長度可以根據(jù)t的IDF推算出來。在全文索引中，單詞出現(xiàn)的位置信息占據(jù)索

20、引數(shù)據(jù)的主要部分，所以忽略文檔號d和文檔中的詞頻f。用變長壓縮算法，單詞出現(xiàn)位置平均可以用少于8bit的位表示。設全部文檔分詞后的單詞總數(shù)是TN，那么單詞t總的出現(xiàn)次數(shù)是TN*TF， 它的Posting lists平均長度小于TN*TF字節(jié)。,結論（一）,用戶的大部分查詢中的單詞數(shù)量比較少，查詢一個主題時用2-3個單詞就可以描述，查詢文章的題目時可能有10個單詞以上。不妨設Lq表示用戶查詢中的單詞個數(shù)，估計平均Lq等于5。根據(jù)前面得出的

21、現(xiàn)在一個磁盤的IOPS=100， 可以計算出在不考慮數(shù)據(jù)緩存情況下，系統(tǒng)平均每秒鐘處理查詢的上限是IOPS/Lq=20。根據(jù)磁盤的可用帶寬大約是20MBytes/s，得出每個查詢的I/O應不大于1Mbytes，也就是滿足如下條件：TN*TF*Lq≤1MB。代入以上得出的估計參數(shù)，有如下結論：l        對漢語字符： TN≤400MB（TF=0.05%，

22、Lq=5 ）l        對英語單詞： TN≤4GB（TF=0.005%，Lq=5 ）,結論（二）,由于漢語的一個字符占兩個字節(jié)，所以如果對漢語字符建索引，要維持每秒20個查詢的系統(tǒng)吞吐量，只能索引800MB的文本數(shù)據(jù)庫。英語的一個單詞平均占用字節(jié)6-8個（包括空格符），故同樣情況下可以索引24-32GB的英語文本。 漢語切詞后關鍵詞的平均頻率達到和英語相

23、近的水平 。在“天網(wǎng)”的檢索系統(tǒng)中，使用北大計算語言學研究所開發(fā)的切詞程序（共收錄了7.3萬詞條 ），切詞后對詞組建索引。日本的中日韓詞典研究所[41]構建的漢語詞典有260萬的簡體和繁體詞條，包括60萬的一般詞匯（簡繁各240,000）和科技術語，200萬的人名、地名和公司名稱等，它對GB-2312的詞頻統(tǒng)計顯示在第100個詞頻率已經下降到0.05%。,結論（三）,單機系統(tǒng)支持的檢索系統(tǒng)規(guī)模在Gbytes級，更大規(guī)模的數(shù)據(jù)必須使用分