初始数据压缩

在计算机中，一切文件均是以字节为单位进行保存，文件包括文本文件、图片、程序等。

1B(1字节) = 1Byte = 8 bite 可以表示 256 中字节数据

2⌃8 = 256

在任何情况下，文件中的字节数据都是 连续 存储的。

文件是字节数据的集合体。

例子：AAAAAABBCCCCDDDEE 17 个字符

把文件中的内容用 “数据 x 重复次数” 的形式来表示的压缩方法称为 RLE (Run Length Encoding, 行程长度编码)

使用这种压缩方式的上文表示如下：

A6B2C4D3E2 5个字符

那么其压缩率为： 5 ÷ 17 = 0.29 = 29％

RLE 算法的缺点：

不适合文本文件的压缩

原因：文本文件中同样的字符连续出现的部分不多

This is a girl. ==＞ T1h1i1s1 i1s1 a1 g1i1r1l1.1

很明显的是：压缩后的文件大小反而变大，效果与愿景相悖。

哈夫曼编码是根据日常文本中各字符的出现频率来决定各个字符的编码的数据长度。

哈夫曼算法是指，为各压缩对象文件分别构造最佳的编码体系，并以该编码体系为基础来进行压缩。

用哈夫曼算法压缩过的文件中，存储着哈夫曼编码信息和压缩过的数据。

如果仅仅依照 “出现频率最高的字符使用最短的位数编码来表示”，不免会造成识别混乱的现象。而在真实的哈夫曼算法中，通过哈夫曼树构造编码体系，可以避免此现象的发生。

例子: AAAAAABBCCCCDDDEE

具体看一下压缩比：

17 x 8 = 136 很明显是 17B

利用哈夫曼算法压缩文件后的大小：

2 x 13 + 3 x 4 = 48 文件大小为 6B

压缩率为：
6 ÷ 17 = 35％

使用哈夫曼树后，出现频率越高的数据占用的数据位数越少，而且数据的区分也可以很清晰的实现。

Q：哈夫曼算法为什么可以达到这么好的效果？

A：通过上图我们发现，在用枝条连接数据时，我们是从频率较低的数据开始的，这意味着出现频率越低的数据到达根部的枝条数越多，而枝条数越多，编码的位数就随之增多了。

我们把压缩后能够还原到压缩状态的压缩称为可逆压缩，无法还原的称为非可逆压缩。

— From 『程序是怎么跑起来的』

玛斯特・布兰迪