胡曉光信息檢索實(shí)驗(yàn)室.ppt

胡曉光 信息檢索實(shí)驗(yàn)室,索引和查找,提綱,順序查找 索引查找 簽名文件 倒排文件 PAT樹（Patricia tree） 關(guān)于壓縮,說明,索引和查找的關(guān)系 索引和查找其實(shí)是密不可分的 建索引時(shí)必須不斷的執(zhí)行查找操作 查找和查詢的區(qū)別 查找（search） 如何在索引中定位關(guān)鍵詞信息 查詢（query） Query處理：如何根據(jù)用戶輸入確定關(guān)鍵詞 檢索模型：如何利用查找返回的信息計(jì)算相似度等 文本壓縮和索引壓縮的區(qū)別 注意文本壓縮不能有效地減少索引文件的大小,順序查找,精確匹配算法 Brute Force Knuth-Morris-Pratt Boyer-Moore Shift-Or Suffix Automaton 容錯(cuò)匹配算法 Dynamic Programming Non-deterministic Finite Automaton Bit-Parallelism 正則表達(dá)式和擴(kuò)展模式,索引,索引文件 為方便查找，描述原文件信息組織的文件 簽名文件，倒排文檔，后綴樹都是索引文件,簽名文件,Karp-Rabin匹配思想 假設(shè)我們現(xiàn)在要判斷字符串A和字符串B是否匹配 把A和B分別散列成數(shù)字hash (A)和hash (B) 如果hash (A) != hash (B) 則A != B 然而hash (A) = hash (B) 不能說明 A B,Karp-Rabin匹配例子 關(guān)鍵詞 x05 ： A A C T C T Hash( x05 ) = 17579 文本y09 ： G C A A C T C T C A Hash( y05 ) = 17819 文本y09 ： G C A A C T C T C A Hash( y16 ) = 17533 文本y09 ： G C A A C T C T C A Hash( y27 ) = 17579,簽名文件,文檔的簽名 把文檔中的關(guān)鍵詞散列成F位的位串Signature 順序訪問原文檔的關(guān)鍵詞，把散列所得的位串依次存入文件 重疊編碼(superimposed coding) 我們不需要為每個(gè)關(guān)鍵詞都保存一個(gè)Signature 多個(gè)關(guān)鍵詞共用一個(gè)Signature可以減少文件的長(zhǎng)度 錯(cuò)誤匹配（False drop） 由于重疊編碼和哈希沖突的原因，關(guān)鍵詞和Signature不是一一對(duì)應(yīng)的關(guān)系 Signature匹配并不能保證關(guān)鍵詞一定出現(xiàn)，還需要檢查,Block 1 Block2 Block3 Block4,000101 110101 100100 101101,文本,簽名文件,h(text) =000101 h(many) =110000 h(words) =100100 h(made) =001100 h(letters) =100001,This is a text. A text has many words. Words are made from letters.,簽名文件,簽名文件,優(yōu)點(diǎn) 文件組織簡(jiǎn)單，基本和原文檔順序一致 維護(hù)容易，生成，插入，刪除都很方便 所需空間小，特別是采用重疊編碼之后 缺點(diǎn) 檢索速度慢，需要順序掃描 并且，當(dāng)False Drop發(fā)生的時(shí)候需要比較原文檔 總之 簽名文件是倒排文檔和全文掃描之間的折中,倒排文件,倒排索引思想 每個(gè)文檔都可以用一系列關(guān)鍵詞來表示 如果按關(guān)鍵詞建立到文檔的索引便可以根據(jù)關(guān)鍵詞快速地檢索到相關(guān)文檔 倒排文件組成 詞匯表（Vocabulary） 根據(jù)Heaps定律，通常比較小O (n), : 0.40.6 通常我們稱存放詞匯表的文件為索引文件（index file） 出現(xiàn)位置（Occurrence） 較大，O（n），通常在原文本的3040 通常我們稱存放出現(xiàn)位置的文件為置入文件（posting file）,倒排文件,1 6 9 11 17 19 24 28 33 40 46 50 55 60 This is a text. A text has many words. Words are made from letters.,letters 60 made 50 many 28 text 11, 19 words 30, 40 ,Vocabulary Occurrences,Text,addressing granularity: inverted list word positions character positions inverted file document,倒排文件,塊地址索引 有時(shí)候?yàn)榱斯?jié)省索引空間，可按塊地址建索引 把原文劃分為多個(gè)塊，只記錄關(guān)鍵詞的塊地址,Block1 Block2 Block3 Block 4 This is a text. A text has many words. Words are made from letters.,letters 4 made 4 many 2 text 1, 2 words 3 ,Vocabulary Occurrences,Text,Inverted index,倒排文件,倒排文件的性能 時(shí)間代價(jià)主要取決于詞匯表的組織方式 詞表文件通常較小且比較固定 對(duì)于未登錄詞和數(shù)詞可以按字建索引 空間代價(jià)主要取決于對(duì)置入文件的壓縮能力 置入文件的壓縮能減少IO操作，也能提高部分時(shí)間性能 詞匯表文件的組織方式 采用Hash散列表 按字母表順序有序排列 采用Trie樹，B樹等查找樹 置入文件的壓縮 通常采用差值壓縮（delta compression）,倒排文件,詞匯表的哈希存儲(chǔ) 根據(jù)給定的關(guān)鍵字，散列成一個(gè)整數(shù) 用該整數(shù)作為詞匯的訪問地址 例如：如果我們按字索引，那么可以直接用字的編碼 作為訪問地址，對(duì)于2字節(jié)編碼只需64K地址 優(yōu)點(diǎn) 實(shí)現(xiàn)簡(jiǎn)單 速度極快 缺點(diǎn) 關(guān)鍵在于找到一個(gè)好的散列函數(shù) 隨著現(xiàn)在散列空間的增大，問題相對(duì)簡(jiǎn)單 當(dāng)沖突過多時(shí)效率會(huì)下降,倒排文件,詞匯表的順序排列 把詞匯按照字典順序排列 詞匯的查找采用二分查找 優(yōu)點(diǎn) 實(shí)現(xiàn)簡(jiǎn)單 詞匯表體積?。ㄍǔＶ挥袔渍祝?缺點(diǎn) 索引構(gòu)建的效率一般 對(duì)于插入的文檔需要反復(fù)地調(diào)用排序和查找算法 排序的時(shí)間復(fù)雜度為N*log N （分配排序例外） 索引合并時(shí)還需要堆排序等方法合并多個(gè)有序的詞匯表 如果合并最主要的時(shí)間開銷在于IO操作的話，這點(diǎn)還是次要的 檢索的效率一般 二分查找logN的復(fù)雜度已經(jīng)具有較好的效率 能不能變成和詞匯數(shù)量無關(guān)的常數(shù)復(fù)雜度,倒排文件,Lucene的詞匯表即采用這種方式 假設(shè)現(xiàn)在詞表中有16，000個(gè)詞 indexInterval=16 則在詞表中需要查找次數(shù)為16log(1000) = 26次,倒排文件,詞匯表的查找樹 把詞匯表中的關(guān)鍵詞以樹的形式組織 二叉樹，B樹，Trie 等 二叉查找樹 考慮到平衡性，性能低于二分查找 B樹 是多路查找樹，效率高于二叉樹，實(shí)現(xiàn)更麻煩 Trie 樹 查找時(shí)間只跟詞的長(zhǎng)度有關(guān) 而于詞表中詞的個(gè)數(shù)無關(guān) 詞表較大時(shí)才能體現(xiàn)出速度優(yōu)勢(shì) Log (詞表長(zhǎng)度) E(詞長(zhǎng)) E表示期望,Trie樹,什么是trie樹 trie樹是一種用于快速檢索的多叉樹結(jié)構(gòu) trie樹把要查找的關(guān)鍵詞看作一個(gè)字符序列。 根據(jù)這一序列構(gòu)造用于檢索的樹結(jié)構(gòu)。 在trie樹上進(jìn)行檢索類似于查閱英語詞典。 例如，電子英文詞典，為了方便用戶快速檢索英語單詞，可以建立一棵trie樹。,詞典單詞：a、b、c、aa、ab、ac、ba、ca、 aba、abc、baa、bab、bac、cab、abba、baba、caba、abaca、caaba,Trie樹,優(yōu)點(diǎn) 查找效率高，與詞表長(zhǎng)度無關(guān) Trie樹的查找效率只與關(guān)鍵詞長(zhǎng)度有關(guān) 目前我們分詞詞表最長(zhǎng)的詞為13個(gè)字 “大不列顛及北愛爾蘭聯(lián)合王國(guó)” 事實(shí)上索引詞表中詞過長(zhǎng)會(huì)降低檢索召回率 用戶如果只輸入“北愛爾蘭”則無法返回該結(jié)果 索引的插入，合并速度快 注意，直接遍歷Trie樹需要搜索大量的無效節(jié)點(diǎn) 可以把數(shù)據(jù)存在一個(gè)數(shù)組中，Trie只保存指針 這樣合并時(shí)，只需要對(duì)數(shù)組進(jìn)行遍歷即可 缺點(diǎn) 所需空間較大 如果是完全m叉樹，節(jié)點(diǎn)數(shù)指數(shù)級(jí)增長(zhǎng) 好在Trie不是，但所需空間仍然很大 不可達(dá)上限： 詞數(shù) 字符序列長(zhǎng)度 字符集大小 指針長(zhǎng)度 例如：20000 6 256 4 120M 實(shí)現(xiàn)較復(fù)雜,差值壓縮（Delta Compression）,置入文件 置入文件必須包含如下信息 當(dāng)前詞出現(xiàn)的文檔號(hào)ID，以及在文檔中的位置Pos 差值壓縮 記錄當(dāng)前ID和前一ID的差值 記錄當(dāng)前Pos和前一Pos的差值 這樣做能有效減少表示ID，Pos所需的字長(zhǎng) 例如：關(guān)鍵詞A在文檔13，124，346中出現(xiàn) 如果不壓縮，由于346256,需要要兩個(gè)字節(jié) 而346124222256，只需一個(gè)字節(jié) 應(yīng)用實(shí)例 Lucene對(duì)詞匯表和置入文件都采用了這種壓縮,PAT樹（Patricia tree）,什么是Patricia樹 Patricia樹是Trie樹的壓縮表示 所有只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)都和父節(jié)點(diǎn)合并 后綴樹（Suffix tree） 以文本所有后綴為關(guān)鍵詞的Patricia樹 后綴樹的引入主要是針對(duì)字符串的高效查找 子串查找 最長(zhǎng)重復(fù)子串 最長(zhǎng)公共子串 回文子串 后綴數(shù)組（Suffix array） 按后綴樹的先根遍歷順序，存儲(chǔ)后綴,1 6 9 11 17 19 24 28 33 40 46 50 55 60 This is a text. A text has many words. Words are made from letters.,Suffix Trie,60,50,28,19,11,40,33,l,m,a,d,n,t,e,x,t,w,o,r,d,s,60,5,50,28,19,11,40,33,l,m,d,n,t,w,1,6,3,Suffix Tree,space overhead: 120%240% over the text size,Text,difference between suffix array and inverted list,suffix array: the occurrences of each word are sorted lexicographically by the text following the word inverted list: the occurrences of each word are sorted by text position,1 6 9 11 17 19 24 28 33 40 46 50 55 60 This is a text. A text has many words. Words are made from letters.,Suffix Array,Inverted list,Vocabul