信息檢索中效率問題的研究

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

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

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

4、干”?！?可以提高查全率，降低查準(zhǔn)率。漢字之間沒有空格，可以對漢字字符索引，也可以索引做切詞處理后的詞組。 現(xiàn)代漢語中大部分是兩個(gè)字的詞組，單個(gè)的字符表示的意義很不確定，所以對詞組建索引可以提高查詢的效果。切詞對查詢效率也有重大影響。,倒排文件的組織,將文檔分割成獨(dú)立的單詞項(xiàng)(term),按單詞項(xiàng)索引形成倒排文件。單詞tj對應(yīng)的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)的位置等信息，要占用較多的存儲空間。如果去掉位置信息，僅可以支持邏輯查詢形式。,詞典的組織（一）,索引單詞項(xiàng)的集合構(gòu)成詞典，系統(tǒng)通過查找詞典定位該單詞對應(yīng)的posting lists，這是從單詞到指針的映射。有兩種詞典的組織方式：直接用B+樹等方式組織單詞的字符串。用哈希（hash

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

7、部分必須存儲在磁盤中，不同單詞的posting lists 長度差別很大，可以區(qū)別對待。存儲管理的方法在DBMS已經(jīng)有深入研究。在倒排文件中，每個(gè)單詞的posting lists的訪問模式是順序掃描（sequential scanning） ，作為一個(gè)對象看待最合適。關(guān)系數(shù)據(jù)庫管理系統(tǒng)（RDBMS）用于倒排文件的缺點(diǎn)是不太靈活，而且SQL語句的開銷比較大。,數(shù)據(jù)組織（二）,面向?qū)ο蟮母拍罡芎啙嵉孛枋龅古盼募慕Y(jié)構(gòu)，采用面向?qū)ο髷?shù)據(jù)庫

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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