本文主要是介绍数据压缩入门-读书笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
数据压缩入门-读书笔记
简单的说，数据压缩算法有5类：变长编码(variable-length codes，VLC）、统计压缩（statistical compression）、字典编码（dictionary encodings）、上下文模型（context modeling）和多上下文模型（multicontext modeling）。
对数据进行压缩，通常有两个思路：
•减少数据中不同符号的数量（即让“字母表”尽可能小）；
•用更少的位数对更常见的符号进行编码（即最常见的“字母”所用的位数最少）。
60年来的数据压缩研究都可以归结到上面两个重要思路上，数据压缩中的每一个算法都聚焦于解决这两件事情中的一件。
数据压缩所做的无非就是尽可能减少表示特定数据集时所需的二进制位数量。
数位的概念：比如193这个数从左到右包含3个数位，分别是百位、十位和个位
信息论
信息论：即从数学的角度研究如何利用符号序列、脉冲序列或其他形式对信息进行编码，以及信息能以多快的速度在计算机电路或者电信信道中传输。
根据信息论的观点，一个数值所包含的信息内容等于，为了在一个集合中唯一地确定这个数值，需要做出的二选一（是/否）决定的次数。
考虑如下场景：有一个100平方英尺的房间，地上铺了100块瓷砖，上面是拱形的天花板，靠近东面的窗户边有一张四柱大床，北面的墙边有一张古色古香的小写字台，而在床的西边则放着一个沉重的18世纪的衣橱。
你完全可以在一页纸上用JSON 或者其他你喜欢的脚本语言写出上面所有这些内容。
或者，你也可以采用下面这种略有不同的方法，用7个二进制位对地上的100块瓷砖进行编码，再用2个二进制位对4个主要方向进行编码，然后对3件家具进行编码，每件家具各用2个二进制位。
按照瓷砖–家具–方向这样的顺序，你睡的床可以用10010100111来表示。（每个二进制位的“意义”这样的元信息，可以存在你的头脑中，或者编码到组装这个房间的软件中，抑或附在这些数据的后面。）
现在，描述整个房间只需要44个二进制位或者6个字节就够了，比起文字描述或者JSON文件，节省了相当多的空间（不仅我们这样认为，那些下载了你的游戏的移动端用户也会认同）。
简单来说，这就是一个数据压缩的过程。
熵
给定任意一个十进制整数，通过计算它对应的LOG2函数的值，我们就能知道用二进制来表示这个数最少需要多少二进制位。香农将一个变量对应的LOG2函数的值定义为它的熵（entropy），也就是用二进制来表示这个数所需的最少二进制位数。
数值的LOG2表示形式虽然高效，但对于制造计算机元件的方式来说并不实用。这其中的问题在于，如果用最少的二进制位数来表示一个数，在解码相应的二进制字符串时会产生混乱（因为我们并不知道该数对应的LOG2长度），会与硬件的执行性能相冲突，两者不能兼顾。
现代计算机采用了折中的方案，用固定长度的二进制位数来表示大小不同的整数。最基本的存储单元是一个字节，由8个二进制位组成。
在现代编程语言中，通常可用的整数的存储类型包括：短整型16个二进制位、整型32个二进制位、长整型64个二进制位。
因此，对于十进制数10，虽然其对应的二进制数为1010，但在实际存储中是短整型，在计算机中的实际表示为0000000000001010。显然，这样做浪费了很多的二进制位。
这里需要指出的是，在现代应用程序开发中，我们所用到的绝大多数算法使用预先设定好的固定的二进制位长度，而不是通过LOG2函数计算出的二进制位长度。这就是信息论与实际实现层面的差别。
在计算机内存中，我们遇到的任何二进制位流都会舍入到下一个字节对齐的大小。这可能会让人困惑，比如当我们只存储了7个二进制位的数据时，计算机仍然会报告说我们所存储的数据长度与计算机一次读取的最小字节数相同。
实际中的数据压缩目标，是尽可能接近理论上的压缩极限。
为了使表示某个数据集所需的二进制位数最少，数据集中的每个符号平均所需的最小二进制位数就是熵。
从本质上来说，香农所定义的熵，是以一种倒排序的方式建立在数据流中每个符号出现概率的估算之上的。
总的来说，一个符号出现得越频繁，它对整个数据集包含的信息内容的贡献就会越少，这看起来似乎完全违背直觉。
钓鱼就是这样一个真实的例子。设想你坐在岸边草坪中的躺椅上，戴着漂亮的帽子，手拿卷筒和连杆，望着河面和鱼浮。每隔几分钟，你就会看一眼鱼浮，发现它并没有变化，但每隔一小时左右，就会有鱼咬钩，这才是你真正感兴趣的事情。也就是说，很长的时间里没有什么有用的信息，真正有用的信息偶尔才会出现。如果用0表示没有鱼，用1表示鱼上钩，那么你记录的信息里很容易出现这样的片段：0000000010000000001000000000001。
从统计上来说（从运动角度来说同样如此），我们感兴趣的是鱼在咬钩这样的事件，其他的都是冗余信息。
数据压缩领域的最前沿都是关于如何改变熵的。事实上，整个数据压缩科学界的人士都认为熵是互联网上的一大“谎言”。
真相是，实际上，通过利用真实数据的两个性质，我们完全有可能将数据压缩得比熵定义的还要小。按照香农对熵的定义，他只考虑了符号出现的概率，完全没有考虑符号之间的排序。而对真实数据集来说，排序是一项基本的信息，符号之间的关系同样如此。
例如，排好序的[1,2,3,4] 和没有排序的[4,1,2,3] 这两个集合，按照香农的定义，两者的熵相同，但是凭直觉我们就能发现，其中的一个集合包含了额外的排序信息。我们再来看一个元素为字母的例子，[Q,U,A,R,K] 和[K,R,U,Q,A] 这两个集合有相同的熵，但[Q,U,A,R,K] 这个集合表示的是英语中一个有意义的单词，而且字母的出现也有一定的规则，比如字母Q后面通常会跟着字母U。
突破熵的关键在于，通过利用数据集的结构信息将其转换为一种新的表示形式，而这种新表示形式的熵比源信息的熵小。
增量编码
元素递增的集合[0,1,2,3,4,5,6,7] 称为集合 A1，现在打乱，得到[1,0,2,4,4,5,7,6]集合 A2。
根据香农的定义，每个符号都需要用3个二进制位来编码，而每个集合则需要24个二进制位。然而最终的结果是，我们很容易就能突破熵的限制，用更少的二进制位对集合A1进行编码，具体方法如下：
集合A1实际上是数的一个线性递增序列。因此，无须对其中的每个数都进行编码，而是可以对整个数据流进行转换，将各个数编码为其与前一个数的差。所以，编码后的集合 A3 会是这样：
[0,1,1,1,1,1,1,1]
这样的转换一般称为增量编码（delta coding），也就是将一系列的数转换为其与上一个数的差后再编码。
符号分组
字符串 S = “TOBEORNOTTOBEORTOBEORNOT”，它包含了不同符号的集合[O,T,B,E,R,N]。
如果不是将单个的字母当成符号，而是把单词当成符号，情况又会如何呢？这样一来，我们有单词集合[TO,BE,OR,NOT]。
再观察这个字符串，我们发现“TOBEORNOT”这个词组出现过多次，可以将该词组当做一个符号。
如果数据集中存在连续值组合出现多次的情况，就可以利用这种情况来减小熵。一般来说，通过最佳符号分组预处理数据，会得到一个较小的熵值。
排列
在数学中，排列这一概念是指重新安排或者改变一个集合的所有元素的次序或者顺序。
从经典的定义来看，只有同一组数的不同顺序才算排列，比如可以说[2,1,3,4] 是[1,2,3,4] 的一个排列，但[5,2,7,9] 就不是。
通过消除编码法压缩排列
排列很难压缩是出了名的。排列是可以稍微压缩的，但这个过程没什么意思，也没多少实际价值。
数据压缩算法的艺术，就在于真正试图去突破熵的限定，或者说是将数据转换成一种熵值更小的、新的表现形式。
这可以说是真正的舞蹈：
信息论已经制定了相应的规则，
数据压缩则以斗牛士的热情巧妙地避开了这些规则。
VLC
摩尔斯码
摩尔斯码为英语字母表中的每一个字符都分配了或长或短的脉冲，一个字母用得越频繁，其编码也就越短、越简单。因此，英语中最常用的字母“E”的编码最短，用一个点表示；而字母“X”的编码毫无疑问则很长；所有的数字都用5个脉冲表示。
即使是追溯到19世纪，这也是对符号分配变长编码（variable-length codes，VLC）的最初实现之一，其目的则在于减少传输信息过程中所需要的总工作量。
有理由相信，在早期对信息论的研究中，克劳德•香农（他是摩尔斯码方面的专家）正是利用了这一概念，由此创造了一个新的技术领域“数据压缩”的第一代技术，这些都是在VLC的启发下产生的。
对于给定的输入数据集，可先计算涉及的符号的出现概率，然后就可以通过VLC将字长最短的码字分配给最可能出现的符号，从而实现压缩数据。
运用 VLC
一般来说，对数据进行VLC通常有3个步骤。
(1) 遍历数据集中的所有符号并计算每个符号的出现概率。
(2) 根据概率为每个符号分配码字，一个符号出现的概率越大，所分配的码字就越短。
(3) 再次遍历数据集，对每一个符号进行编码，并将对应的码字输出到压缩后的数据流中。
举个例子，要使用刚创建的符号码字对应表对“TOBEORNOT”进行编码，第一个字符是“T”，因此将相应的码字00添加到输出流，接下来是字符“O”，再将11添加到输出流。如此反复，最终得到“TOBEORNOT”所对应的输出流为001101110111010001011100，共24个二进制位。
与72个二进制位的源数据流相比（即使平均每个字符只用3个二进制位），通过压缩节省了大约11% 的空间。
前缀性质
在任意时刻，解码器都需要能确定到目前为止所读取的二进制位，是否与特定字符的码字相匹配，以及是否还需要继续读取下一个二进制位。为了确保正确，在设计VLC集的码字时，必须考虑两个原则：一是越频繁出现的符号，其对应的码字越短；二是码字需满足前缀性质。
先看看一个潜在的VLC是怎样崩溃的。假定我们有数据流0101111，以及如下表所示的VLC对应表。
解码过程如下所示：
(1) 解码器读取0，其对应的字符肯定是A，因此将A输出。
(2) 解码器读取1，它可能是字符B、C或D的码字的第一位。
(3) 解码器继续读取0，现在可能字符的范围缩小为B或C。
(4) 解码器继续读取1，这里我们遇到了歧义：读取的二进制位101，应该解释为10 + 1(表示的是B与另一个字符的开始，该字符可以是B、C或者D）还是 101（表示的是字符C）呢？此时，解码的过程已经进行不下去了，因为我们已不能确定读取的二进制位到底表示的是什么符号。如下图所示，我们设计的码字已经让我们无法区分不同的符号。
这里，我们提到了VLC的前缀性质，它的意思是：
在某个码字被分配给一个符号之后，其他的码字就不能用该码字作为前缀。
换句话说，每个符号都能通过其码字前缀唯一地确定，只有这样，VLC才能正常工作。
前缀性质是VLC能正常工作所必须具有的性质。这也就意味着，与二进制表示相比，VLC要更长一些。
折中后的结果是，我们得到的数据流会更长（因而也更大），但同时也能在事先不知道符号长度的情况下进行解码。由于那些常见的字符对应的码字很短，因此对那些少数几个字符出现频率特别高的数据流而言，VLC的压缩率还是很高的。
通用编码
一位数学家板凳一坐十年冷，最终找到了一种将整数转换为VLC的独特方法。
这种编码方法一般称为通用编码（universal codes），大致来说，就是为正整数赋上一个长度可变的二进制码字。
通常来说，通用编码遵循以下原则：数值越小，其对应的码字也越短，因为假定小整数比大整数出现得更频繁。
通用编码是一类特殊的前缀编码。还有其他类型的VLC方法，比如唯一可译码（uniquely decodable codes）与非奇异码（nonsingular codes）。
二进制编码
由于二进制编码在计算机中无处不在，因此它总是数据压缩的最终结果。
人们总是习惯用[插图]来表示整数B(n)的标准二进制表示。这种表示通常被称为beta编码或二进制编码，不过它不满足前缀性质。例如，2的二进制表示为10，同时它也是4的二进制表示100的前缀。
给定 0~n 的任意整数，我们都能用 1 + floor(lb(n)) 个二进制位来表示。也就是说，只要提前知道 n 的值，我们就能通过固定长度表示法来避开前缀问题。换句话说，如果知道有多少个数需要表示，我们很容易算出一共需要多少二进制位。然而，如果不能提前知道数据集中有多少个不同的整数，就不能用固定长度表示法。
一元码
任意正整数 n，它的一元码表示都是 n - 1 个1后面跟着1个0，例如，4的一元码表示为1110。所以，很容易得出，整数 n 的一元码长度也是 n 个二进制位。同样，也容易看出一元码满足前缀性质，因此可以将它作为VLC使用。
将一元码应用在那些前一个符号的出现概率是后一个符号2倍的数据集上，效果最佳。（也就是说，A的出现概率是B的两倍，而B的出现概率又是C的两倍。）
Elias gamma 编码
Elias gamma编码主要用于事先无法确定其上界的整数的编码，也就是说，不知道最大的整数会是多大。
该方法最主要的思想是不再对整数直接编码，而是用其数量级作为前缀。这样一来，相应的码字就由两部分组成，即与此整数相当的2的次幂再加上余数，编码方法如下所示：
(1)找出最大的整数 N ，使其满足 2 ^N< n < 2 ^(N+1)，并且将 n 表示为 n = 2 ^N + L 这样的形式（这里 L = n - 2 ^N）
(2)用一元码表示 N。
(3)将 L 表示为长为 N 的二进制编码，并加在步骤(2)中得出的一元码之后。（这一步很重要，正是有了这样的对称性，后面才能顺利解码。）
比如，当 n = 12 时，会进行如下编码：
（1）由于 2^3 = 8，而 2 ^4= 16，同时 2 ^3< 12 < 2^4，因此 N 的值等于 3。
（2）根据前面的说明，可以算出 L 的值为 12 - 8 = 4。
（3）N = 3，其对应的一元码为 110.
（4）L = 4，其对应的长度为 3 的 二进制码为 100.
（5） 将前两个步骤得出的编码连接，就得到了最终的输出 110100。
与简单的一元编码类似，Elias gamma编码对那些整数 n 的出现概率 P(n) = 1 / (2 * n²)的情形比较适用。
Elias delta 编码
Elias delta编码则是另外一个变种。在这一方法中，Elias还在前面加上了二进制的长度，使这一编码稍微复杂一些。
原理如下：
(1)将要编码的数 n 用二进制表示。
(2)数一下 n 的二进制位数，并将这个位数转化为二进制，作为C。
(3)去掉 n 的二进制表示的最左边一位，这个值肯定是1，可以推断出来。
(4)将 C 的二进制表示加在去掉最左边一位后的 n 的二进制表示前。
(5) 在上一步骤所得的结果前加上C的二进制位数减1个0作为最终的编码。
以 数字 12 为例：
(1)将 n = 12 表示为二进制1100。
(2)12的二进制表示共有4位，将4表示为二进制，即C = 100。
(3)去掉 n 的二进制表示的最左一位，得到100。
(4) 将C = 100加到上一步骤所得的结果之前，得到100100。
(5) 将C的二进制位数减1，即3-1 = 2，在上一步骤所得的结果前加上2个0，由此得到12的最终编码为00100100。
在过去的40多年中，人们创造了数百种VLC算法.
谷歌的 Varint 算法：避免压缩整数
VLC主要存在以下几个问题，因而只能用于表示压缩数据流，没有其他应用。
•它们不按字节 / 字 / 整型对齐。
•对于大的数值 n，为了方便解码，其码字长度的增长速度一般会超过 lb(n) 个二进制位。
•解码的速度很慢（每次只能读取一个二进制位）。
对那些需要处理很多大整数的系统来说，这些问题使得VLC无法应用。然而，在21世纪初，出现了一个新的可变长度整数模型，在搜索引擎和其他海量数据系统中得到了广泛应用。
虽然它是以谷歌的Varint算法而流行的，但其中最基本的概念早在1972年就提出来了，并在2010年作为“避免压缩整数”（escaping for compressed integers）而被重新引入。
Varint是一种表示整数的方法，它用一个或多个字节来表示一个整数，数值越小用的字节数越少，数值越大用的字节数越多。
该方法将几个字节连接起来表示整数，并用每个字节的MSB作为布尔标志，来判断当前的字节是否为该整数的最后一个字节；而每个字节的低7位则用来存储该数的二进制补码（two’s complement representation）。
比如：
整数1可以用一个字节表示，因此它的MSB不需要设置，可表示为00000001。
再来看整数300，它的表示则要复杂一些：10101100 00000010。那么如何判断它表示的是300呢？
最高有效位（ most significant bit，MSB）指的是一个n位二进制数字中的n-1位，具有最高的权值2^(n-1)。
首先，需要删掉每个字节的MSB，因为它的作用只是判断当前字节是否是最后一个字节（正如你看到的那样，第一个字节的MSB已经设置为1，因为用Varint方法来表示，该数需要多个字节）。10101100 00000010 → 0101100 0000010。
接着，将剩下的两个7二进制位的数据顺序颠倒一下，因为用Varint方法表示时，低位的字节在前。最后，将二进制表示转换为十进制数，就得到了最终的数值。
0101100 0000010 → 0000010 0101100 → 2^8 + 2^5 + 2 ^ 3 + 2 ^ 2 = 256 + 32 + 8 + 4 = 300
Varint表示方法结合了VLC的灵活性和现代计算机体系结构的高效率，是一种很好的混合方法。它既允许我们表示可变范围内的整数，同时还对自身的数据进行了对齐以提高解码的效率，达到了双赢。
为数据集找到最适合的编码方法
在为数据集选择一种VLC编码方法时，必须要先考虑数据集的整体大小和数据范围，并计算各个符号的出现概率。如果不这样做，得到的结果可能就是，数据集的大小不但没有压缩，有可能反而比原来的数据集还大。
VLC编码方法是根据某个数值期望的出现频率来为该值分配码字的。因此，每种VLC编码方法，对于数据集中的各个符号如何分布，都有相应的期望。因此，为数据集选择适当的VLC编码方法，关键在于使VLC背后的概率模型与该数据集匹配。如果偏离了这个方向，最终得到的可能会是更大的数据流。
统计编码（statistical encoders）这类算法无须将特定的整数转换为特定的码字，而是通过数据集中符号的出现概率来确定新的、唯一的变长码字。最终的结果就是，给定任何输入数据，我们都能为其构造出一套自定义的码字集，而无须去匹配现有的VLC方法。
如果要更准确地描述这类算法，那么“统计编码算法通过数据集中符号出现的概率来进行编码使结果尽可能与熵接近”这样的表述可能很合适。
统计编码
哈夫曼编码
哈夫曼编码可能是生成自定义VLC最直接、最有名的方法。给定一组符号及其出现频率，该方法能生成一组符号平均长度最短的VLC。它的工作原理是将数据排序后建立决策树(decision tree），然后从“树干”一直往下直到“树叶”为止，并记录下所做的是/否选择。这里所说的“树叶”就是我们要找的各个符号。
1、构造哈夫曼树
哈夫曼发现如果使用二叉树，就能利用符号表中的概率与二叉树的分支来创建优化的二进制代码。
先将符号及其出现的频次写在便签纸上，再根据频次对符号进行排序，然后自下而上建一棵二叉哈夫曼树，并称它们为哈夫曼树的叶子。
接下来，选择出现频次最小的两个符号，并将它们往下移一层，然后拿出新的便签将两者合并作为它们的父节点，上面写上两个符号的组合及频次相加之和：
然后重复上述过程，再合并剩下的A结点和BC结点创建一个新的根节点ABC，这样它就表示了完整的符号集：
2、生成码字
为了能生成码字，给所有左子树赋值0，为所有右子树赋值1。
最后，为了获得给定符号（叶子节点）的码字，需要从根节点“沿着树枝”往下走，并将所得的1和0按从MSB到LSB排列起来，也就是从左排到右。
例如，为了确定符号B的码字，从根节点开始，向右遍历（得到1），然后再向左遍历（0），这样得到的10就是B的码字
为了得到其他剩余符号（叶子节点）的码字，只要重复上面的过程就可以了:
3、编码与解码
现在你已成功地为数据集构造了VLC，可以用它们进行编码了。只要遍历输入流，对遇到的每一个符号，写下其对应的码字作为输出就可以了。
为了解码，也需要将符号码字对应表与压缩后的内容放在一起传输，然后再按照标准的VLC的解码过程进行解码。
由于创建哈夫曼树（需使用计算资源）要比传输符号码字对应表（会增加数据流大小）困难得多，因此总是应该将码字对应表加在数据流的前面，而不是在解码时再重新创建一次。
4、实际的实现方法
在过去的50多年里，人们已经对哈夫曼编码进行了大量的分析，不但产生了各种能在特定性能或内存阈值下工作的变体，也有针对特定概率分布的各种变体。
算术编码
哈夫曼编码简单、高效，也能为单个的数据符号生成最佳的码字。然而，对于给定的符号集来说，它并非总是生成最有效的码字。
事实上，哈夫曼编码能生成理想VLC（即码字的平均长度等于符号集的熵）的唯一情形是，各个符号的出现概率等于2的负整数次幂（即是1/2、1/4或1/8这样的值）。这是因为哈夫曼方法会为给定符号集中的每个符号都分配一个整数二进制位长的码字。
信息论告诉我们，如果一个符号的出现概率为0.4，那么它最理想的码字长度应该是1.32个二进制位，因为–lb(0.4) ≈ 1.32。而哈夫曼方法分配给这个符号的码字长度则只能是1个二进制位或2个二进制位。
与按照1∶1的比例为每个符号分配一个码字不同，算术编码算法会将整个输入流转换为一个长度很长的数值，而它的lb表示则与整个输入流真正的熵值很接近。算术压缩的神奇之处在于，它将转换应用到整个源数据上以生成一个输出值，而表示这个输出值所需要的二进制位数比源数据本身少。
1、找出正确的数
算术编码的工作原理是将字符串转换为一个数，与字符串相比，表示这个数需要的二进制位数要少一些。例如，字符串“TOBEORNOT”可以用数236712来表示，而ceil(lb(236 712)) = 18，即只需要18个二进制位就能表示。相比而言，如果用ASCII码来表示“TOBEORNOT”，则需要56个二进制位。
不过，事情并不像前面举的例子那样简单，随机挑选一个数就可以了。相反，算术编码会根据输入流，通过一系列复杂的步骤计算出那个数。
算术编码首先会创建[0,1)这样的数值区间，然后再通过数据流中符号出现的概率对这一区间进行细分。比如说，如果A出现的概率为25%，那么为A分配的区间就是[0,0.25)，B出现的概率为10%，那么B对应的区间则为[0.25,0.35)，以此类推，如下图所示。
当编码器读取一个符号时，它就会找到这个符号对应的区间。例如，如果读取字符A，那么用到的区间就是[0.0,0.25)。在读取一个符号以后，编码器将继续细分这个取值区间，并按符号的出现比例进行细分。
例如，
这篇关于数据压缩入门-读书笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
