霍夫曼压缩的最后一个字节

Question

我想知道在Huffman Copression中处理最后一个字节的最佳方法是什么.我在C++中有一些很好的代码,它可以很好地压缩文本文件,但是目前我必须写入我的编码文件也编码字符数(好吧,它等于输入文件大小),因为不知道如何处理最后一个字节更好.

例如,要压缩的最后一个char是'a',哪个代码是011,我只是开始写入新字节,所以最后一个字节看起来像:011 +大约5位垃圾,我将它们作为例如0结束.当我编码这个编码文件时,可能会发生代码00000(或者用较少的零)是某些字符的代码,所以我在编码文件的末尾会有一些垃圾字符.

正如我在第一段中所写,我通过在编码文件中保存输入文件的字符数来避免这种情况,并且在编码时,我正在读取编码文件以达到该数字(而不是EndOfFile,不要去那些例子) 5个零).它不是真正有效,编码文件的大小增加了长数.

我怎样才能更好地处理这个问题？

PS.对不起我不完美的英语,我希望有可能理解:-)

Answer 1

您的方法(将编码的字节数写入文件)是一种非常合理的方法.如果你想尝试不同的途径,你可以考虑发明了一种新的"伪EOF"字符标志着输入的结束(我会记为□).无论何时你想压缩字符串s,你都要压缩字符串s □.这意味着当您构建编码树时,您将包含□字符的一个副本,以便您具有□的唯一编码.然后,当您将字符串写入文件时,您将正常写出字符串的位字符,然后写出□的位模式.如果有剩余的位,你可以随意设置它们.

这种方法的优点是,当你解码文件时,如果你在任何时候找到了□字符,你可以立即停止解码位,因为你知道你已经命中了文件的末尾.这不需要您存储在任何地方写出的字节数 - 编码隐式标记其自己的端点.

这种设置的缺点是它可能会增加某些字符使用的位模式的长度,因为除了所有其他字符之外,还需要为□指定位模式.

我教授入门编程课程,我们使用霍夫曼编码作为我们的任务之一.我们让学生使用上述方法,因为它比在文件内容之前写出位数或字节数要容易一些.有关详细信息,您可以查看本讲义或课程中的这些讲座幻灯片.

希望这可以帮助!