索引压缩
词典压缩
如果我们按照上图的方式存储倒词典,那存储单词的空间必然要按照最长单词的长度来分配,这样就会造成大量的空间浪费。
在词典压缩这种技术方案里,可以将单词连续存储在某个内存区域,原先存储单词内容的部分由指向这个存储区对应单词起始位置的指针代替,单词结尾可以用词典中下一个单词的指针所指向的位置来做判断。如此就可以将原先浪费的存储空间利用起来。
在上面的基础上,我们还可以继续做出改进,我们可以将连续词典进行分块,在实际开发时,动态调整分块大小,而且原先每个词典项需要保留一个指向连续词典区的指针,分块之后,同一块的词典项可以共享同一个指针,每节省一个指针,就节省了4字节长的空间,此外,因为同一块内有多个单词,所以我们需要标识出单词的长度以便于区分。
经过上述优化的词典比不做优化的词典占用内存数量减少了60%。
倒排列表压缩
倒排列表往往记载三类信息:文档编号、词频信息及单词位置序列信息,因为文档编号及单词位置序列都是依次递增的,所以通常的做法是存储其差值,而非原始数据。这样文档编号和单词位置信息往往会被转换成大量的小整数,使得数字分布严重不均衡。
评价索引压缩算法的指标通常由三个:压缩率、压缩速度和解压速度。其中解压速度在3个指标中是最重要的。
一元编码和二进制编码是所有倒排列表压缩算法的基本构成元素,一元编码是,使用x-1个二进制数字1和末尾一个数字0来表示这个整数。比如5编码为11110。
二进制编码方式就是利用二进制进行编码。
Elias Gamma 算法与 Elias Delta 算法
Elias Gamma采用的分解函数是:x=(2^e)+d
对因子e+1用一元编码来表示,对于因子d采用比特宽度为e的二进制编码来表示。比如9编码为1110:001
Elias Delta是在Elias Gamma基础上的改进,它对因子e+1利用Elias Gamma再次进行压缩。比如9编码110:00:001,从左到右,110是3,110:00是4(2^2),110:00:000是8(2^3),110:00:001是9。
Golomb 算法与 Rice 算法
Golomb算法与Rice算法与上述两个算法相似,只是分解函数不同,就不详述了。