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

索引詞索引項(postinglist)北京大學<doc1><doc2>。。。計算機<doc1><doc3>。。。。。。。。。

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

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

排文

件①

①

①

②

③

③

③

④

④

④

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

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

③

北京大學①

④

∧

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