天網(wǎng)索引系統(tǒng)介紹課件

1、文本檢索的索引技術(shù)彭波2003-11-1提綱背景和概念文檔分析索引創(chuàng)建索引查詢相關(guān)資料1。背景和概念索引作用索引?提供從記錄的特征快速查詢到記錄的數(shù)據(jù)結(jié)構(gòu)(B樹、散列表、位圖索引等）數(shù)據(jù)庫，文檔數(shù)據(jù)庫，SE/IR系統(tǒng)文本檢索記錄文檔doc，記錄特征索引詞(index terms)數(shù)據(jù)庫結(jié)構(gòu)化，查詢和事務(wù)型更新文檔數(shù)據(jù)庫非結(jié)構(gòu)化，查詢和事務(wù)型更新SE/IR系統(tǒng)非結(jié)構(gòu)化，查詢1。背景和概念索引形式文本檢索常見索引方式Brute-force檢索 grep簽名文件 signature file hash簽名,false match倒排文件 inverted file 高效，支持多種檢索模型倒排索引從i

2、ndex term快速查詢到doc的索引結(jié)構(gòu)Doc正常表示為index term的集合，建立索引是把每個index term表示為其出現(xiàn)的doc的集合，這個過程稱為inversion，即倒排。1。背景和概念倒排文檔內(nèi)容Doc1.北京大學(xué)計算機(jī)系.Doc2.北京大學(xué)主頁.Doc3計算機(jī)的發(fā)展。索引詞索引項(posting list)北京大學(xué)。計算機(jī)。原始文檔倒排索引倒排2。文檔分析原則索引詞的選擇范圍人工索引質(zhì)量高，但不適用大規(guī)模文檔數(shù)據(jù)處理自動索引部分索引title,abstract,keywords, etc（例如：北大圖書館的WebCat系統(tǒng)）全文索引文檔中所有詞都參與索引。(SE/IR普

3、遍采用)索引詞的選擇原則Index term word理想：表達(dá)文檔內(nèi)容的語義單位字、詞、短語（詞匯詞）中文分詞2。文檔分析英文文本Tokenize (Lexical grammar)問題：“c+”，R&B，U.S.，a.out沒有被識別問題：數(shù)字長度、詞長度詞規(guī)模Lemertization (曲折詞形合并)He,him -he ; is, are,was -beStemmer (取詞根）Stemmer -stem ; SE為了支持精確查詢，往往不使用后兩種技術(shù)A-ZA-Z+ return UPWORD; a-zA-Z0-9+ return WORD; A-ZA-Z+()?s)? return

4、 ACRONYM2; a-zA-Z0-9+a-zA-Z+ return CONTRACTION;A-Z.(A-Z.)+ return ACRONYM; 2。文檔分析中文文本字符編碼問題字符集：GB2312,GBK,BIG5,HZ UNICODE簡、繁轉(zhuǎn)換 （乾杯，乾坤）分詞問題詞？：語法詞、詞匯詞表達(dá)確定的意義（魚）、非組合性（多媒體）、互譯檢查（dioxide 二氧化物）2。文檔分析中文文本分詞中文分詞歧義交集型：“部分居民生活水平”1分居、居民、民生、生活、組合型：“老人家”老人、老人家未登錄詞專有名詞（人名、地名、機(jī)構(gòu)名、譯名、術(shù)語等）、新詞對大規(guī)模中文信息處理，“詞典規(guī)模是制約分詞精度

5、的主要因素”22。文檔分析中文文本混合索引基本分詞詞典6萬，選詞較為嚴(yán)格統(tǒng)計識別的未登錄詞擴(kuò)展詞典統(tǒng)計方法，精度不高如果加入到基本分詞詞典中，帶來大量組合型歧義問題，不能正確處理。-混合索引混合索引基本詞典：“北京”“大學(xué)”，無“北京大學(xué)”；擴(kuò)展詞典：有“北京大學(xué)”文檔中的“北京大學(xué)”，基本分詞分為“北京”“大學(xué)”，擴(kuò)展詞典基礎(chǔ)上在分為“北京大學(xué)”，索引按“北京”“大學(xué)”，“/2北京大學(xué)”這樣三個單位建立。3。倒排索引創(chuàng)建基本思想：排序文檔分析文本數(shù)據(jù)排序詞典倒排文件term,ptrterm,ptrDoc1,doc2Doc1,doc2先term,再docid3。倒排索引創(chuàng)建算法優(yōu)化Term編碼

6、（詞典組織）每個term用整數(shù)編碼，減小存儲空間英文前綴編碼(liber,liberal,liberalist)散列表(MPH,無沖突散列）減少磁盤的隨機(jī)訪問次數(shù)（大內(nèi)存環(huán)境）在內(nèi)存中排序，排序結(jié)果分批寫入磁盤，最后合并。兩趟算法，在內(nèi)存中直接倒排，小倒排文件分批寫入磁盤，最后多路合并。數(shù)據(jù)壓縮3。倒排索引創(chuàng)建兩趟算法詞典詞典詞典主詞典倒排文件倒排文件倒排文件主 倒排 文件 3。倒排索引創(chuàng)建兩趟算法Two-pass索引創(chuàng)建1。Parsing ,提取index term，統(tǒng)計df和tf，通過hash表轉(zhuǎn)換為term id，生成詞典文件(lexicon file)。2。按統(tǒng)計得到的index te

7、rm的tf,df屬性,可以估計出對應(yīng)posting list長度，預(yù)申請空間。再次parsing文檔集，在內(nèi)存中執(zhí)行倒排。結(jié)果保存到臨時文件。3。對多次生成的臨時倒排文件，多路合并，壓縮輸出，得到最終倒排文件。效率：Parsing（包括中文分詞）為主要時間開銷?？臻g開銷在臨時文件(parsing結(jié)果，臨時倒排文件)上，使用壓縮。3。倒排索引創(chuàng)建整數(shù)壓縮整數(shù)壓縮的整數(shù)序列壓縮存貯。壓縮的基本思想：高頻使用較短的位表示，低頻使用較長的位表示（ Huffman編碼 ）頻率分布模式與編碼有序整數(shù)序列，記錄距離，改變頻率分布模式，以提高壓縮比1,3,7,11,13,14 1,2,4,4,2,1編碼方案

8、系列、golomb系列、bytecode4。索引查詢北京詞典倒排文件大學(xué) 北京大學(xué) 文檔屬性4。索引查詢布爾查詢北京 AND 大學(xué)VSM rank查詢相關(guān)度用文檔相似度來計算Similarity(Q,D)=COS(Q,D)4。索引查詢VSM rank查詢Document-level索引：增加文檔屬性數(shù)據(jù)庫：|D|短語、臨近查詢例如：“北京 網(wǎng)易” ，“北京大學(xué)”Word-level索引：docid,F(d,t),結(jié)構(gòu)查詢例如：“北京大學(xué) IN TITLE”在loc數(shù)據(jù)中用位標(biāo)識記錄 .VS. 在word-level index基礎(chǔ)上使用text interval 4。索引查詢效率問題索引壓縮減少磁盤io時間，增加cpu處理索引項的時間折衷：使用Byte code，索引的隨機(jī)訪問加入同步點更多的IO次數(shù)，減少數(shù)據(jù)傳輸總量折衷：控制block大小參數(shù)有待進(jìn)一步工作參考Justin Zobel,Ian Witten,Alistair moffat等人一系列的paper5。其它問題倒排索引更新查詢和更新效率postinglist連續(xù)存儲查詢效率高，更新難posti