信息組織與檢索第七章索引和搜索教學提綱

第7章索引(suǒyǐn)和搜索查詢的實現(xiàn)靠搜索快速搜索需要索引本章內(nèi)容：文本(wénběn)索引和搜索技術(shù)索引：倒排文件、后綴數(shù)組和簽名文件搜索：文本(wénběn)順序查找算法、模式匹配、對壓縮文本(wénběn)的搜索第一頁，共44頁。2023/1/131第7章本章(běnzhānɡ)內(nèi)容7.1為什么需要索引7.2倒排索引7.3后綴索引7.4簽名文件7.5順序(shùnxù)查找和模板匹配7.6對壓縮文本的搜索7.7小結(jié)第二頁，共44頁。2023/1/1327.1為什么需要(xūyào)索引順序搜索適合于文本庫的規(guī)模比較小、變化頻繁、對實時性要求(yāoqiú)比較高的場合又稱為在線搜索基于索引的搜索適合大規(guī)模、穩(wěn)定的或周期性變化的文本文檔庫（集）第三頁，共44頁。2023/1/1337.2倒排索引(suǒyǐn)一、什么是倒排索引稱為：倒排（Inverted）文件(wénjiàn)、倒排索引、倒排表是一種索引數(shù)據(jù)結(jié)構(gòu)組成：詞表（或稱為詞典）事件表（或稱為置入表）。第四頁，共44頁。2023/1/1347.2倒排索引(suǒyǐn)詞表文本中所包含的不同詞的集合。事件表對于詞表中的詞，一個(yīɡè)列表存儲了其在文檔中所有的出現(xiàn)位置。所有這些列表的集合被稱為“事件表”第五頁，共44頁。2023/1/1357.2倒排索引(suǒyǐn)第六頁，共44頁。2023/1/1367.2倒排索引(suǒyǐn)倒排文件和倒排表的概念區(qū)分一個倒排文件中，列表中的每一項指向文檔或文件名倒排表的每一項指向文檔內(nèi)部的詞或字符(zìfú)的位置。這只不過是一粒度的問題尋址的文本塊可以大到文檔，也可以小到一個單詞或一個字符(zìfú)第七頁，共44頁。2023/1/1377.2倒排索引(suǒyǐn)第八頁，共44頁。2023/1/1387.2倒排索引(suǒyǐn)二、利用倒排文件進行搜索詞表搜索。將查詢(cháxún)表達式中的單詞或模式分離出來，并在詞表中進行查找；事件表處理。對事件表中所有出現(xiàn)的位置進行相應的處理，定位到查詢(cháxún)結(jié)果；事件表上的操作。在事件表上進行處理，以實現(xiàn)詞組查詢(cháxún)、鄰近查詢(cháxún)或布爾操作。第九頁，共44頁。2023/1/1397.2倒排索引(suǒyǐn)DocumentVectorsDocumentsarerepresentedas“bagsofwords”RepresentedasvectorswhenusedcomputationallyAvectorislikeanarrayoffloatingpointHasdirectionandmagnitudeEachvectorholdsaplaceforeveryterminthecollectionTherefore,mostvectorsaresparse第十頁，共44頁。2023/1/13107.2倒排索引(suǒyǐn)nova galaxy heat h’wood film role diet fur10 5 3 5 10 10 8 7 9 10 5 10 10 9 105 7 9 6 10 2 8 7 5 1 3ABCDEFGHI“Nova”occurs10timesintextA“Galaxy”occurs5timesintextA“Heat”occurs3timesintextA(Blankmeans0occurrences.)第十一頁，共44頁。2023/1/13117.2倒排索引(suǒyǐn)nova galaxy heat h’wood film role diet fur10 5 3 5 10 10 8 7 9 10 5 10 10 9 105 7 9 6 10 2 8 7 5 1 3ABCDEFGHI“Hollywood”occurs7timesintextI“Film”occurs5timesintextI“Diet”occurs1timeintextI“Fur”occurs3timesintextI第十二頁，共44頁。2023/1/13127.2倒排索引(suǒyǐn)nova galaxy heat h’wood film role diet fur10 5 3 5 10 10 8 7 9 10 5 10 10 9 105 7 9 6 10 2 8 7 5 1 3ABCDEFGHIDocumentids第十三頁，共44頁。2023/1/13137.2倒排索引(suǒyǐn)StarDietDocaboutastronomyDocaboutmoviestarsDocaboutmammalbehavior第十四頁，共44頁。2023/1/13147.2倒排索引(suǒyǐn)InvertedIndexThisistheprimarydatastructurefortextindexesMainIdea:InvertdocumentsintoabigindexBasicsteps:Makea“dictionary”ofallthetokensinthecollectionForeachtoken,listallthedocsitoccursin.Doafewthingstoreduceredundancyinthedatastructure第十五頁，共44頁。2023/1/13157.2倒排索引(suǒyǐn)Wehaveseen“Vectorfiles”conceptually.AnInvertedFileisavectorfile“inverted”sothatrowsbecomecolumnsandcolumnsbecomerows第十六頁，共44頁。2023/1/13167.2倒排索引(suǒyǐn)HowAreInvertedFilesCreated?Documentsareparsedtoextracttokens.ThesearesavedwiththeDocumentID.NowisthetimeforallgoodmentocometotheaidoftheircountryDoc1Itwasadarkandstormynightinthecountrymanor.ThetimewaspastmidnightDoc2第十七頁，共44頁。2023/1/13177.2倒排索引(suǒyǐn)HowInvertedFilesareCreatedAfteralldocumentshavebeenparsedtheinvertedfileissortedalphabetically.第十八頁，共44頁。2023/1/13187.2倒排索引(suǒyǐn)HowInvertedFilesareCreatedMultipletermentriesforasingledocumentaremerged.Within-documenttermfrequencyinformationiscompiled.第十九頁，共44頁。2023/1/13197.2倒排索引(suǒyǐn)ThenthefilecanbesplitintoADictionaryfileandAPostings

file第二十頁，共44頁。2023/1/13207.2倒排索引(suǒyǐn)Dictionary Postings第二十一頁，共44頁。2023/1/13217.2倒排索引(suǒyǐn)PermitfastsearchforindividualtermsForeachterm,yougetalistconsistingof:documentIDfrequencyoftermindoc(optional)positionoftermindoc(optional)TheselistscanbeusedtosolveBooleanqueries:country->d1,d2manor->d2countryANDmanor->d2Alsousedforstatisticalrankingalgorithms第二十二頁，共44頁。2023/1/13227.2倒排索引(suǒyǐn)Queryon“time”AND“dark”2docswith“time”indictionary-> IDs1and2frompostingfile1docwith“dark”indictionary-> ID2frompostingfileTherefore,onlydoc2satisfiedthequery.Dictionary Postings第二十三頁，共44頁。2023/1/13237.3后綴(hòuzhuì)索引一、什么是后綴后綴：文本中的每個位置被認為是文本的一個后綴，即從當前文本位置到文本末尾的字符串起始(qǐshǐ)位置不同的兩個后綴，其依照字典順序也是不同的每個后綴由它的位置唯一地標識第二十四頁，共44頁。2023/1/13247.3后綴(hòuzhuì)索引第二十五頁，共44頁。2023/1/13257.3后綴(hòuzhuì)索引二、后綴樹和后綴數(shù)組一個后綴樹是一種trie樹數(shù)據(jù)結(jié)構(gòu)，在trie樹上表示文本的所有后綴為提高空間利用率，這個trie被壓縮成為一個Patricia樹，包括壓縮一元路徑然而，這種結(jié)構(gòu)的主要問題是空間問題后綴數(shù)組提供了與后綴樹相同的功能，但其空間需求(xūqiú)要遠小于后綴樹后綴數(shù)組是后綴樹的一種有效實現(xiàn)第二十六頁，共44頁。2023/1/13267.3后綴(hòuzhuì)索引第二十七頁，共44頁。2023/1/13277.3后綴(hòuzhuì)索引后綴數(shù)組就是簡單按照字典的順序，存儲所有文本后綴指針的數(shù)組因為每個被索引的后綴只存儲一個指針，其空間需求幾乎與倒排索引相同對于大型的后綴數(shù)組，為了提高存取效率，可以在后綴數(shù)組之上，建立上部索引來加速存取后綴數(shù)組和倒排索引的區(qū)別在倒排索引中，每個單詞事件表的順序是按照單詞在文本中的出現(xiàn)順序排列的；而在后綴數(shù)組中，是按照文本中跟隨單詞的字典序列(xùliè)排序的第二十八頁，共44頁。2023/1/13287.3后綴(hòuzhuì)索引第二十九頁，共44頁。2023/1/13297.3后綴(hòuzhuì)索引第三十頁，共44頁。2023/1/13307.4簽名文件一、簽名索引機制使用哈希函數(shù)，將詞映射為掩碼（簽名）把文本劃分為若干塊，每塊有b個詞。每個文本塊的大小是b，并賦予B位的掩碼。掩碼是通過(tōngguò)對文本塊中的所有詞的簽名進行比特OR操作獲得的。簽名文件所有文本數(shù)據(jù)塊的位掩碼序列，包括每個塊的指針第三十一頁，共44頁。2023/1/13317.4簽名文件簽名文件的主要思想是如果某個詞出現(xiàn)在一個文本塊內(nèi)，則簽名文件中的所有(suǒyǒu)比特位也會在這個文本塊的位掩碼之中。如果查詢詞的掩碼中的一個比特不在文本塊的掩碼中，那么可以說這個詞就不會出現(xiàn)在文本塊中第三十二頁，共44頁。2023/1/13327.4簽名文件例子塊3里有crowded和people兩個需要被索引的詞其掩碼位分別是001100和100100對這兩個掩碼進行(jìnxíng)OR操作則塊3的掩碼就是101100第三十三頁，共44頁。2023/1/13337.4簽名文件第三十四頁，共44頁。2023/1/13347.4簽名文件二、利用簽名文件進行搜索執(zhí)行哈希變換，將這個詞轉(zhuǎn)換(zhuǎnhuàn)為位掩碼W與文本中的每個塊的位掩碼Bi進行比較，即執(zhí)行WANDBi操作；若其結(jié)果為W，則說明在這個文本塊中可能存在多個要求的查詢詞；對于所有侯選的文本塊，執(zhí)行在線的遍歷，以檢驗查詢詞是否真實地存在其中第三十五頁，共44頁。2023/1/13357.4簽名文件例子查找wear這個詞，其掩碼位為000101。對五個塊的掩碼進行比較，只有在第四個塊中能滿足100101AND000101=000101則說明在第四個文本塊中至少存在一個wear。然后，順序搜索該文本塊，最終確定(quèdìng)wear的存在及其位置第三十六頁，共44頁。2023/1/13367.5順序搜索和模板(múbǎn)匹配一、順序搜索當不在文本(wénběn)上建立任何數(shù)據(jù)結(jié)構(gòu)時，對文本(wénběn)進行查找常用算法布魯特-福斯（BruteForce）算法克魯什-莫里斯-普拉特（Knuth-Morris-Pratt）算法博葉-摩爾（Boyer-Moore）算法第三十七頁，共44頁。2023/1/13377.5順序查找(cházhǎo)和模板匹配二、模式匹配與順序搜索順序搜索順序搜索是指不利用索引對文本進行(jìnxíng)搜索，通過精確的串匹配，得到要求查找的項。即在文本T中找到模式P出現(xiàn)的所有位置。這實際上是一種簡單形式的模式匹配。第三十八頁，共44頁。2023/1/13387.5順序查找(cházhǎo)和模板匹配二、模式匹配與順序搜索模式匹配模式匹配還包括復雜形式的模式匹配，它允許具有一定(yīdìng)誤差的匹配，或稱為近似字符串匹配；或?qū)U展模式（見第6章）進行匹配對于長度為m的短模式P與長度為n的長文本T，假設允許的匹配誤差為k，模式匹配就是從文本T中，找出小于等于誤差條件的所有的模式P出現(xiàn)的文本位置。可以用Levenshtein距離來度量串之間的距離。第三十九頁，共44頁。2023/1/13397.6對壓縮文本(wénběn)的搜索直接對壓縮的文本和索引進行搜索根據(jù)：壓縮數(shù)據(jù)中包含有直接或間接可以利用的可搜索信息和特征，使得搜