1.概率、熵与码字长度1.1.数据压缩的目的1.1.1.给定一个数据集中的符号，将最短的编码分配给最可能出现的符号1.2
1.2.1.当P(A)=P(B)，也就是两个符号等可能出现时，数据集对应的熵取最大值LOG2（符号的个数），此时数据集很难压缩1.2.2.其中一个符号出现的可能越大，数据集的熵值就越小，此时数据集也越容易压缩1.2.3.对只包含两个符号的数据集来说，两个符号互换概率不影响其熵值1.3.启示1.3.1.随着数据集的冗余度下降，它的熵在变大，其最大值为数据集中不同符号个数的LOG2值1.3.2.数据集中一个符号出现的概率越大，整个数据集的熵就越小，数据集也就越容易压缩1.3.3.码字的长度与符号的出现概率密切相关，而与符号本身没有太大关系2.VLC算法2.1.在过去的40多年中，人们创造了数百种VLC算法2.2.在为数据集选择一种VLC编码方法的考虑因素2.2.1.数据集的整体大小2.2.2.数据范围2.2.3.计算各个符号的出现概率2.2.4.如果不这样做，得到的结果可能就是，数据集的大小不但没有压缩，有可能反而比原来的数据集还大2.3.存在的主要问题2.3.1.它们不按字节 / 字 / 整型对齐2.3.2.对于大的数值N，为了方便解码，其码字长度的增长速度一般会超过lb(N)个二进制位2.3.3.解码的速度很慢（每次只能读取一个二进制位）2.3.4.只能用于表示压缩数据流，没有其他应用3.设计VLC集的码字原则3.1.越频繁出现的符号，其对应的码字越短3.2.码字需满足前缀性质4.前缀性质4.1.如果一个码字是另一个码字的前缀，那么用VLC解码二进制流就会很难4.2.某个码字被分配给一个符号之后，其他的码字就不能用该码字作为前缀4.2.1.每个符号都能通过其码字前缀唯一地确定4.3.前缀性质是VLC能正常工作所必须具有的性质4.3.1.与二进制表示相比，VLC要更长一些5.唯一可译码5.1.uniquely decodable codes6.非奇异码6.1.nonsingular codes7.每一种前缀编码都是唯一可译的和非奇异的8.VLC编码步骤8.1.遍历数据集中的所有符号并计算每个符号的出现概率8.1.1.画出数据集中所有符号的直方图8.2.根据概率为每个符号分配码字，一个符号出现的概率越大，所分配的码字就越短8.2.1.根据出现的频数对直方图进行排序8.2.2.给每个符号分配一个VLC，从VLC集中码字最短的开始8.3.再次遍历数据集，对每一个符号进行编码，并将对应的码字输出到压缩后的数据流中9.VLC解码步骤9.1.由于码字的长度并非是固定的，因此解码过程还是稍微有些复杂9.2.解码的时候，我们会一二进制位一二进制位地读取数据，直到读取的二进制位流与其中的某个码字相匹配9.3.一旦匹配，就会输出相应的符号，并继续读取下一个码字10.摩尔斯码10.1.1836年10.1.1.画家Samuel F. B. Morse10.1.2.物理学家Joseph Henry10.1.3.机械师Alfred Vail10.1.4.发明了第一套电报系统10.2.克劳德•香农10.2.1.摩尔斯码方面的专家10.3.最简单的编码文本信息的方法10.3.1.用数字126来编码AZ的英文字母10.4.发送一次信息所需要的人工操作次数太多10.4.1.物理硬件（发报机设备）和人工硬件(也就是操作人员的手腕）的磨损比预期的要快，解决方法则是使用统计来减少工作量10.5.对符号分配变长编码（variable-length codes，VLC）的最初实现之一10.6.为英语字母表中的每一个字符都分配了或长或短的脉冲，一个字母用得越频繁，其编码也就越短、越简单10.6.1.目的则在于减少传输信息过程中所需要的总工作量11.通用编码11.1.universal codes11.2.一种将整数转换为VLC的独特方法11.3.一类特殊的前缀编码11.4.为正整数赋上一个长度可变的二进制码字11.5.数值越小，其对应的码字也越短11.5.1.因为假定小整数比大整数出现得更频繁12.二进制编码12.1.不满足前缀性质12.2.用B(n)来表示整数n的标准二进制表示12.3.beta编码或二进制编码12.4.给定0~N的任意整数，都能用1+floor(lb(n))个二进制位来表示12.4.1.只要提前知道N的值，就能通过固定长度表示法来避开前缀问题12.4.2.如果不能提前知道数据集中有多少个不同的整数，就不能用固定长度表示法13.一元码13.1.满足前缀性质13.2.任意正整数N，它的一元码表示都是N-1个1后面跟着1个013.2.1.4的一元码表示为111013.3.整数N的一元码长度也是N个二进制位13.4.将一元码应用在那些前一个符号的出现概率是后一个符号2倍的数据集上，效果最佳13.5.如果每个整数N的出现概率P(N)服从指数分布2^(-N)，即1/2、1/4、1/8、1/16、1/32，其他以此类推，就可以使用一元码进行编码14.Peter Elias14.1.1923年11月23日生14.2.1955年，他就引入了卷积码（convolutional codes），作为分组码（block codes）的一种替代方法14.3.建立了二进制删除信道（binary erasure channel），并提出了用纠错码的列表译码（list decoding of error-correcting codes）来代替唯一可译码（unique decoding）14.4.Elias gamma编码14.4.1.用于事先无法确定其上界的整数的编码14.4.1.1.不知道最大的整数会是多大14.4.2.对整数n的出现概率P(n)=1/(2n*n)的情形比较适用14.4.3.最主要的思想是不再对整数直接编码，而是用其数量级作为前缀14.4.3.1.相应的码字就由两部分组成，即与此整数相当的2的次幂再加上余数14.4.4.工作原理14.4.4.1.找出最大的整数N，使其满足2N＜n＜2(N+1)，并且将n表示为n=2^N+L这样的形式14.4.4.1.1.L=n-2^N14.4.4.1.2.n=12,23=8,24=16,23＜n＜24,N=314.4.4.1.3.L=12-2^3=414.4.4.2.用一元码表示N14.4.4.2.1.N=3,一元码11014.4.4.3.将L表示为长为N的二进制编码，并加在步骤(2)中得出的一元码之后14.4.4.3.1.有了这样的对称性，后面才能顺利解码14.4.4.3.2.L=4，其对应的长度为3的二进制码为10014.4.4.3.3.将前两个步骤得出的编码连接，就得到了最终的输出11010014.5.Elias delta编码14.5.1.对整数N的出现概率P(N)等于1/[2n(lb(2n)*lb(2n))的数据集来说是理想的选择14.5.2.工作原理14.5.2.1.将要编码的数N用二进制表示14.5.2.1.1.将N=12表示为二进制110014.5.2.2.数一下N的二进制位数，并将这个位数转化为二进制，作为C14.5.2.2.1.12的二进制表示共有4位，将4表示为二进制，即C = 10014.5.2.3.去掉N的二进制表示的最左边一位，这个值肯定是114.5.2.3.1.去掉N=12的二进制表示的最左一位，得到10014.5.2.4.将C的二进制表示加在去掉最左边一位后的N的二进制表示之前14.5.2.4.1.将C = 100加到上一步骤所得的结果之前，得到10010014.5.2.5.在上一步骤所得的结果前加上C的二进制位数减1个0作为最终的编码14.5.2.5.1.将C的二进制位数减1，即3-1 = 2，在上一步骤所得的结果前加上2个0，由此得到12的最终编码为0010010015.谷歌的Varint算法15.1.最基本的概念早在1972年就提出15.2.2010年作为“避免压缩整数”（escaping for compressed integers）而被重新引入15.3.是一种表示整数的方法，它用一个或多个字节来表示一个整数，数值越小用的字节数越少，数值越大用的字节数越多15.3.1.结合了VLC的灵活性和现代计算机体系结构的高效率，是一种很好的混合方法15.3.2.既允许我们表示可变范围内的整数，同时还对自身的数据进行了对齐以提高解码的效率，达到了双赢15.4.方法15.4.1.将几个字节连接起来表示整数15.4.2.并用每个字节的MSB作为布尔标志，来判断当前的字节是否为该整数的最后一个字节15.4.3.每个字节的低7位则用来存储该数的二进制补码（two’s complement representation）15.4.4.整数1可以用一个字节表示，因此它的MSB不需要设置，可表示为0000000115.5.示例15.5.1.10101100 0000001015.5.1.1.10101100 00000010 → 0101100 000001015.5.1.1.1.删掉每个字节的MSB15.5.1.1.1.1.它的作用只是判断当前字节是否是最后一个字节15.5.1.1.1.2.第一个字节的MSB已经设置为1，因为用Varint方法来表示，该数需要多个字节15.5.1.2.0101100 000001015.5.1.2.1.将剩下的两个7二进制位的数据顺序颠倒一下15.5.1.2.1.1.用Varint方法表示时，低位的字节在前15.5.1.3.0000010 010110015.5.1.3.1.将二进制表示转换为十进制数，就得到了最终的数值300