压缩算法

发表于 | 更新于 | 分类于 | 阅读次数：

常见压缩算法

Algorithm % remaining Encoding Decoding
GZIP 13.4% 21 MB/s 118 MB/s
LZO 20.5% 135 MB/s 410 MB/s
Zippy/Snappy 22.2% 172 MB/s 409 MB/s
Lz4 大约等于snappy snappy两倍 snappy两倍
  • GZIP的压缩率最高，但是是cpu密集型，对cpu的消耗要大很多，压缩也解压速度都满
  • L4Z的压缩率和snappy差不多，但是速度是snappy的两倍。

列式存储压缩算法

  1. 字典编码
    将相同的值提取出来生成符号表（感觉就是建立索引表），每个列值则直接存储该值映射成的符号表值id（通过索引id的短来减少存储），但是如果量很大的时候，索引也会很大，等于没效果
    image
  2. 常量编码
    当区内的数据大部分的数据相同，只有少数不同时，可以采用常量编码。该编码将区内数据出现最多的一个值作为常量值，其他值作为异常值。异常值使用<行号+值>的方式存储。（将不一样的单独拎出来，加以行号）

image

  1. RLE编码（Run-Length Encoding）
    当区内的数据存在大量的相同值，每个不同值的个数比较均匀，且连续出现时，可以使用RLE编码。（其核心思想是将一个有序列中相同的列属性值转化为三元组（列属性值，在列中第一次出现的位置，出现次数）
    image

image

  1. 序列编码
    当区内的数据差值成等差数列，或者存在一定的代数关系，则可以使用序列编码。
    image

  2. Bit-Vector Encoding
    其核心思想是将一个列中所有相同列属性的值转化为二元组（列属性值，该列属性值出现在列中位置的Bitmap[Bitmap就是一个很大的数组，以01表示对应的数是否存在，海量数据的排序很有效，占用内存固定]）

image

Reference

http://www.cnblogs.com/23lalala/p/5643541.html
https://blog.csdn.net/bitcarmanlee/article/details/50938970