为了除了各种数据时候,解决其各类数据中冗余,压缩数据空间
例如图片总有很大的冗余
文本中某些字符的频率远远大于其他字符串
这章将介绍广泛使用的两种高级算法
本节中使用比特流这个术语表示比特的序列
用字节流表示固定大小的字节序列的比特序列
对于数据压缩,抽象模型如下:
由两个黑盒子组成
压缩盒:能够将一个比特流B转换成压缩后的版本C(B)
展开盒:能够将C(B)转换成B
于是乎,我们最追求的压缩率,就是将|C(B)|/|(B)|最小化
而在此基础之上,出现了无损压缩和有损压缩,
很多数据文件都要求无损压缩,但是对于图像和音乐来说,有损压缩是可接受的
本次学习的算法针对以下四种特点的数据结构
小规模的字母表
较长的连续相同的位或者字符
频繁使用的字符
较长的连续重复的位或者字符
如果获取的比特流中具有以上4中数据特点的任意一种,就能够通过对应方法进行压缩,如果不知道特点,也可以碰碰运气
而且这些方法大多适用性很广