【Golang系统开发】搜索引擎(2) 压缩词典

写在前面

这篇文章我们就给出一系列的数据结构，使得词典能达到越来越高的压缩比。当然，和倒排索引记录表的大小相比，词典只占据了非常小的空间。那么为什么要对词典进行压缩呢？

这是因为决定信息检索系统的查询响应时间的一个重要因素就是磁盘的访问次数，而如果有部分词典存在于磁盘上，那么在处理查询时就需要更多的磁盘访问次数。 因此，词典压缩的主要目的是可以将词典放在内存当中，这样才会获得很高的查询吞吐率。那么如何能将更多的词典压缩在有限的内存中呢？

1. 词典看成单一字符串

最简单的词典的数据结构就是整个词典采用定长数组来存储且所有词项按照词典序排序。假设对每个词项采用20B的固定长度存储，文档频率采用4B存储，词项到倒排索引也采用4B存储。这里的4B指针能够访问4GB的地址空间（4B–>32位–>2的32次方–>4GB）。

这样即使我们的词典有 四百万 个，我们所占的内存就只是 4,000,000 * (20+4+4) B = 112 MB，只是一百多兆而已，这非常的压缩。

但是很明显，采用这种定长方法来存储词典存在空间浪费。一个中文三个字节，很多情况下我们的词典只是两个中文，也就是六个字节，所以会有 14字节的浪费 。但是如果是一些特定的词语超过了20字节（比如中南财经政法大学），这里又存不下去。一种解决上述缺陷的方法是将所有的词项存成一个长字符串，并给每个词项增加一个定位指针，他在指向下一词项的同时也表示这当前词项的结束。 同以往一样，仍然可以通过二分查法定位到所需的词项，但是现在的表更小了。

由于每20B能够节省下12B，所以相当于前面的定长机制而言，这种机制能够在词项存储上节省大约60%的空间。当然，以上计算没有包括指向词项的指针所消耗的空间。所有的这些指针寻址的空间大小为 $400000\ast 8=3.2\ast 10^6$ ，因此一个指针 可以用 ${\log }_2(3.2)\ast 10^2$ 约等于 22 位 或者 3B来表示

将整个词条看成一个长字符串的词典存储方式，其中指向下一词项的指针同时也标志着当前词项的结束。

在这种方式下，词条就将所有上述的 4,000,000 * (20+4+4) B = 112 MB 压缩到了 4,000,000 * (3+4+4+8) B = 76 MB ，这个 8 指的是每个词项的平均长度。这种就从 112MB --> 76MB 大大降低了1/3

2. 按块存储

我们可以根据上一节的结果进行再一次的压缩：将长字符串中的词项进行分组变成大小为k的块，即k个词项一组，然后对每个块只保留第一个词项的指针。同时用一个额外字典将每个词项的长度存储在每个词项的首部。因此，每个块而已，可以减少k-1个词项指针，但是需要额外的kB来保存k个词项的首部。

因此，对每个块而言，可以减少k-1个词项指针，到那时需要额外的kB来保存k个词项的长度。对于k=4，词项指针的存储将会减少 (k-1) * 3 = 9B ，但是同时需要增加 k=4B 来存储词项的长度。因此在按块存储的方式下，没k=4个词项的方式下，每k=4个词项就会节省出5B，所以总共节省的空间位 400000 * 1/4 * 5 = 5 MB，也就再次减少了5MB，在 76MB 的基础上又少了 71MB。

显然，k越大，压缩率也就越高。但是，在压缩和词项查找速度之间必须要保持某种平衡。否则会导致查找速率偏慢。

除此之外，还有一种前端编码方式的压缩，也就是将上面多个词的公共部分提取出来，这样能减少很多的空间。，这里就不过多讲解了。