文件压缩 之RLE算法和哈弗曼算法

文件压缩

1.什么是文件？

文件是存储在磁盘等媒介中的一种形式，磁盘是以字节为单位存储的，所以文件也是。存储文字的叫文本文件，存储图形的叫图像文件。

2.压缩算法之RLE算法

RLE算法是使用“数据 * 重复次数”来表示数据的一种方法。比如数据AAAAASSRRR，使用RLE算法表示为:A5S2R3，从10个字节压缩到6个字节。

但这种算法只适用于有重复字节出现的文件，比如图像文件，但并不实用与于文本文件。

3.压缩算法之哈弗曼算法

哈弗曼算法是将出现频率高的字符用尽量少的位数来表示。比如一个文本文件中“I”出现100次、“L”出现3次，如果一个字符用一个字节表示则为103 * 8 = 824bit，如果“I”用2bit，“L”用10bit表示，则为100 * 2 + 3 * 10 = 230bit。

哈弗曼算法会为每个要压缩的文件构造最佳的编码体系，再以此为基础进行压缩和解压。压缩后的文件存着哈弗曼编码信息和压缩后的数据。

注意:压缩后的文件也是以字节为单位存储的

4.使用哈弗曼树构造编码体系

可以看到，出现频率最高的字符对应编码位数最短，并且编码不会出现歧义。解压时以位为单位对数据进行排查，与哈弗曼树比较看是否找到相应编码。

5.可逆压缩与不可逆压缩

顾名思义，可逆压缩指解压后与压缩前一模一样，比如文本文件必须是可逆压缩。不可逆压缩则相反，比如图像文件只要解压后不影响使用就没必要一模一样。

6.说明

本文是《程序是怎样跑起来的》读书笔记，压缩算法有很多种，这里只介绍了其中两种，由于各文件压缩需求不同，至今学界也不能提出一种万能压缩算法。所以我们也有机会原创自己的压缩算法，压缩算法的拙劣需要花费功夫。

如发现什么错误，请兄弟们指正，大家一起进步！