文本檢索的索引技術(shù)

文本檢索的索引技術(shù)第1頁，共22頁，2023年，2月20日，星期六提綱背景和概念文檔分析索引創(chuàng)建索引查詢相關(guān)資料第2頁，共22頁，2023年，2月20日，星期六1。背景和概念－索引作用索引?提供從記錄的特征快速查詢到記錄的數(shù)據(jù)結(jié)構(gòu)(B樹、散列表、位圖索引等）數(shù)據(jù)庫，文檔數(shù)據(jù)庫，SE/IR系統(tǒng)文本檢索記錄－》文檔doc，記錄特征－》索引詞(indexterms)數(shù)據(jù)庫結(jié)構(gòu)化，查詢和事務(wù)型更新文檔數(shù)據(jù)庫非結(jié)構(gòu)化，查詢和事務(wù)型更新SE/IR系統(tǒng)非結(jié)構(gòu)化，查詢第3頁，共22頁，2023年，2月20日，星期六1。背景和概念－索引形式文本檢索常見索引方式Brute-force檢索grep簽名文件signaturefilehash簽名,falsematch倒排文件invertedfile 高效，支持多種檢索模型倒排索引從indexterm快速查詢到doc的索引結(jié)構(gòu)Doc正常表示為indexterm的集合，建立索引是把每個(gè)indexterm表示為其出現(xiàn)的doc的集合，這個(gè)過程稱為inversion，即倒排。第4頁，共22頁，2023年，2月20日，星期六1。背景和概念－倒排文檔內(nèi)容Doc1….北京大學(xué)計(jì)算機(jī)系….Doc2….北京大學(xué)主頁…..Doc3…計(jì)算機(jī)的發(fā)展…。。。

索引詞索引項(xiàng)(postinglist)北京大學(xué)<doc1><doc2>。。。計(jì)算機(jī)<doc1><doc3>。。。。。。。。。

原始文檔倒排索引倒排第5頁，共22頁，2023年，2月20日，星期六2。文檔分析－原則索引詞的選擇范圍人工索引－>質(zhì)量高，但不適用大規(guī)模文檔數(shù)據(jù)處理自動(dòng)索引部分索引－>title,abstract,keywords,etc（例如：北大圖書館的WebCat系統(tǒng)）全文索引－>文檔中所有詞都參與索引。(SE/IR普遍采用)索引詞的選擇原則Indexterm≠word理想：表達(dá)文檔內(nèi)容的語義單位字、詞、短語（詞匯詞）中文分詞第6頁，共22頁，2023年，2月20日，星期六2。文檔分析－英文文本Tokenize(Lexicalgrammar)

問題：“c++”，R&B，U.S.，a.out沒有被識(shí)別 問題：數(shù)字長(zhǎng)度、詞長(zhǎng)度詞規(guī)模Lemertization(曲折詞形合并)He,him->he;is,are,was->beStemmer(取詞根）Stemmer->stem;SE為了支持精確查詢，往往不使用后兩種技術(shù)[A-Z][A-Z]+returnUPWORD;[a-zA-Z0-9]+returnWORD;[A-Z][A-Z]+((\')?[s])?returnACRONYM2;[a-zA-Z0-9]+\'[a-zA-Z]+returnCONTRACTION;[A-Z]\.([A-Z]\.)+returnACRONYM;第7頁，共22頁，2023年，2月20日，星期六2。文檔分析－中文文本字符編碼問題字符集：GB2312,GBK,BIG5,HZUNICODE簡(jiǎn)、繁轉(zhuǎn)換（乾杯，乾坤）分詞問題詞？：語法詞、詞匯詞表達(dá)確定的意義（魚）、非組合性（多媒體）、互譯檢查（dioxide－二氧化物）第8頁，共22頁，2023年，2月20日，星期六2。文檔分析－中文文本分詞中文分詞歧義交集型：“部分居民生活水平”[1]分居、居民、民生、生活、組合型：“老人家”老人、老人家未登錄詞專有名詞（人名、地名、機(jī)構(gòu)名、譯名、術(shù)語等）、新詞對(duì)大規(guī)模中文信息處理，“詞典規(guī)模是制約分詞精度的主要因素”[2]第9頁，共22頁，2023年，2月20日，星期六2。文檔分析－中文文本混合索引基本分詞詞典6萬，選詞較為嚴(yán)格統(tǒng)計(jì)識(shí)別的未登錄詞擴(kuò)展詞典統(tǒng)計(jì)方法，精度不高如果加入到基本分詞詞典中，帶來大量組合型歧義問題，不能正確處理。->混合索引混合索引基本詞典：“北京”“大學(xué)”，無“北京大學(xué)”；擴(kuò)展詞典：有“北京大學(xué)”文檔中的“…北京大學(xué)…”，基本分詞分為“北京”“大學(xué)”，擴(kuò)展詞典基礎(chǔ)上在分為“北京大學(xué)”，索引按“北京”“大學(xué)”，“/2北京大學(xué)”這樣三個(gè)單位建立。第10頁，共22頁，2023年，2月20日，星期六3。倒排索引創(chuàng)建基本思想：排序文檔分析<term,doc><term,doc><term,doc><term,doc>文本數(shù)據(jù)排序詞典倒排文件term,ptrterm,ptrDoc1,doc2Doc1,doc2先term,再docid第11頁，共22頁，2023年，2月20日，星期六3。倒排索引創(chuàng)建－算法優(yōu)化Term編碼（詞典組織）每個(gè)term用整數(shù)編碼，減小存儲(chǔ)空間英文－前綴編碼(liber,liberal,liberalist…)散列表(MPH,無沖突散列）減少磁盤的隨機(jī)訪問次數(shù)－（大內(nèi)存環(huán)境）<termid,docid>在內(nèi)存中排序，排序結(jié)果分批寫入磁盤，最后合并。兩趟算法，在內(nèi)存中直接倒排，小倒排文件分批寫入磁盤，最后多路合并。數(shù)據(jù)壓縮第12頁，共22頁，2023年，2月20日，星期六3。倒排索引創(chuàng)建－兩趟算法詞典詞典詞典主詞典倒排文件倒排文件倒排文件主倒

排文

件①

①

①

②

③

③

③

④

④

④

第13頁，共22頁，2023年，2月20日，星期六3。倒排索引創(chuàng)建－兩趟算法Two-pass索引創(chuàng)建1。Parsing,提取indexterm，統(tǒng)計(jì)df和tf，通過hash表轉(zhuǎn)換為termid，生成詞典文件(lexiconfile)。2。按統(tǒng)計(jì)得到的indexterm的tf,df屬性,可以估計(jì)出對(duì)應(yīng)postinglist長(zhǎng)度，預(yù)申請(qǐng)空間。再次parsing文檔集，在內(nèi)存中執(zhí)行倒排。結(jié)果保存到臨時(shí)文件。3。對(duì)多次生成的臨時(shí)倒排文件，多路合并，壓縮輸出，得到最終倒排文件。效率：Parsing（包括中文分詞）為主要時(shí)間開銷?？臻g開銷在臨時(shí)文件(parsing結(jié)果，臨時(shí)倒排文件)上，使用壓縮。第14頁，共22頁，2023年，2月20日，星期六3。倒排索引創(chuàng)建－整數(shù)壓縮整數(shù)壓縮<docid,…..>的整數(shù)序列壓縮存貯。壓縮的基本思想：高頻使用較短的位表示，低頻使用較長(zhǎng)的位表示（Huffman編碼）頻率分布模式與編碼有序整數(shù)序列，記錄距離，改變頻率分布模式，以提高壓縮比1,3,7,11,13,141,2,4,4,2,1編碼方案γ

系列、golomb系列、bytecode第15頁，共22頁，2023年，2月20日，星期六4。索引查詢北京<d0,d1,d2…>詞典倒排文件<d0,d1…>大學(xué)②

③

北京大學(xué)①

④

∧

文檔屬性第16頁，共22頁，2023年，2月20日，星期六4。索引查詢布爾查詢北京AND大學(xué)VSMrank查詢相關(guān)度用文檔相似度來計(jì)算Similarity(Q,D)=COS(Q,D)第17頁，共22頁，2023年，2月20日，星期六4。索引查詢VSMrank查詢Document-level索引：<docid,F(d,t)>增加文檔屬性數(shù)據(jù)庫：|D|短語、臨近查詢例如：“北京網(wǎng)易”，“北京大學(xué)”Word-level索引：<docid,F(d,t),<loc1,loc2…locF(d,t)>>結(jié)構(gòu)查詢例如：“北京大學(xué)INTITLE”在loc數(shù)據(jù)中用位標(biāo)識(shí)記錄.VS.在word-levelindex基礎(chǔ)上使用textinterval第18頁，共22頁，2023年，2月20日，星期六4。索引查詢－效率問題索引壓縮減少磁盤io時(shí)間，增加cpu處理索引項(xiàng)的時(shí)間折衷：使用Bytecode，索引的隨機(jī)訪問－加入同步點(diǎn)更多的IO次數(shù)，減少數(shù)據(jù)傳輸總量折衷：控制block大小參數(shù)有待進(jìn)一步工作參考JustinZobel,IanWitten,Alistairmoffat等人一系列的paper第19頁，共22頁，2023年，2月20日，星期六5。其它問題倒排索引－更新查詢和更新效率postinglist連續(xù)存儲(chǔ)－>查詢效率高，更新難postinglist分塊鏈表存儲(chǔ)－>查詢效率低，更新易成批更新，