C++ 中的 Huffman 压缩类
3.64/5 (20投票s)
本文提供了一个动态哈夫曼压缩和解压缩类，以及用C++编写的控制台应用程序。
引言
几年前，我编写了一个动态哈夫曼算法来压缩和解压缩数据。它主要针对数据中某些符号出现的频率高于其他符号的情况（例如，一个数据文件由三个不同的符号组成，它们的总出现次数分别为s1(1000)、s2(200)、s3(30)，那么文件的总长度为1000+200+30=1230字节；编码后，为s1分配1位，为s2和s3分配2位，因此编码后的长度为1*1000+2*(200+30)=1460位=182字节）。在最佳情况下，仅由一个符号组成的文件将以1:8的压缩比进行编码。哈夫曼编码用于图像压缩；然而，在JPEG2000中，使用了算术编码器。
背景
本文旨在仅提供代码，而不是哈夫曼教程。您可以搜索在线教程来了解相关知识。
使用代码
控制台的使用非常简单，可以编码源文件为哈夫曼压缩文件
>>huffman.exe e sourcefile destinationfile
或者将哈夫曼压缩的源文件解码回原始文件
>>huffman.exe d sourcefile destinationfile
哈夫曼类提供了三个函数来使用
void encode(unsigned char *dest, int &csize, unsigned char *sour, int usize)- 用于编码void decode(unsigned char *dest, int &usize, unsigned char *sour)- 用于解码int get_uncompressed_size(unsigned char *sour)- 从哈夫曼编码的数据文件中获取未压缩的文件大小
dest 和 sour 分别是目标和源缓冲区，usize 和 csize 是原始数据的未压缩大小和哈夫曼编码数据的压缩大小。要进行编码，只需在 sour 缓冲区中提供您的数据，并在 usize 中指定其大小。csize 将给出您需要在 dest 指针中提供的压缩哈夫曼数组的大小。确保分配的大小至少与原始数据的大小相同。要进行解码，只需在 sour 中提供您的哈夫曼编码数据，并使用 get_uncompressed_size(sour) 查询您需要分配的 dest 缓冲区的大小。解压缩完成后，usize 将被覆盖为未压缩的数据大小。
关注点
我知道将数据符号及其频率存储到哈夫曼编码文件中会占用空间，并且存在更紧凑的表示方法。