寫(xiě)在前面

這篇文章我們就給出一系列的數(shù)據(jù)結(jié)構(gòu)，使得詞典能達(dá)到越來(lái)越高的壓縮比。當(dāng)然，和倒排索引記錄表的大小相比，詞典只占據(jù)了非常小的空間。那么為什么要對(duì)詞典進(jìn)行壓縮呢？

這是因?yàn)闆Q定信息檢索系統(tǒng)的查詢響應(yīng)時(shí)間的一個(gè)重要因素就是磁盤(pán)的訪問(wèn)次數(shù)，而如果有部分詞典存在于磁盤(pán)上，那么在處理查詢時(shí)就需要更多的磁盤(pán)訪問(wèn)次數(shù)。 因此，詞典壓縮的主要目的是可以將詞典放在內(nèi)存當(dāng)中，這樣才會(huì)獲得很高的查詢吞吐率。那么如何能將更多的詞典壓縮在有限的內(nèi)存中呢？

1. 詞典看成單一字符串

最簡(jiǎn)單的詞典的數(shù)據(jù)結(jié)構(gòu)就是整個(gè)詞典采用定長(zhǎng)數(shù)組來(lái)存儲(chǔ)且所有詞項(xiàng)按照詞典序排序。假設(shè)對(duì)每個(gè)詞項(xiàng)采用20B的固定長(zhǎng)度存儲(chǔ)，文檔頻率采用4B存儲(chǔ)，詞項(xiàng)到倒排索引也采用4B存儲(chǔ)。這里的4B指針能夠訪問(wèn)4GB的地址空間（4B–>32位–>2的32次方–>4GB）。

這樣即使我們的詞典有 四百萬(wàn) 個(gè)，我們所占的內(nèi)存就只是 4,000,000 * (20+4+4) B = 112 MB，只是一百多兆而已，這非常的壓縮。

但是很明顯，采用這種定長(zhǎng)方法來(lái)存儲(chǔ)詞典存在空間浪費(fèi)。一個(gè)中文三個(gè)字節(jié)，很多情況下我們的詞典只是兩個(gè)中文，也就是六個(gè)字節(jié)，所以會(huì)有 14字節(jié)的浪費(fèi) 。但是如果是一些特定的詞語(yǔ)超過(guò)了20字節(jié)（比如中南財(cái)經(jīng)政法大學(xué)），這里又存不下去。一種解決上述缺陷的方法是將所有的詞項(xiàng)存成一個(gè)長(zhǎng)字符串，并給每個(gè)詞項(xiàng)增加一個(gè)定位指針，他在指向下一詞項(xiàng)的同時(shí)也表示這當(dāng)前詞項(xiàng)的結(jié)束。 同以往一樣，仍然可以通過(guò)二分查法定位到所需的詞項(xiàng)，但是現(xiàn)在的表更小了。

由于每20B能夠節(jié)省下12B，所以相當(dāng)于前面的定長(zhǎng)機(jī)制而言，這種機(jī)制能夠在詞項(xiàng)存儲(chǔ)上節(jié)省大約60%的空間。當(dāng)然，以上計(jì)算沒(méi)有包括指向詞項(xiàng)的指針?biāo)牡目臻g。所有的這些指針尋址的空間大小為 $400000?8=3.2?10^6$ ，因此一個(gè)指針 可以用 ${\log }_2(3.2)?10^2$ 約等于 22 位 或者 3B來(lái)表示

將整個(gè)詞條看成一個(gè)長(zhǎng)字符串的詞典存儲(chǔ)方式，其中指向下一詞項(xiàng)的指針同時(shí)也標(biāo)志著當(dāng)前詞項(xiàng)的結(jié)束。

在這種方式下，詞條就將所有上述的 4,000,000 * (20+4+4) B = 112 MB 壓縮到了 4,000,000 * (3+4+4+8) B = 76 MB ，這個(gè) 8 指的是每個(gè)詞項(xiàng)的平均長(zhǎng)度。這種就從 112MB --> 76MB 大大降低了1/3

2. 按塊存儲(chǔ)

我們可以根據(jù)上一節(jié)的結(jié)果進(jìn)行再一次的壓縮：將長(zhǎng)字符串中的詞項(xiàng)進(jìn)行分組變成大小為k的塊，即k個(gè)詞項(xiàng)一組，然后對(duì)每個(gè)塊只保留第一個(gè)詞項(xiàng)的指針。同時(shí)用一個(gè)額外字典將每個(gè)詞項(xiàng)的長(zhǎng)度存儲(chǔ)在每個(gè)詞項(xiàng)的首部。因此，每個(gè)塊而已，可以減少k-1個(gè)詞項(xiàng)指針，但是需要額外的kB來(lái)保存k個(gè)詞項(xiàng)的首部。

因此，對(duì)每個(gè)塊而言，可以減少k-1個(gè)詞項(xiàng)指針，到那時(shí)需要額外的kB來(lái)保存k個(gè)詞項(xiàng)的長(zhǎng)度。對(duì)于k=4，詞項(xiàng)指針的存儲(chǔ)將會(huì)減少 (k-1) * 3 = 9B ，但是同時(shí)需要增加 k=4B 來(lái)存儲(chǔ)詞項(xiàng)的長(zhǎng)度。因此在按塊存儲(chǔ)的方式下，沒(méi)k=4個(gè)詞項(xiàng)的方式下，每k=4個(gè)詞項(xiàng)就會(huì)節(jié)省出5B，所以總共節(jié)省的空間位 400000 * 1/4 * 5 = 5 MB，也就再次減少了5MB，在 76MB 的基礎(chǔ)上又少了 71MB。

顯然，k越大，壓縮率也就越高。但是，在壓縮和詞項(xiàng)查找速度之間必須要保持某種平衡。否則會(huì)導(dǎo)致查找速率偏慢。

除此之外，還有一種前端編碼方式的壓縮，也就是將上面多個(gè)詞的公共部分提取出來(lái)，這樣能減少很多的空間。，這里就不過(guò)多講解了。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-654496.html

到了這里，關(guān)于【Golang系統(tǒng)開(kāi)發(fā)】搜索引擎(2) 壓縮詞典的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！