霍夫曼编码压缩比计算错误排查及压缩文件存储疑问

问题描述 #

我尝试按以下步骤计算霍夫曼编码的压缩比：

1. 计算原始数据大小：

int size= sizeof(inputarr)/sizeof(inputarr[0]);
originalsize = size *(sizeof(int))

得到原始大小为164×4=656字节。
2. 计算编码后数据大小：参考网上示例，用(数值×频率)求和得到总比特数，再转成字节。我的数值列表和频率列表如下：

数值列表：2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,19,20,21,23,24,26,28,29,31,35,37,48,49,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,103
频率列表：8,1,12,4,10,4,9,2,2,3,2,3,1,2,2,1,3,2,1,1,1,1,1,1,1,1,1,1,1,2,3,3,2,5,4,5,5,5,5,7,7,6,4,5,4,4,3,2,1

计算得(数值×频率)总和为8499比特，转成字节是1062.375字节，压缩比CR=656/1062.375<1，明显不合理。

更新疑问：我得到了可正常解压的字符串形式压缩数据（如下），但不知道如何将其存储为比原始文件更小的文件：

0111100000010010110101000001011111001010110111100011010100111101100001110100001110110001001111111101000010111001100101000101100000111101111000011001001011001110111011000011101000011101100011100000111100000010111101100000101010010101111110001110110011110111101000100000110111100101010100111100110101111000111001101010010101100111001010100110110111011100000111000000100010010110111111111000010111111010111001011010010010001111000001010011010101100001001100001011000101000110111110100101101010111001111100100001101000111100001110011000101110101001000111000101110001011011111111110110101100111100101100001101101110010100010011111010111010000001110010011010001000101111111111100110111010101100101100001111110011111000110001000100001110111110110111011111011111100011110100111111110110111001001111100111011001010101110000110010010110101110110110110111011000011110000101001

解决方案 #

一、压缩比计算错误的核心原因 #

你完全混淆了霍夫曼编码长度和符号数值：

• 霍夫曼编码的总比特数计算应该是：每个符号的霍夫曼编码的比特长度 × 该符号的频率，再求和。而不是用符号本身的数值去乘频率。
• 举个例子：频率最高的符号（数值4，频率12）应该对应最短的编码（比如2比特），而频率最低的符号（比如数值3、15等，频率1）对应最长的编码（比如10比特左右）。你之前用数值（比如4）代替编码长度计算，才会得到远大于原始大小的错误结果。

另外，原始数据大小的计算也可以优化：你的所有数值都在0-127范围内，完全可以用uint8_t（单字节）存储，原始大小应为164字节，而非用int存储的656字节——这也是压缩比看起来异常的次要原因。

二、压缩数据的存储优化方案 #

要让压缩后的文件比原始文件小，需要做好以下几点：

1. 将字符串形式的01序列转为二进制字节存储
   你现在的压缩结果是字符串形式的0和1，每个字符占1字节，完全没有压缩效果。正确的做法是把比特流打包成字节：

   • 每8个连续的比特转为一个字节（比如"01111000"转为十进制120，存储为单字节）
   • 最后不足8位的比特补0，同时在文件开头或结尾记录总比特数，解压时去掉补位的0。

2. 紧凑存储霍夫曼编码表/树
   解压必须依赖霍夫曼编码规则，所以需要把编码表（符号+对应编码长度+编码值）或霍夫曼树存入压缩文件。可以用以下方式优化存储：

   • 先按频率从高到低排序符号，用变长编码记录符号的编码长度，再存储编码值；
   • 对于数值连续的符号，可以用区间记录减少存储量。

3. 优化原始数据的基础存储
   如前所述，原始数据不需要用int存储，改用单字节的uint8_t类型，原始大小从656字节降到164字节，压缩后的文件大小更容易低于原始值。

4. 验证霍夫曼树的正确性
   确保构建霍夫曼树时，频率高的符号分配更短的编码。可以手动计算几个高频符号的编码长度，再重新计算总比特数，正确的总比特数应该远小于原始数据的比特数（比如原始164字节=1312比特，霍夫曼总比特数应该在800比特以内）。

内容的提问来源于stack exchange，提问作者lena