胡曉光信息檢索實驗室.ppt_第1頁
胡曉光信息檢索實驗室.ppt_第2頁
胡曉光信息檢索實驗室.ppt_第3頁
胡曉光信息檢索實驗室.ppt_第4頁
胡曉光信息檢索實驗室.ppt_第5頁
已閱讀5頁,還剩21頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

胡曉光 信息檢索實驗室,索引和查找,提綱,順序查找 索引查找 簽名文件 倒排文件 PAT樹(Patricia tree) 關于壓縮,說明,索引和查找的關系 索引和查找其實是密不可分的 建索引時必須不斷的執(zhí)行查找操作 查找和查詢的區(qū)別 查找(search) 如何在索引中定位關鍵詞信息 查詢(query) Query處理:如何根據用戶輸入確定關鍵詞 檢索模型:如何利用查找返回的信息計算相似度等 文本壓縮和索引壓縮的區(qū)別 注意文本壓縮不能有效地減少索引文件的大小,順序查找,精確匹配算法 Brute Force Knuth-Morris-Pratt Boyer-Moore Shift-Or Suffix Automaton 容錯匹配算法 Dynamic Programming Non-deterministic Finite Automaton Bit-Parallelism 正則表達式和擴展模式,索引,索引文件 為方便查找,描述原文件信息組織的文件 簽名文件,倒排文檔,后綴樹都是索引文件,簽名文件,Karp-Rabin匹配思想 假設我們現在要判斷字符串A和字符串B是否匹配 把A和B分別散列成數字hash (A)和hash (B) 如果hash (A) != hash (B) 則A != B 然而hash (A) = hash (B) 不能說明 A B,Karp-Rabin匹配例子 關鍵詞 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,簽名文件,文檔的簽名 把文檔中的關鍵詞散列成F位的位串Signature 順序訪問原文檔的關鍵詞,把散列所得的位串依次存入文件 重疊編碼(superimposed coding) 我們不需要為每個關鍵詞都保存一個Signature 多個關鍵詞共用一個Signature可以減少文件的長度 錯誤匹配(False drop) 由于重疊編碼和哈希沖突的原因,關鍵詞和Signature不是一一對應的關系 Signature匹配并不能保證關鍵詞一定出現,還需要檢查,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)點 文件組織簡單,基本和原文檔順序一致 維護容易,生成,插入,刪除都很方便 所需空間小,特別是采用重疊編碼之后 缺點 檢索速度慢,需要順序掃描 并且,當False Drop發(fā)生的時候需要比較原文檔 總之 簽名文件是倒排文檔和全文掃描之間的折中,倒排文件,倒排索引思想 每個文檔都可以用一系列關鍵詞來表示 如果按關鍵詞建立到文檔的索引便可以根據關鍵詞快速地檢索到相關文檔 倒排文件組成 詞匯表(Vocabulary) 根據Heaps定律,通常比較小O (n), : 0.40.6 通常我們稱存放詞匯表的文件為索引文件(index file) 出現位置(Occurrence) 較大,O(n),通常在原文本的3040 通常我們稱存放出現位置的文件為置入文件(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,倒排文件,塊地址索引 有時候為了節(jié)省索引空間,可按塊地址建索引 把原文劃分為多個塊,只記錄關鍵詞的塊地址,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,倒排文件,倒排文件的性能 時間代價主要取決于詞匯表的組織方式 詞表文件通常較小且比較固定 對于未登錄詞和數詞可以按字建索引 空間代價主要取決于對置入文件的壓縮能力 置入文件的壓縮能減少IO操作,也能提高部分時間性能 詞匯表文件的組織方式 采用Hash散列表 按字母表順序有序排列 采用Trie樹,B樹等查找樹 置入文件的壓縮 通常采用差值壓縮(delta compression),倒排文件,詞匯表的哈希存儲 根據給定的關鍵字,散列成一個整數 用該整數作為詞匯的訪問地址 例如:如果我們按字索引,那么可以直接用字的編碼 作為訪問地址,對于2字節(jié)編碼只需64K地址 優(yōu)點 實現簡單 速度極快 缺點 關鍵在于找到一個好的散列函數 隨著現在散列空間的增大,問題相對簡單 當沖突過多時效率會下降,倒排文件,詞匯表的順序排列 把詞匯按照字典順序排列 詞匯的查找采用二分查找 優(yōu)點 實現簡單 詞匯表體積?。ㄍǔV挥袔渍祝?缺點 索引構建的效率一般 對于插入的文檔需要反復地調用排序和查找算法 排序的時間復雜度為N*log N (分配排序例外) 索引合并時還需要堆排序等方法合并多個有序的詞匯表 如果合并最主要的時間開銷在于IO操作的話,這點還是次要的 檢索的效率一般 二分查找logN的復雜度已經具有較好的效率 能不能變成和詞匯數量無關的常數復雜度,倒排文件,Lucene的詞匯表即采用這種方式 假設現在詞表中有16,000個詞 indexInterval=16 則在詞表中需要查找次數為16log(1000) = 26次,倒排文件,詞匯表的查找樹 把詞匯表中的關鍵詞以樹的形式組織 二叉樹,B樹,Trie 等 二叉查找樹 考慮到平衡性,性能低于二分查找 B樹 是多路查找樹,效率高于二叉樹,實現更麻煩 Trie 樹 查找時間只跟詞的長度有關 而于詞表中詞的個數無關 詞表較大時才能體現出速度優(yōu)勢 Log (詞表長度) E(詞長) E表示期望,Trie樹,什么是trie樹 trie樹是一種用于快速檢索的多叉樹結構 trie樹把要查找的關鍵詞看作一個字符序列。 根據這一序列構造用于檢索的樹結構。 在trie樹上進行檢索類似于查閱英語詞典。 例如,電子英文詞典,為了方便用戶快速檢索英語單詞,可以建立一棵trie樹。,詞典單詞:a、b、c、aa、ab、ac、ba、ca、 aba、abc、baa、bab、bac、cab、abba、baba、caba、abaca、caaba,Trie樹,優(yōu)點 查找效率高,與詞表長度無關 Trie樹的查找效率只與關鍵詞長度有關 目前我們分詞詞表最長的詞為13個字 “大不列顛及北愛爾蘭聯合王國” 事實上索引詞表中詞過長會降低檢索召回率 用戶如果只輸入“北愛爾蘭”則無法返回該結果 索引的插入,合并速度快 注意,直接遍歷Trie樹需要搜索大量的無效節(jié)點 可以把數據存在一個數組中,Trie只保存指針 這樣合并時,只需要對數組進行遍歷即可 缺點 所需空間較大 如果是完全m叉樹,節(jié)點數指數級增長 好在Trie不是,但所需空間仍然很大 不可達上限: 詞數 字符序列長度 字符集大小 指針長度 例如:20000 6 256 4 120M 實現較復雜,差值壓縮(Delta Compression),置入文件 置入文件必須包含如下信息 當前詞出現的文檔號ID,以及在文檔中的位置Pos 差值壓縮 記錄當前ID和前一ID的差值 記錄當前Pos和前一Pos的差值 這樣做能有效減少表示ID,Pos所需的字長 例如:關鍵詞A在文檔13,124,346中出現 如果不壓縮,由于346256,需要要兩個字節(jié) 而346124222256,只需一個字節(jié) 應用實例 Lucene對詞匯表和置入文件都采用了這種壓縮,PAT樹(Patricia tree),什么是Patricia樹 Patricia樹是Trie樹的壓縮表示 所有只有一個子節(jié)點的節(jié)點都和父節(jié)點合并 后綴樹(Suffix tree) 以文本所有后綴為關鍵詞的Patricia樹 后綴樹的引入主要是針對字符串的高效查找 子串查找 最長重復子串 最長公共子串 回文子串 后綴數組(Suffix array) 按后綴樹的先根遍歷順序,存儲后綴,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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論