关于哈夫曼压缩的评论请求

最佳压缩是将整个文件作为一个单一的令牌,并使用零长度的哈夫曼代码对其进行压缩。这会给你一个无限的压缩比。不幸的是,对哈夫曼代码的描述将非常大。

这是正确的,但并不像听起来那么令人惊讶。

有两段数据必须传输以解码哈夫曼编码的字节流。编码流(当然)是必需的,但是字典也是必需的,它允许您正确地构建Huffman树来执行解码。

使用较大的令牌对数据进行编码总是会导致较小的编码流。不幸的是,除非您有一些非常具体和特殊的数据,否则较大的令牌也会使您的字典大小意外增加。退化情况(由Mark Byers的答案引用)将导致整个未压缩的数据流是一个单一的令牌,而编码流是一个单一的位,从而导致绝对没有压缩。

因此,哈夫曼编码(几乎和所有东西一样)是一种权衡。要在编码文件的效率和字典的大小之间取得平衡可能很困难。我从未根据数据特征执行过实际的分析,以找出各种理想的令牌大小,但我认为字节往往会被使用,因为这是一个简单的划分点,通常会导致一些真正的压缩。我知道在大学的时候,我做过一次四字节令牌的练习,但我不能诚实地说它比一字节令牌更好。

当然,也有可能作弊,而不是动态地构建字典以获得真正贪婪的压缩,您可以使用预先构建的树并用它进行压缩。这样就可以避免传输字典,但解码器也必须使用相同的字典来解码数据。

阿拉伯科德,你的假设是正确的。

附带说明:许多8位哈夫曼编解码器不仅压缩了一个字节的256个自然符号。它们还具有一个或多个特殊符号。这些都是用来检测哈夫曼流的结束或切换从一个哈夫曼树到另一个…

完全正确。总之,在实现压缩算法时几乎没有什么用处(除了智力挑战或培训),因为几乎每种语言都在其标准库中有它们。

顺便说一下,哈夫曼编码总是与算术编码相同或更糟。哈夫曼编码被使用了很多年,因为算术编码直到最近才获得专利,而且因为哈夫曼编码有点容易实现。 如今,在设计一种新的压缩算法时,没有太多理由再使用哈夫曼。应始终使用算术。

哈夫曼压缩法是一种相当古老的压缩方法,并没有这样使用。它包含在课程中教授的基本压缩方法中。考虑到许多文件(如jpeg、pdf或jar)都是经过压缩的,运行普通的Huffman压缩不会给您带来太多好处。

我这么说是因为我这样做了。即使您经常优化符号表,这也适用。