压缩数据的原因主要有两点：节省保存信息所需的空间和节省传输信息所需的时间。我们将学习的算法之所以能够节省空间，是因为大多数数据文件都有很大的冗余。
我们将会讨论广泛应用的一种初级算法和两种高级算法。这些算法的压缩效果可能不同，取决于输入的特征。文本数据一般能节省 20% ~ 50% 的空间，某些情况下能够达到 50% ~ 90%。
本文提到的性能（对于数据压缩），性能指代的是算法的压缩率，也会考虑压缩用时。
基础模型
数据压缩的基础模型主要由两部分组成，两者都是一个能读写比特流的黑盒子：
- 压缩盒：能够将一个比特流B转化为压缩后的版本C(B)。
- 展开盒：能够将C(B)转化回B。
如果使用|B|表示比特流中比特的数量的话，我们感兴趣的是将|C(B)|/|B|最小化，这个值被称为压缩率。
待添加图片
这种模型叫做无损压缩模型－保证不丢失任何信息，即压缩和展开之后的比特流必须和原始的比特流完全相同。许多种类型的文件都会使用无损压缩， 如果数值数据或者可执行代码。对于某些类型的文件，如图像视频和音乐，有损压缩也是能接受的。此时解释器产生的输出只是与原输入的文件近似。有损压缩算法的评价标准不仅是压缩率，还包括主管的质量感受。
压缩的局限
通用数据压缩
通用性的数据压缩算法是指一个能够缩小任意比特流的算法。但是这样的算法是不存在的：
反证法
假设存在通用压缩算法，那么说明可以用它压缩它自己的输出，从而得到一个更短的比特流，循环直到比特流的长度为0，显然是错误的。
统计法
后续讲解
根据统计法可以得出，对于任意数据压缩算法，将长度1000位的随机比特流压缩为一半的概率最多为$1/2^{500}$
不可判定性
压缩一个文件最好的办法就是找出创造这些数据的程序。
可以证明最优数据压缩（找到能够产生给定字符串的最短程序）是一个不可能判定的问题：我们不但不可能找到能够压缩任意比特流的算法，也不可能找到最佳的压缩算法。
这些局限性所带来的实际影响要求无损压缩算法必须尽量利用被压缩的数据流中的已知结构：
- 小规模的字母表
- 较长的连续相同的位或字符
- 频繁使用的字符
- 较长的连续重复的位或字符
