哈夫曼解压缩

描述

利用哈夫曼编码进行信息通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,要求在发送端通过一个编码系统对传输数据预先编码(压缩);在接收端将传来的数据进行译码(解压缩复原)。试为这样的通信站编写一个哈夫曼编译码系统—哈夫曼压缩/解压缩算法。

要求

1)通信内容可以是任意的多媒体文件;

2)自己设定字符大小,统计该文件中不同字符的种类(字符集、个数)、出现频率(在该文件中);

3)构建相应的哈夫曼树,并给出个字符的哈夫曼编码;

4)对源文件进行哈夫曼压缩编码形成新的压缩后文件(包括哈夫曼树);

5)编写解压缩文件对压缩后文件进行解码还原成源文件。

6)不同源文件形成的压缩文件中应该包含相应的哈夫曼树结构,以便解压缩系统直接译码还原之。

需求分析

  • 需要统计各种文件类型二进制形式的字符出现频数

  • 依据频数构建哈夫曼树,并将哈夫曼树编码记录

  • 依据哈夫曼树编码进行压缩

  • 利用文件的哈夫曼树进行解压缩

实战

大部分参考 哈夫曼压缩与解压缩_飞鸿踏雪泥

源代码

程序思想:

  • 首先构建数据的存储应用类型结构体

    结构体对应文件struct.h

  • 每次读入一个字节,一个字节有256种,统计这256种字符各自的频度。生成256种字符的hash数组,各个字符对应各个字符频度,便于查询。

    对应文件charFrequency.c

  • 构建 haffman 树,首先按照字符频度使用快速排序对各字节进行排序。用一个数组存储排序后的字节顺序。然后进行一个递归,对最小的两个字节生成一个树,并把树放到第二小字节的位置,用冒泡排序将这个生成树摆到合适的位置,然后再对减去位置一的最小的两个字节生成一个树,直到位置减到只剩下两个,并返回最后生成的树。

    对应文件createHaffmanCode.c

  • 构建 haffman 编码。创建一个字节种类长度的数组,中序递归的向数组中加入或者改变某个位置的‘0’'1',并按照深度为树添加编码。并将编码加入hash数组,便于查询。

    对应文件createHaffmanCode.c

  • 按照 haffman 树,读取文件字节。每读取一个字节,将 1 bit 的0或者1输入新建的压缩文件中。并且在压缩文件的文件头输入文件的后缀名和字符频度。便于解压。

    对应文件zip.c

  • 解压时读取文件头,创建相应文件,用字符频度构建 haffman 树。读取文件头之后的位,并按照 haffman 树0/1向左子树或右子树读取,直到读到叶子节点,并输出叶子节点上的字符到解压文件中。

    对应文件unzip.c

输入和输出数据

输入为各种类型的文件如filename.xxx

压缩输出为filename.huf

解压输出为filename.xxx

简单评价

无法处理只有两个字节的文件,或者字符种类少于2种的文件。

空间复杂度非常高,当字节种类很多时,生成的haffman树会需要很多空间来生成。

解压时间复杂度比压缩时间复杂度多很多,因为每个字节都需要操作指针指向子树,并判断。

生成haffman树的算法并不是最优解,例如当字符频度相似时,生成时第一次排序会比较慢。但是还是较好的方式。

事后

老师提醒用两字节读取编码和一个字节读取编码完全不同。

但是显然两个字节进行编码的可能性就会增大到65536个种类。这未必一定是好的。

评论