正排索引(forward index)与倒排索引(inverted index)
一、正排索引（前向索引）
正排索引也稱為"前向索引"。它是創(chuàng)建倒排索引的基礎(chǔ)，具有以下字段。
（1）LocalId字段（表中簡(jiǎn)稱"Lid"）：表示一個(gè)文檔的局部編號(hào)。
（2）WordId字段：表示文檔分詞后的編號(hào)，也可稱為"索引詞編號(hào)"。
（3）NHits字段：表示某個(gè)索引詞在文檔中出現(xiàn)的次數(shù)。
（4）HitList變長(zhǎng)字段：表示某個(gè)索引詞在文檔中出現(xiàn)的位置，即相對(duì)于正文的偏移量。
由于一篇文章中的某些詞可能出現(xiàn)多次，而且位置不同，而全文檢索的本質(zhì)要求是把這些位置標(biāo)識(shí)出來，因此HitList中的每個(gè)命中都表示索引詞在文檔的某個(gè)位置中出現(xiàn)了一次，這個(gè)序列為單調(diào)遞增序列。基于游程編碼的方法，變升序序列為差分序列，采用前文提到的Variable Byte Coding方法編碼可以大大壓縮正排索引的HitList字段。
在正排索引中LocalId采用升序序列編號(hào)（假定編號(hào)采用自增1的方式遞增），這為下面的計(jì)算創(chuàng)造條件。進(jìn)行倒排索引的轉(zhuǎn)化時(shí)，由于正排索引中Lid天然的有序性，因此在正排索引轉(zhuǎn)化為倒排索引的創(chuàng)建過程中，自然可以保證倒排索引中每個(gè)詞匯對(duì)應(yīng)的文檔編號(hào)也是有序的，倒排索引將在下一節(jié)中介紹。
這樣，正排索引如圖4-3所示。
| ? |
| 圖4-3? 正排索引 |
| ? |
| 圖4-4? 正排索引示例 |
HitList是變長(zhǎng)的，因此需要NHits這個(gè)字段標(biāo)記其長(zhǎng)度，這樣才能讀出全部的正排索引數(shù)據(jù)。假定每個(gè)域都是一個(gè)字節(jié)大小，而HitList變長(zhǎng)。在上面這個(gè)例子中，假定這個(gè)正排索引依次存放在一個(gè)數(shù)組Array中，則當(dāng)讀取到Array[2]時(shí)，讀取的內(nèi)容為T1的NHits，讀出的結(jié)果為1。由于T1出現(xiàn)了1次，因此在T1的HitList中僅存放了一個(gè)位置信息。這樣在讀取Array[3]后，接下來讀取Array[4]則能夠判斷為下一個(gè)索引詞T2。正是由于NHits的這種表示長(zhǎng)度的作用，全部的數(shù)據(jù)才能被有效地讀取。
最后用NULL表示為一個(gè)結(jié)束符的這種設(shè)計(jì)是很巧妙的；否則，正排索引可能是這樣，如圖4-5所示。
| ? |
| 圖4-5? 冗余存放DocId的正排索引 |
在圖4-5中，為了結(jié)構(gòu)化數(shù)據(jù)的需要，在去掉表示結(jié)束符的NULL后，正排索引必須冗余地存放DocId，因此一個(gè)標(biāo)記結(jié)束符的字段有效地壓縮了正排索引的大小。
本質(zhì)上說，正排索引以文檔編號(hào)為視角看待索引詞，也就是通過文檔編號(hào)去找索引詞。任給一個(gè)文檔編號(hào)，能夠知道它包含了哪些索引詞、這些索引詞分別出現(xiàn)的次數(shù)，以及索引詞出現(xiàn)的位置。然而全文索引是通過關(guān)鍵詞來檢索，而不是通過文檔編號(hào)來檢索，因此正排索引不能滿足全文檢索的要求。
雖然正排索引不能滿足全文檢索的需要，但是正排索引為創(chuàng)建倒排索引創(chuàng)造了有利條件，是計(jì)算倒排索引的不可缺少的一環(huán)。
二、倒排索引
倒排索引是一種以關(guān)鍵字和文檔編號(hào)結(jié)合，并以關(guān)鍵字作為主鍵的索引結(jié)構(gòu)。倒排索引分為兩個(gè)部分。
（1）第1個(gè)部分：由不同索引詞（index term）組成的索引表，稱為"詞典"（lexicon）。其中保存了各種中文詞匯，以及這些詞匯的一些統(tǒng)計(jì)信息（例如出現(xiàn)頻率nDocs），這些統(tǒng)計(jì)信息用于各種排名算法（Ranking Algorithm） [Salton 1989;Witten 1994]
（2）第2個(gè)部分：由每個(gè)索引詞出現(xiàn)過的文檔集合，以及命中位置等信息構(gòu)成，也稱為"記錄表"（posting file）或"記錄列表"（posting list）。如圖4-6所示。
| ? |
| （點(diǎn)擊查看大圖）圖4-6? 倒排索引 |
左邊的表結(jié)構(gòu)（詞典）記錄索引詞Id號(hào)、匹配該索引詞的文檔數(shù)量，并匹配文檔在記錄文件內(nèi)的偏移量，通過這個(gè)偏移量就可以讀取記錄文件對(duì)應(yīng)區(qū)域的信息。例如在圖4-6中，通過讀取T1的偏移量x，讀取在記錄文件中T1命中的相關(guān)文檔Doc1、Doc2和Doc3的相關(guān)信息。
右邊的表結(jié)構(gòu)（記錄表）記錄文檔編號(hào)（DocId）、索引詞在該文檔的命中個(gè)數(shù)（NHits），以及命中域的列表（HitList）。例如在圖4-6中，記錄文件顯示了T2關(guān)鍵詞在Doc1中出現(xiàn)了3次。
圖4-6所示的倒排索引示例中，以索引詞T2為例，T2在兩個(gè)文檔中出現(xiàn)。通過偏移量在記錄文件中找到了存放與T2有關(guān)的信息，即T2匹配的Doc1和Doc2兩個(gè)文檔，并且在Doc1中出現(xiàn)了3次，位置分別為3、5和7（圖中3、2和2表示為差分序列后的實(shí)際值，即3、5-3和7-5）。
注意到這種按照索引詞組織文檔的方式，在索引詞WordId一邊，其Id號(hào)不會(huì)重復(fù)；而在DocId一邊，由于每個(gè)文檔都可能包含多個(gè)索引詞，DocId的重復(fù)非常普遍，因此對(duì)DocId就需要進(jìn)行大規(guī)模的壓縮。
壓縮編碼也采用Variable Byte Coding編碼方法進(jìn)行壓縮，首先對(duì)DocId排序，接下來將DocId的遞增序列為差分序列，最后用Variable Byte Coding編碼方法進(jìn)行壓縮編碼。例如這樣的DocId序列（22，5，9，1），通過排序得到（1，5，9，22），變差分序列得到（1，4，4，13），壓縮編碼后得到（2，8，8，26），對(duì)于小于128的數(shù)進(jìn)行壓縮編碼，相當(dāng)于乘2（詳細(xì)參見本章第三節(jié)中的相關(guān)內(nèi)容）。
最后，在倒排索引中，按照何種順序存放DocId更加有利于檢索呢？在圖4-6中，T1這個(gè)詞有Doc1、Doc2、Doc3與之相匹配，也就是在這些文檔中都出現(xiàn)了T1，那么在倒排索引的記錄表中，哪個(gè)文檔編號(hào)先存放，哪個(gè)文檔編號(hào)后存放呢？這種存放順序的策略大致有如下3種。
（1）按照DocId升序存放。
（2）按照索引詞在文檔中出現(xiàn)次數(shù)降序存放。
（3）記錄表分塊存放，塊內(nèi)按DocId升序存放，塊間按PageRank值降序存放。
對(duì)于方案1來說，它有助于在多關(guān)鍵詞查詢中，得到相同的DocId（在第六章中介紹查詢系統(tǒng)時(shí)，會(huì)提到因?yàn)镈ocId有序而為查詢帶來的好處）。并且能夠?qū)ocId進(jìn)行壓縮編碼，同時(shí)降低磁盤I/O的開銷。
對(duì)于方案2來說，按照索引詞Id在文檔中出現(xiàn)的次數(shù)降序排序，因?yàn)樗饕~出現(xiàn)次數(shù)多的文檔與查詢關(guān)鍵詞的相關(guān)性越好（這里，索引詞和關(guān)鍵詞是同一個(gè)詞，在索引系統(tǒng)中稱為"索引詞"，在查詢系統(tǒng)中稱為"關(guān)鍵詞"或"查詢?cè)~"），這是很自然的，檢索就是檢索哪些與查詢?cè)~相關(guān)性高的文檔。文獻(xiàn)[S. Brin 1998]闡述了一種折中的設(shè)計(jì)方案，即不同的索引詞命中區(qū)分對(duì)待，對(duì)于索引詞在標(biāo)題或者錨文本（Anchor）命中的文檔，以及命中信息存放在一個(gè)記錄表中，不妨稱為"表A"，表內(nèi)數(shù)據(jù)按DocId排序；命中其他位置的文檔及其命中信息存放在另一個(gè)記錄表中，稱為"表B"，同樣表內(nèi)數(shù)據(jù)也是按照DocId排序。這樣對(duì)于每個(gè)索引詞的查詢，優(yōu)先在表A中查詢。只有當(dāng)結(jié)果數(shù)不夠時(shí)，再到表B中查詢。這樣既照顧到了壓縮存儲(chǔ)的需要，也照顧到了相關(guān)性，通常標(biāo)題中的詞大多在正文中會(huì)多次出現(xiàn)。當(dāng)然這種折中的方法有時(shí)也不夠合理，它過分倚重于錨文本的關(guān)鍵詞，常常被針對(duì)這種算法作弊的網(wǎng)頁設(shè)計(jì)者利用。
對(duì)于方案3來說，一方面照顧到了方案1的索引壓縮功能（文檔按序存儲(chǔ)）；另一方面照顧了重要的文檔在檢索過程中優(yōu)先被檢索的需要，而且防止了方案2中由網(wǎng)頁設(shè)計(jì)者作弊可能帶來的麻煩。有些網(wǎng)頁設(shè)計(jì)者在網(wǎng)頁中正文，錨文本中堆砌大量經(jīng)常被查詢的重要關(guān)鍵詞，因此方案2在設(shè)計(jì)上不可避免的缺陷容易被利用。當(dāng)然PageRank算法也會(huì)被作弊者利用，然而PageRank的作弊較為困難，所以方案3是較為理想的解決方案。
最后，總結(jié)一下正排索引和倒排索引的關(guān)系。本質(zhì)上說，存在這樣兩個(gè)空間，一個(gè)稱為"索引詞空間"，一個(gè)稱為"文檔空間"。正排索引可以理解成一個(gè)定義在文檔空間到索引詞組空間的一個(gè)映射，任意一個(gè)文檔對(duì)應(yīng)唯一的一組索引詞；而倒排索引可以理解成一個(gè)定義在索引詞空間到文檔組空間的一個(gè)映射。任意一個(gè)索引詞對(duì)應(yīng)唯一的一組該索引詞其命中的文檔。因此從文檔到正排索引，進(jìn)而從正排索引到倒排索引就是理順這種關(guān)系的過程。使得給出一個(gè)索引詞，就能通過倒排索引能夠找到其命中的文檔，以及位置信息。
from: http://book.51cto.com/art/201105/262903.htm
總結(jié)
以上是生活随笔為你收集整理的正排索引(forward index)与倒排索引(inverted index)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 搜索引擎-倒排索引基础知识
- 下一篇： 分享一些优秀有趣的博客