第二十六課倒排索引基本概念

單詞——文檔矩3-1的每列代表一個文檔，每行代表一個單詞，打?qū)吹奈?-1單詞-從縱向即文檔這個維度來看，每列代表文檔包含了哪些單詞，比如文檔114，而不包含其它單詞。從橫向即單詞這個維度來看，每行代表了哪些文檔包含了某個單詞。比如對于詞匯1來說，文檔1和文檔4中11。矩陣中其它的行列也可作此種解搜索引擎的索引其實就是實現(xiàn)“單詞-”的具體數(shù)據(jù)結(jié)構(gòu)?？梢杂胁煌姆绞絹韺崿F(xiàn)上述概念模型，比如“”、“簽名文件”、“”等方式。但是各項實驗數(shù)據(jù)表明，“倒排索引”現(xiàn)方式，所以本章主要介紹“倒排索引”倒排索引基本概念要更寬泛些，代表以文本形式存在 對象，相比網(wǎng)頁來說，涵 形式，比如Word，PDF，html，XML等不同格式的文件都可以稱之為文檔。文檔集合(Collection)：由若干文檔構(gòu)成的集合稱之為文檔集文檔編號(ID)：在搜索引擎內(nèi)部，會將文檔集合內(nèi)每個文檔賦予理，每個文檔的內(nèi)部編號即稱之為“文檔編號”DocID來便捷地單詞編號(WordID)：與文檔編號類似，搜索引擎內(nèi)部以唯一的編號來表征倒排索引(InvertedIndex)：倒排索引是實現(xiàn)“單詞-文檔矩陣”的一種具體存倒排文件(InvertedFile)：所有單詞的倒排列表往往順序地在磁盤的某3-23-2倒排索引簡單實倒排索引從邏輯結(jié)構(gòu)和基本思來講非常簡單。下面我們通過具體實例3-3所示，在圖中最左端3-3倒排索引（3-4）3-4中，“單詞ID”一欄記錄了每個單詞的單詞編歌”1，倒排列表為{1,2,3,4,5}，說明文檔集合中每個文檔都包3-43-4所示倒排索引是最簡單的，是因為這個索引系統(tǒng)只記載了哪些文檔包含某個單詞，而事實上，索引系統(tǒng)還可以記錄除此之外的信3-53-4的基本索引系統(tǒng)比，在單3-5的例子里，單詞“創(chuàng)始人”7，對應(yīng)的倒排列表內(nèi)容為：（3:1），3代31313-5實用的倒排索引還可以記載的信息，圖3-6所示索引系統(tǒng)除了記錄文檔編號和單詞頻率信息外，額外記載了兩類信息，即每個單詞對應(yīng)的“息”（3-6的第三欄）以及在倒排列表中記錄單詞在某個文檔出現(xiàn)的位置

3-6以單詞“”為例，其單詞編號為8，文檔頻率為2，代表整個文檔集合中為在文檔3和文檔5出現(xiàn)過這個單詞，單詞頻率都為1，單詞“”在兩個文檔中的出現(xiàn)位置都是4，即文檔中第四個單詞是“”。類聚3-6所示倒排索引已經(jīng)是一個非常完備的索引系統(tǒng)，實際搜索系統(tǒng)的索引 單詞詞單詞詞典是倒排索引中非常重要的組成部分，它用來文檔集合中出現(xiàn)過的所有單主體部分是哈希表，每個哈希表項保存一個指針，指針指向鏈表，在鏈表里，相同哈的單詞形成鏈表結(jié)構(gòu)。之所以會有鏈表，是因為兩個不同單詞獲得相同的哈，如果是這樣，在哈希方法里被稱做是一次沖 1-7哈希加鏈表詞典結(jié)新文檔的時候，對于某個在文檔中出現(xiàn)的單詞T，首先利用哈希函數(shù)獲得其哈，之后根據(jù)哈對應(yīng)的哈希表項其中保存的指針，就找到了對應(yīng)的鏈表。如果鏈表里已經(jīng)存在這個單詞，說明單詞在之前解析的文檔里已經(jīng)出現(xiàn)過。如果在鏈表里沒有發(fā)現(xiàn)這個單詞，說明該單詞是首次碰到，則將其加入鏈表里。通過這種方式，當文檔集合內(nèi)所有文檔解析完畢時，1-7為例，假設(shè)用戶輸入的查32號槽，從其保留的指針可以獲得鏈表，依次將單詞3和鏈表內(nèi)的單詞比較，發(fā)現(xiàn)單詞3在鏈表內(nèi)，于是找到這個單詞，之后可以讀出這個單詞對應(yīng)的倒排列表樹形結(jié)意圖。B樹與哈希方式查找不同，需要字