倒排索引（Inverted File Index )
目前主流的索引技術(shù)有三種：倒排文件、后綴數(shù)組和簽名。后綴數(shù)組的方法雖然快，但是其維護(hù)困難，代價(jià)相當(dāng)高，不適合做引擎的索引。簽名是一種很好的索引方式，但倒排文件的速度和性能已經(jīng)超過了簽名。倒排文件是一種在各大搜索引擎中被主要使用的索引的方式，并且它也是搜索引擎中一個(gè)核心的技術(shù)。
（1）順排文件的建立
假設(shè)有網(wǎng)頁(yè)P(yáng)1,P2,……,Pn，給每個(gè)網(wǎng)頁(yè)文件賦予一個(gè)編號(hào)Pid，給每個(gè)關(guān)鍵字賦予一個(gè)編號(hào)keyi，假設(shè)key是網(wǎng)頁(yè)文件中的一個(gè)關(guān)鍵字，ni表示該關(guān)鍵字在網(wǎng)頁(yè)文件中出現(xiàn)的次數(shù)，<hit1,hit2,…,hitn>表示該關(guān)鍵字在網(wǎng)頁(yè)文件中的位置信息。首先將網(wǎng)頁(yè)內(nèi)容切分成一系列關(guān)鍵字：Pi={Key1,key2,…，keyn}。建立以下順排文件：
P1={[n1，Key1(hit1,hit2,…,hitn)],…,[nx，keyi（hit1,hit2,…,hitx）] }
P2={[n1，Key1(hit1,hit2,…,hitn)],…,[nn，keyk（hit1,hit2,…,hitn）] }
…………
Pn={[n1，Key1(hit1,hit2,…,hitn)],…,[ny，keyj（hit1,hit2,…,hity）] }
例如，對(duì)以下兩段文字進(jìn)行順排文件操作。
“隨著經(jīng)濟(jì)的發(fā)展，人們對(duì)生活的品質(zhì)要求越來越高。特別是在視覺欣賞方面，更是追求精益求精。如何把模糊的圖像變得清晰，把暗淡的色彩變得色彩鮮艷是一個(gè)非常值得研究的課題。并且在數(shù)字電視、掃描儀、醫(yī)療圖像、計(jì)算機(jī)視覺、衛(wèi)星監(jiān)測(cè)、航空攝像等方面對(duì)圖像的清晰度有著廣泛的需求。目前基于網(wǎng)格和密度的聚類方法已經(jīng)滲透到各個(gè)領(lǐng)域，且得到了令人意想不到的效果。本文是將基于網(wǎng)格和密度的聚類方法運(yùn)用到模糊圖像中，從而對(duì)圖像進(jìn)行增色處理。”
“數(shù)字圖像處理又稱為計(jì)算機(jī)圖像處理，它是指將圖像信號(hào)轉(zhuǎn)換成數(shù)字信號(hào)并利用計(jì)算機(jī)對(duì)其進(jìn)行處理的過程。數(shù)字圖像處理最早出現(xiàn)于20世紀(jì)50年代，當(dāng)時(shí)的電子計(jì)算機(jī)已經(jīng)發(fā)展到一定水平，人們開始利用計(jì)算機(jī)來處理圖形和圖像信息。數(shù)字圖像處理作為一門學(xué)科大約形成于20世紀(jì)60年代初期。早期的圖像處理的目的是改善圖像的質(zhì)量，它以人為對(duì)象，以改善人的視覺效果為目的。”
假設(shè)第一段文字是一個(gè)網(wǎng)頁(yè)P(yáng)1的全部?jī)?nèi)容，段首的起始位置為1。第二段文字是第二個(gè)網(wǎng)頁(yè)P(yáng)2的全部?jī)?nèi)容，段首的起始位置為1。
對(duì)網(wǎng)頁(yè)進(jìn)行自動(dòng)分詞，得到關(guān)鍵字以及關(guān)鍵字在網(wǎng)頁(yè)文件中出現(xiàn)的位置信息。順排文件的結(jié)果為：
P1={[1，經(jīng)濟(jì)（3）]，[1，發(fā)展（6）]，……，[2，視覺（26，93）]，……，[5，圖像（46，88，107，177，182）]，……，[1，處理（189）]}
P2={[4，數(shù)字（1，29，48，101）]，[8，圖像（3，13，21，49，96，103，130，140）]，……，[1，視覺（156）]，……，[2，目的（135，161）]}
（2）實(shí)現(xiàn)倒排文件的原理
順排文件是以網(wǎng)頁(yè)來索引關(guān)鍵字的，即形式為（網(wǎng)頁(yè)→關(guān)鍵字），不符合搜索引擎的需要。因此，需進(jìn)行倒排處理，以關(guān)鍵字來索引網(wǎng)頁(yè)，即形式為（關(guān)鍵字→網(wǎng)頁(yè)）：
Keyi→{[Pid1,ni1(hit1,hit2,…,hitni1)],…,[Pidn,nin(hit1,hit2,…,hitnin)]}
對(duì)以上順排文件中建立的兩個(gè)實(shí)例網(wǎng)頁(yè)P(yáng)1和P2的順排文件進(jìn)行倒排，倒排文件的結(jié)果為：
經(jīng)濟(jì)→{[P1，1（3）]}
發(fā)展→{[P1，1（6）]，[P2，1（74）]}
……
視覺→{[P1，2（26，93）]，[P2，1（156）]}
……
圖像→{[P1，5（46，88，107，177，182）]，[P2，8（3，13，21，49，96，103，130，140）]}
……
綜上所述，倒排文件的實(shí)現(xiàn)過程是：先得到順排文件，然后根據(jù)順排文件得到倒排文件，從而實(shí)現(xiàn)由關(guān)鍵字來索引網(wǎng)頁(yè)。
（3）倒排文件的優(yōu)化之一—位圖文件
在實(shí)際中，一般索引項(xiàng)并不存儲(chǔ)實(shí)際的關(guān)鍵字，而存儲(chǔ)它的一個(gè)編號(hào)值（kid），這樣可以有效節(jié)約存儲(chǔ)空間。對(duì)于文件鏈表（Posting），只存儲(chǔ)網(wǎng)頁(yè)文件編號(hào)（Pid）和網(wǎng)頁(yè)文件編號(hào)加上該關(guān)鍵字在文件中出現(xiàn)的位置信息。
其中Pid1,…,Pidn表示包含關(guān)鍵字ki的所有網(wǎng)頁(yè)文件集合，考慮到文件鏈表進(jìn)行布爾運(yùn)算時(shí)，速度不是很快，以及使用文件鏈表要消耗大量?jī)?nèi)存等問題，一般采用位圖（Bitmap）文件來實(shí)現(xiàn)倒排索引。Bitmap的優(yōu)點(diǎn)是布爾運(yùn)算非常快，直接用對(duì)應(yīng)的bit位作運(yùn)算就可以了。想要得到同時(shí)包含某幾個(gè)關(guān)鍵字的網(wǎng)頁(yè)，那么直接把它們對(duì)應(yīng)的網(wǎng)頁(yè)文件位圖向量進(jìn)行與運(yùn)算，就可以知道在哪些文件中同時(shí)包含了這幾個(gè)關(guān)鍵字。在文件數(shù)目不是很多的情況下，只存儲(chǔ)命中信息，實(shí)現(xiàn)了命中信息和非命中信息（比如關(guān)鍵字在文件中的位置，關(guān)鍵字在文件中出現(xiàn)的頻率等）的分離，可以大大提高索引的效率。
把由網(wǎng)頁(yè)文件向量Pi=<key1,key2,…,keyn>構(gòu)成的“網(wǎng)頁(yè)→關(guān)鍵字”，轉(zhuǎn)化成“關(guān)鍵字→網(wǎng)頁(yè)”。轉(zhuǎn)換方法是根據(jù)網(wǎng)頁(yè)文件向量構(gòu)成“網(wǎng)頁(yè)-關(guān)鍵字”陣列，如圖5-2所示，并用Bitmap作為存儲(chǔ)結(jié)構(gòu)，形成倒排矩陣A，如圖5-3所示。
倒排矩陣中的Aij元素取值為0，表示網(wǎng)頁(yè)P(yáng)j中沒有關(guān)鍵字ki；倒排矩陣中的Aij元素取值為1，表示網(wǎng)頁(yè)P(yáng)j中有關(guān)鍵字ki。以此可以得到包含某關(guān)鍵字的網(wǎng)頁(yè)的文件集合，然后根據(jù)文件鏈表得到此關(guān)鍵字在網(wǎng)頁(yè)中的出現(xiàn)位置信息。
| ? |
Bitmap文件實(shí)現(xiàn)的倒排矩陣在海量數(shù)據(jù)環(huán)境下是比較稀疏的，必須對(duì)它進(jìn)行壓縮，并且保證在解壓的過程中，速度也比較快，這樣可以大大提高索引的性能，也節(jié)省了大量的存儲(chǔ)空間。目前比較成熟的位圖壓縮算法主要有Delta encoding、Variable-length encoding、Gamma codes等。
雖然它們都是比較成熟的算法，但是要么實(shí)現(xiàn)起來比較復(fù)雜；要么壓縮效率很高，但是解壓的過程要消耗較長(zhǎng)的時(shí)間，這對(duì)于搜索引擎的實(shí)時(shí)響應(yīng)要求很高的系統(tǒng)是不適合的。
2．改善倒排文件性能的方法
倒排文件的時(shí)間代價(jià)主要取決于詞匯表的組織方式，詞匯表文件通常較小且比較固定，對(duì)于未登錄詞和數(shù)詞可以按字建索引；倒排文件的空間代價(jià)主要取決于對(duì)事件表的壓縮能力，事件表的壓縮能減少I/O操作，也能提高部分時(shí)間性能。詞匯表文件的組織方式通常采用Hash散列表，按字母表順序有序排列，采用Trie樹、B樹等查找樹。事件表的壓縮通常采用Bitmap文件壓縮或差值壓縮（Delta Compression）詞匯表的哈希存儲(chǔ)，根據(jù)給定的關(guān)鍵字，散列成一個(gè)整數(shù)，用該整數(shù)作為詞匯的訪問地址。
倒排文件的優(yōu)點(diǎn)是：實(shí)現(xiàn)簡(jiǎn)單，響應(yīng)時(shí)間快，支持復(fù)雜查詢，適合商用搜索引擎。缺點(diǎn)是：建立索引要消耗很大的磁盤、內(nèi)存空間；當(dāng)網(wǎng)頁(yè)更新后，索引的維護(hù)代價(jià)也比較大。
總結(jié)
以上是生活随笔為你收集整理的倒排索引（Inverted File Index )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： trie数 字典树
- 下一篇： Requires: libstdc++.