两个有意思的编码算法

最近在看《Column-Stores vs. Row-Stores: How Different Are They Really?》， 发现里面提到了列式数据库使用了编码(压缩)算法来减少查询时候的I/O消耗，因此找了两种有意思的编码算法: Run length encoding和Dictionary encoding找出来学习了一下。

Run Length Encoding

Run Length Encoding(RLE)是无损压缩的一种，这种压缩方法在数据连续重复的情况较多的时候比较有用，比如下面的数据:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

利用RLE会被压缩成:

12W1B12W3B24W1B14W

意思是说: 12个W，一个B，12个W, 3个B，24个W，1个B，14个W。原来需要67个字符表示的字符串，利用RLE之后只需要18个字符。

Dictionary Encoding

字典编码也称为替换编码，也是无损数据压缩的一种。它维护一个字典，在编码的时候把要编码的字符串转换成字典里面这个字母对应的下标，而解码的时候这从这个下标还原成原来的字符。我们余则成同志跟组织联系使用的就是这个字典编码：

字典编码在《潜伏》中的应用

字典编码分为两类，分类的依据是所依赖的字典是静态的还是动态的。上面的例子里面则成通知使用的书(好像是《康熙字典》之类的)就是静态的字典。静态字典应用的场景一般是要编码的字符比较固定，并且内容很长；跟静态字典相对应的是动态字典, 所谓的动态字典是在编码的过程中动态构建出来的，一开始字典是空的，输入的字符越来越多，这个字典也就越来越丰富。(具体的构建过程就不详细介绍了)

字典编码的关键是编码之后输出的不再是原来的字符了，而是代表这个字符的引用(通常是下标)，而且可以把多个字符编码成一个数字，因为数字比字符串占用的空间小，因此也就达到了编码的目的。

参考资料

1. Column-Stores vs. Row-Stores: How Different Are They Really?
2. Run Length Encoding
3. Dictionary encoding