无损数据压缩算法介绍

无损数据压缩算法介绍

云计算、大数据、人工智能、物联网、边缘计算等新技术在各行业得到了广泛的普及和应用，催生了越来越多的数据量，数据的存储需求越来越大。

数据压缩在不丢失有用信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率，或按照一定的算法对数据进行重新组织，减少数据的冗余和存储。

数据压缩包括有损压缩和无损压缩。我们主要介绍无损数据压缩。

首先，数据中间常存在一些多余成分，既冗余度。其次，数据中间尤其是相邻的数据之间，常存在着相关性。这两个因素是数据能被压缩的原因。

传统度量数据压缩极限采用香农熵，香农信息熵只考虑的字符的统计性质，没有考虑序列的次序，即只考虑了字符出现的概率，没有考虑一系列字符所表示出的意义。

柯尔莫戈洛夫 (Andrey Nikolaevich Kolmogorov)复杂性，采用生成该对象所需的最短算法的长度来度量压缩的极限。

哥德尔不完全性定理的表述，以程序长度定义的复杂度，通常是不可计算的。即不存在一个程序，可以把字符串s作为输入，然后输出它的K(s)。

我们将分别介绍下面几类无损压缩算法：

统计压缩：Huffman编码，算术编码，ANS(Asymmetric numeral systems)

字典编码：LZ77,LZW,LZMA

上下文转换：游程编码,增量编码，MTF(Move-to-front transform),BWT( Burrows–Wheeler_transform)

预测编码：DMC(Dynamic Markov Coding),PPM(prediction by partial match),CTW(Context Tree Weighting)

上下文混合：PAQ,zpaq,cmix