目標(biāo):存的下,查的塊
1.1 信息
信息是能夠被傳達(dá)和理解的信息.
1.2索引
索引也是一種信息,是信息的信息,描述信息的信息.eg目錄
1.3倒排索引,倒排表,臨時(shí)倒排文件,最終倒排文件
倒排表是指存放在內(nèi)存中的能夠追加倒排記錄的倒排索引。倒排表是迷你的倒排索引。
臨時(shí)倒排文件是指存放在磁盤中，以文件的形式存儲(chǔ)的不能夠追加倒排記錄的倒排索引。臨時(shí)倒排文件是中等規(guī)模的倒排索引。
最終倒排文件是指由存放在磁盤中，以文件的形式存儲(chǔ)的臨時(shí)倒排文件歸并得到的倒排索引。最終倒排文件是較大規(guī)模的倒排索引。
倒排索引作為抽象概念，而倒排表、臨時(shí)倒排文件、最終倒排文件是倒排索引的三種不同的表現(xiàn)形式。
1.4 其他概念
索引部分概念很多，因此本章4.2~4.4 節(jié)分別介紹全文檢索、文檔編號(hào)、正排索引、倒排索引的基本概念。在集中理解索引系統(tǒng)的主要概念后，接下來再了解索引創(chuàng)建中的一些計(jì)算細(xì)節(jié)。
2 全文檢索
全文檢索（full-text retrieval）技術(shù)的出現(xiàn)是信息檢索領(lǐng)域的一場(chǎng)革命，它細(xì)化了信息檢索的粒度，提供了實(shí)現(xiàn)多角度，多側(cè)面且全新的信息檢索體驗(yàn)。因此搜索引擎全面采用了這種嶄新的技術(shù)，并使之成為主流的檢索方法。
早期的信息檢索主要通過檢索數(shù)據(jù)信息的外部特征，例如標(biāo)題、作者、摘要、附錄及資料的編號(hào)等。這樣的檢索系統(tǒng)常見于圖書館的館藏圖書檢索中，它主要存在如下兩個(gè)大問題。
（1）檢索結(jié)果排序不理想。
（2）只能對(duì)標(biāo)題進(jìn)行檢索。
出現(xiàn)這些問題是因?yàn)闆]有考慮到文檔內(nèi)容（本章使用文檔籠統(tǒng)地代表書籍或者網(wǎng)頁）。全文檢索顧名思義，是對(duì)文檔的全部信息進(jìn)行檢索，這些信息包括標(biāo)題和正文等。簡(jiǎn)單地說，全文檢索的內(nèi)在本質(zhì)歸納起來就是如下兩條。
（1）文檔的全部文字參與索引。
（2）檢索結(jié)果能夠提供檢索詞出現(xiàn)的實(shí)際位置。
在全文檢索的過程中，只需要用戶提供一個(gè)或多個(gè)檢索關(guān)鍵詞,不僅能檢索出命中文本,還能提供關(guān)鍵詞出現(xiàn)在文本中的位置.
3.1 文檔編號(hào)
一個(gè)唯一描述文檔的Id.
檢索在索引的基礎(chǔ)上完成,得到一組匹配關(guān)鍵詞的文檔編號(hào).繼而文檔編號(hào)在文檔信息庫中取出,通過一系列計(jì)算戰(zhàn)士出來,文檔編號(hào)發(fā)揮重要作用.
3.2 文檔編號(hào)的方法
文檔編號(hào)需要滿足條件:
(1) 任何一個(gè)文檔在其生命周期只有一個(gè)編號(hào).
(2) 任何兩個(gè)不同文檔編號(hào)不同
(3) 編號(hào)在計(jì)算中盡可能高效,并且便于存儲(chǔ),越短越好
3.3 游戲編碼
使用這種方法進(jìn)行編號(hào)長(zhǎng)度壓縮.對(duì)于單調(diào)遞增的文件編碼,采用增量整數(shù)序列變?yōu)?差分編碼"
eg: 1, 16, 17, 35, 420, 23, 2944 表示的文檔編號(hào)分別為 ?前n項(xiàng)和.
好處:序列中的數(shù)字都比較小,便于存儲(chǔ)
壞處:獲取某個(gè)編碼需要從頭累加,且一旦卻是數(shù)據(jù)塊,那么后邊的編碼將無法計(jì)算
另一種變長(zhǎng)編碼(ariable Byte Coding)
這時(shí)一種字節(jié)對(duì)齊的編碼方式,將整數(shù)轉(zhuǎn)化為二進(jìn)制后,以7位為單位分段.每段段尾增加一位0表示最后一段,1表示還有后續(xù)段.
采用這種方式的好處是字節(jié)對(duì)齊,編碼和解碼都比較容易.
所以最終編碼方式為游戲編碼結(jié)合變長(zhǎng)編碼處理文檔編號(hào).
ps:變長(zhǎng)編碼的好處在于,將原先的差分編碼進(jìn)行優(yōu)化壓縮,減少小數(shù)字占用空間.
4 倒排索引
4.1 經(jīng)典的倒排索引
索引中的三個(gè)概念
命中率(Hit) 表示索引詞在文章中出現(xiàn)的位置和字體等信息
正排索引(Forward Index)
倒排索引(Inverted Index)
4.2 正排索引(前向索引)
正排索引是創(chuàng)建倒排索引的基礎(chǔ).具有以下字段
(1) LocalId表示文檔的局部編號(hào)
(2) WordId表示文檔分詞后的編號(hào),也稱"索引詞編號(hào)"
(3)NHits表示某個(gè)索引詞在文檔中出現(xiàn)的次數(shù)
(4)HitList表示某個(gè)索引詞在文檔出現(xiàn)的位置,相對(duì)于正文的偏移量(基于游戲編碼的差分序列,采用變長(zhǎng)編碼的方式處理)
正排索引以文檔編號(hào)為視角看待索引詞,也就是通過文檔編號(hào)找索引詞.
然而全文檢索的特性是通過關(guān)鍵詞來檢索,而不是通過文檔編號(hào)來檢索,因此正排不能滿足全文索引要求,但是卻為倒排索引創(chuàng)造了有力條件
4.3 倒排索引
倒排索引是一種以關(guān)鍵字和文件編號(hào)結(jié)合,并以關(guān)鍵詞作為主鍵的索引結(jié)構(gòu)
倒排索引兩部分:
(1)由不同索引詞組成索引表,稱為 "詞典"
(2)由每個(gè)索引詞出現(xiàn)過的文檔以及命中位置等信息組成,稱為"記錄表"
倒排索引中的DocId存放順序問題.
三種策略
(1) 按照DocId升序
(2) 按照索引詞出現(xiàn)次數(shù)降序
(3) 記錄表分塊存放,塊內(nèi)按照DocId升序,塊間按照PageRank存放
第三種方案既照顧了(1) 的有序壓縮問題,又照顧了重要文檔優(yōu)先檢索的需要.
總結(jié):正排索引和倒排索引的關(guān)系
本質(zhì)講,存在這樣兩個(gè)空間,一個(gè)稱為索引詞空間,一個(gè)稱為文檔空間
正排索引理解為定義在文檔空間到索引空間的一個(gè)映射.任意一個(gè)文檔對(duì)應(yīng)唯一的一組索引詞
倒排索引理解為定義在索引空間到文檔空間的一個(gè)映射.任意一個(gè)索引詞對(duì)應(yīng)唯一命中文檔
因此,從文檔到正排索引,從正排索引到倒排索引可以理解為這種關(guān)系,給出一個(gè)索引詞,就可以通過倒排索引得到命中文檔及位置信息
5 數(shù)據(jù)規(guī)模的估計(jì)
對(duì)于tb數(shù)量級(jí)的文檔,單純的保存文檔編號(hào),就需要很大一部分空間,家生Hit等信息,那么就問題更大了.所以下邊主要涉及"
6 設(shè)計(jì)存儲(chǔ)規(guī)模的一些計(jì)算
6.1 正排表和倒排表的合并
下載系統(tǒng)將抓取的網(wǎng)頁存放在網(wǎng)頁庫中,分析系統(tǒng)在分析后得到網(wǎng)頁對(duì)象發(fā)送給索引系統(tǒng).因此,索引系統(tǒng)一直得到這樣的網(wǎng)頁對(duì)象
注:正排表和倒排表合并就是將正排表的數(shù)據(jù)追加到倒排表的數(shù)據(jù)過程,追加后,正排表不保留.而倒排在內(nèi)存中存儲(chǔ)一定的記錄后,成批順序?qū)懭氪疟P,成為臨時(shí)倒排文件
6.2 多個(gè)臨時(shí)倒排文件的歸并
方法:
(1) 拉鏈法和二路歸并
(2) 拉鏈法和多路歸并
歸并的方法:
(1) 從頭開始讀取兩個(gè)臨時(shí)倒排文件的一部分(eg每次讀取10MB)
(2) 分別對(duì)DocId進(jìn)行解壓,將解壓的差分序列還原成原始差分序列
(3) 進(jìn)行歸并操作
(4) 歸并結(jié)果進(jìn)行壓縮
(5) 寫入歸并后的臨時(shí)倒排文件1&2中
這種開鏈法采用的是處理大文件的一種通用思路,即每次僅取出大文件的一部分在內(nèi)存中進(jìn)行計(jì)算.
注:對(duì)于2路歸并,需要log(2)64,這樣對(duì)于一個(gè)大文件,會(huì)有太多的臨時(shí)文件產(chǎn)生.所以影響效率.于是使用多路歸并更好點(diǎn)
6.3 倒排索引分布式存儲(chǔ)
兩種方案
多索引節(jié)點(diǎn)(多主機(jī))方法:加快倒排文件創(chuàng)建速度;提高檢索效果
按照DocId進(jìn)行劃分結(jié)果稱為"局部倒排文件"
按照WordId 進(jìn)行劃分結(jié)果稱為"全局倒排文件"
注:全局/局部都是相對(duì)于索引詞來講的.
全局方案好處:索引一個(gè)詞,可能只需要訪問全部包含索引詞的節(jié)點(diǎn),
減少了磁盤I/O,當(dāng)檢索兩個(gè)詞時(shí),那么可以做到并發(fā)執(zhí)行(兩個(gè)節(jié)點(diǎn)),如果將索引看作是服務(wù),那么可以做到64個(gè)窗口同時(shí)提供服務(wù),局部方案則需要單窗口排隊(duì)服務(wù)
;局部方案則需要訪問所有部分包含索引詞的節(jié)點(diǎn).
缺點(diǎn):一蹦全崩;等待索引節(jié)點(diǎn)全部傳輸,速度慢,低效
局部方案:相對(duì)有利點(diǎn):(1)可靠性高,(2)降低網(wǎng)路負(fù)載,提高查詢效率
充分利用網(wǎng)絡(luò)寬帶,對(duì)于一個(gè)索引,并發(fā)傳輸
缺點(diǎn):單窗口排隊(duì)
所以:局部方案有利于并發(fā)獲取索引節(jié)果;全局方案有利于查詢.so 局部方案在查詢結(jié)果獲取方面是有優(yōu)勢(shì)的,且可靠性保證,因此業(yè)界使用.但當(dāng)檢索詞相對(duì)均勻分布時(shí),那么全局方式在性能上是最佳的
6.4 倒排文件緩存
6.5 倒排索引詞典統(tǒng)計(jì)信息的計(jì)算
在索引系統(tǒng)中,關(guān)于索引詞出現(xiàn)文檔數(shù)的統(tǒng)計(jì)是在查詢請(qǐng)求發(fā)生之前預(yù)先計(jì)算好的,是倒排表的詞典部分不可分割的一部分.--統(tǒng)計(jì)員(全局的)
7 倒排索引文件的創(chuàng)建過程
7.1 創(chuàng)建倒排表
![]()
單個(gè)索引節(jié)點(diǎn)倒排文件的創(chuàng)建過程
計(jì)算角度講,臨時(shí)倒排文件創(chuàng)建過程包括磁盤讀取(從網(wǎng)頁庫讀取一個(gè)文檔),計(jì)算(正排計(jì)算,歸并),寫入磁盤(寫入臨時(shí)倒排文件)
所以可以使用兩個(gè)線程并發(fā)處理,流水線方式
7.2 計(jì)算統(tǒng)計(jì)信息
方法1:從正排表開始統(tǒng)計(jì);(耗費(fèi)一定的內(nèi)存空間)
方法2:從臨時(shí)文件開始統(tǒng)計(jì);(需要等待最慢的索引節(jié)點(diǎn)計(jì)算完成后開始計(jì)算)
