γ code及其实现

 

1. What is γ code?

γ编码并不是我随便乱取的名字，其原理在信息检索导论第5章第3节有介绍，用于压缩一连串有序的数字类型的数据非常有用。在MG中将γ编码归类为全局模型（MG更推崇局部模型）。其原理是将所有的数据分成两部分连起来，第一部分为数据长度，第二部分为数据内容。这样做的好处是对于很小的数字γ编码可以只用bit就可以表示了，如对于8这样的数字，只需要表示数据长度的1110四位字节加上表示数据的000三位字节就可以表示了。而如果当做int保存，则需要4字节即32bit保存，而实际上前面的数据都是0，这样做很浪费空间。但γ编码需要保存后面的数据的长度，在保存很大的数字时会占用很大的空间，如保存一个4294967295这样的数字，需要占用64bit。而这个是一个32位的int内的数字，如保存为int，只需32bit即可保存了，前面提到γ编码用于保存一连串有序的数字类型非常有效，因为连续的有序数字型数据可以只保存数字间的间隔即可，如前一个数字是400000，后一个数字是400008，此时间隔只有8，只需保存成400000,8即可。因此后面这个数字就可以节省大量字节。而在搜索引擎的倒排索引中大量保存的都是这些数据，某单词对于的文档号，如：retrieval:1287,1297...

 γ编码的详细介绍请参照：http://nlp.stanford.edu/IR-book/html/htmledition/gamma-codes-1.html

 

相对于γ编码，有一个局部有参模型与之类似，在MG中有介绍，称之为全局贝努力和局部贝努力模型。可以参考下，主要是使用触发将数据化为商和余数，但除数需要经过训练得出。除数即为参数。

2. γ编码的实现

γ编码的实现难点是在文件中存储的是以byte为单位的数据，读取出数据时是一个一个的byte，需要精心计算每个数字的边界，并且计算出边界后需要使用各种二进制操作符对数据截取。

2.1 γ编码读取器

首先，需要确定的是数据的长度，即对读到的bit进行计数，当读到0时结束计数。即，如果读到的byte为01110111，读到第一个0时计数结束，说明后面跟着0bit数据。再加上前面已经确定的1，所有位加起来，数据就是1，然后读到第二个0时，此时计数器为3，表示后面跟着3bit的数据。也就是后面的111，再加上前面的1，即1111，转换为10进制就是15，也就是说这个byte包含两个数字：1,15。

假设现有byte by=119(01110111), by_index=0（用于保存当前byte被读了多少bit）;

首先用by^-1(11111111)，得到10001000，这里的1即表示0所在的位置，再判断10001000&10000000，如果等于10000000，则表示第一位存在0，如果与01000000做按位与操作得到01000000，则表示第二位为0，以此类推。

计数器为0直接返回1，此时by_index的值为1（已读取1bit）。再读取下一数据时，计数器为3。读取后面的数据需要先将by向左移动5位（by_index=5），用以截掉前面已经读取过的数据，得到11100000，再向右移动5位，得到00000111，假设目前有一临时结果保存在内存中(result)值为1。则将result向左移动三位（数据长度为3），得到00001000，再用00001000与00000111做按位或操作，得到00001111即为最终结果。

2.2 γ编码写入器

 γ编码的写入器首先要确定需要写入的数据的长度，同样需要对每个位做按位&计算，输出时需要考虑输出时按照每byte输出的，上次输出可能并没有完整地用完一byte，需要将bit数据加到后面去。

假设有数据15(1111),6(110)需要输出，首先经过计算得出数据15的长度是3（截掉前面的1），缓存中有byte by=0;需要先将3个1输出到缓存中，即by|11100000，然后输出数据，需要输出3位数字，此时前面4比特已被占用，需要将数据右移4bit。得到00001110，再与缓存数据做按位或操作，得到11101110，此时还有1bit未被占用，可被下一个数据使用，下一个数据需要2长度，使用上次遗存的1bit再加上下一byte的4byte就能完成存储了。

 

3.实验

使用GammaCodeWriter对随机100个1W以内的整数进行编码，输出到文件中，占用209字节，而如果使用DataOutputStream进行完整输出，则需要占用400字节。