dap*_*hez 9 compression math huffman-code
这是我在学校设置中遇到的一个问题,但它一直困扰着我,所以我决定在这里问一下.
在霍夫曼压缩中,固定长度序列(字符)用可变长度序列编码.代码序列长度取决于源字符的频率(或概率).
我的问题是:最小的最高字符频率是多少,该字符将由一个位编码？
事实证明答案是0.4,也就是说,如果最高频率p是p> = 0.4,则保证相应字符的1位代码.换句话说,这是一个充分的条件.
p> = 1/3也是必要条件.也就是说,可能存在0.4> p> = 1/3的示例,并且最短的代码是1位,但是如果p <1/3则没有类似的情况.
推理这种方法的方法是查看代码树的构造方式,特别是在3个最后存活的子树的频率上.约翰森出现了一个证明,"关于二元霍夫曼码的冗余",1980年(不幸的是这是付费链接).
通常,大约50%的输入符号流必须由给定符号组成,以便霍夫曼将其编码为单个位.其原因在于,由于霍夫曼编码的工作原理(一个符号的编码不能成为另一个符号的前缀),通过对一个符号进行编码,您需要每个其他符号的第一个比特值相反(即如果一个符号被编码为0,则其他所有内容必须以1加号开始至少再多一位).由于您为任何给定的位长度消除了一半可能的编码空间,因此您需要获得一种方法来编码至少一半的输入符号以便实现均衡.
请注意,有一种特殊情况,符号空间仅包含3个符号.在这种情况下,具有最大频率的任何符号将被编码为1比特(因为其他两个将是未选择的第一比特值的第二比特变化) - 如果2个或更多具有相同更大的概率,任何一个都可以编码.因此,在3符号的情况下,理论上可以将具有例如34%概率的符号编码为单个比特(例如0),而其他两个概率可以具有33%或更低的概率并且被编码为10和11.
因此,如果您正在考虑所有可能性,那么技术上任何1/3或更高的内容都可能被编码为单个位(在3个符号的情况下).