倒排索引源于實(shí)際應(yīng)用中需要根據(jù)屬性的值來(lái)查找記錄。這種索引表中的每一項(xiàng)都包括一個(gè)屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來(lái)確定屬性值,而是由屬性值來(lái)確定記錄的位置,因而稱(chēng)為倒排索引(inverted index)。帶有倒排索引的文件我們稱(chēng)為倒排索引文件,簡(jiǎn)稱(chēng)倒排文件(inverted file)。
倒排列表概念
在實(shí)際的搜索引擎系統(tǒng)中,并不存儲(chǔ)倒排索引項(xiàng)中的實(shí)際文檔編號(hào),而是代之以文檔編號(hào)差值(D-Gap)。文檔編號(hào)差值是倒排列表中相鄰的兩個(gè)倒排索引項(xiàng)文檔編號(hào)的差值,一般在索引構(gòu)建過(guò)程中,可以保證倒排列表中后面出現(xiàn)的文檔編號(hào)大于之前出現(xiàn)的文檔編號(hào),所以文檔編號(hào)差值總是大于0的整數(shù)。如圖2所示的例子中,原始的 3個(gè)文檔編號(hào)分別是187、196和199,通過(guò)編號(hào)差值計(jì)算,在實(shí)際存儲(chǔ)的時(shí)候就轉(zhuǎn)化成了:187、9、3。
之所以要對(duì)文檔編號(hào)進(jìn)行差值計(jì)算,主要原因是為了更好地對(duì)數(shù)據(jù)進(jìn)行壓縮,原始文檔編號(hào)一般都是大數(shù)值,通過(guò)差值計(jì)算,就有效地將大數(shù)值轉(zhuǎn)換為了小數(shù)值,而這有助于增加數(shù)據(jù)的壓縮率。
倒排索引概念
一條記錄的水平反向索引(或者反向檔案索引)包含每個(gè)引用單詞的文檔的列表。
一個(gè)單詞的水平反向索引(或者完全反向索引)又包含每個(gè)單詞在一個(gè)文檔中的位置。
后者的形式提供了更多的兼容性(比如短語(yǔ)搜索),但是需要更多的時(shí)間和空間來(lái)創(chuàng)建。
現(xiàn)代搜索引擎的索引都是基于倒排索引。相比“簽名文件”、“后綴樹(shù)”等索引結(jié)構(gòu),“倒排索引”是實(shí)現(xiàn)單詞到文檔映射關(guān)系的最佳實(shí)現(xiàn)方式和最有效的索引結(jié)構(gòu)。