为什么霍夫曼的编码算法比原来的尺寸占用更多的位?
Why Huffman's coding algorithm takes more bit than the original size?
我给定的字符串是“Today_is_Monday”。如果我对这个字符串应用霍夫曼编码算法。
如果不进行编码,字符串的总大小为 (15*8) = 120
位。
编码后大小为 (10*8 + 15 + 49) = 144
位。
据我所知,霍夫曼算法用于减小尺寸。但是为什么编码后的大小比原来的大?
我所做的更多细节如下
谢谢。
霍夫曼编码优化消息长度,给定频率 table。你如何处理频率 table 由你决定。
用于超短消息的应用程序通常假定发送方和接收方都事先知道的静态频率table,因此不必发送。
需要发送频率table的应用程序通常会执行额外的优化。可以通过仅按字母顺序传输每个符号的长度来传达树。然后可以对长度本身进行霍夫曼编码。
文字太短,概率分布函数看起来均匀。如果出现频率(或多或少)相同,则输入字符串会非常接近随机噪声。不可能以一般方式压缩随机噪声,压缩很可能比输入序列长,因为还需要添加一些元数据,如编码 table.
相比之下,考虑对字符串进行编码:aaaaaaaaaaaaaaa
.
如果尝试对较长的通用英文文本进行编码,您会注意到在某个时候,编码字符串的大小将开始变得比原始文本短得多。这是因为编码序列频率将开始产生更大的影响 - 最频繁出现的字符将使用尽可能短的代码进行编码,并且因为它重复了很多次,其较短的大小将支配原始字符的大小。
不存在保证压缩所有可能输入的可逆压缩算法。如果有,那么您可以重复地为它提供自己的输出,并最终将任何输入文件减少到 1 位。对于任何初始输入文件。
因此,一定有一些输入是任何特定算法都无法压缩的。
正如其他人所解释的,您发现了 Hoffman 无法压缩的输入。
我给定的字符串是“Today_is_Monday”。如果我对这个字符串应用霍夫曼编码算法。
如果不进行编码,字符串的总大小为 (15*8) = 120
位。
编码后大小为 (10*8 + 15 + 49) = 144
位。
据我所知,霍夫曼算法用于减小尺寸。但是为什么编码后的大小比原来的大?
我所做的更多细节如下
谢谢。
霍夫曼编码优化消息长度,给定频率 table。你如何处理频率 table 由你决定。
用于超短消息的应用程序通常假定发送方和接收方都事先知道的静态频率table,因此不必发送。
需要发送频率table的应用程序通常会执行额外的优化。可以通过仅按字母顺序传输每个符号的长度来传达树。然后可以对长度本身进行霍夫曼编码。
文字太短,概率分布函数看起来均匀。如果出现频率(或多或少)相同,则输入字符串会非常接近随机噪声。不可能以一般方式压缩随机噪声,压缩很可能比输入序列长,因为还需要添加一些元数据,如编码 table.
相比之下,考虑对字符串进行编码:aaaaaaaaaaaaaaa
.
如果尝试对较长的通用英文文本进行编码,您会注意到在某个时候,编码字符串的大小将开始变得比原始文本短得多。这是因为编码序列频率将开始产生更大的影响 - 最频繁出现的字符将使用尽可能短的代码进行编码,并且因为它重复了很多次,其较短的大小将支配原始字符的大小。
不存在保证压缩所有可能输入的可逆压缩算法。如果有,那么您可以重复地为它提供自己的输出,并最终将任何输入文件减少到 1 位。对于任何初始输入文件。
因此,一定有一些输入是任何特定算法都无法压缩的。
正如其他人所解释的,您发现了 Hoffman 无法压缩的输入。