霍夫曼编码详解
计算机通常用同样多的比特存储每个字母,在普通 ASCII 中是 8 个。这样做简单却浪费,因为有些字母比其他字母常见得多。1951 年,一位学生找到了为每个符号分配各自长度编码的最佳方法:常见符号用短码,罕见符号用长码,而且构造方法简单到只需几行就能写完。如今,你打开的几乎每个压缩文件、图像和声音里都有霍夫曼编码。
常见符号用短码
早在 19 世纪 30 年代,摩尔斯电码就用到了这个思想:英语中最常见的字母 E 只是一个点,而 Q 是划划点划。只要有些符号比其他符号出现得更频繁,这样的编码就能节省时间和空间。但可变长度带来了一个问题,摩尔斯电码用停顿解决了它:怎么知道一个编码在哪里结束、下一个从哪里开始?每个符号又该分配多长的编码,才能让总长度尽可能小?
前缀码
只要没有哪个编码是另一个编码的开头,第一个问题就消失了。使用编码 A = 0、B = 10、C = 110 和 D = 111 时,比特 0101100 只能读作 A B C A:一旦已读的比特构成一个编码,这个编码就完整了。这样的前缀码恰好对应于符号位于叶子上的二叉树,其中每个左分支代表 0,每个右分支代表 1。选择一种编码,就是选择一棵树。
霍夫曼的构造
从每个符号一片叶子开始,权重是它出现的次数。取出最轻的两棵树,把它们合并到一个新节点下,新节点的权重是它们之和,重复这一步,直到只剩一棵树。这就是整个算法。罕见的符号最先被合并,最终位于树的深处,编码较长;常见的符号最后才被合并,留在靠近顶部的位置,编码较短。使用优先队列时,对于 n 个符号,所需时间与 n log n 成正比。
为什么它是最优的
在一棵最优的树中,总可以把两个最罕见的符号作为兄弟节点放在最深层:把它们与原来在那里的符号交换,只会让总长度变短。把它们合并成一个权重为两者之和的符号,剩下的就是少了一个符号的同一个问题,因此贪心的这一步永远不会错过最优解。所用的总比特数等于所有内部节点的权重之和,而合并过程让这个和尽可能小。
用学期论文代替考试
1951 年,麻省理工学院(MIT)研究生戴维·霍夫曼选修了罗伯特·法诺的信息论课程。法诺让学生们二选一:参加期末考试,或者写一篇学期论文,研究如何找到最高效的二进制编码。霍夫曼几乎要放弃这篇论文了,这时他发现,自下而上地构建树,而不是像香农-法诺方法那样自上而下地拆分,总能得到最优结果。他在 1952 年发表了这一方法;学生的方法胜过了他的教授与克劳德·香农共同提出的方法。
接近熵
克劳德·香农证明,平均而言,没有哪种编码每个符号使用的比特数能少于信源的熵。当每个概率都是二分之一的幂时,霍夫曼编码恰好达到熵,而且每个符号永远不会比熵高出整整 1 比特。当某个符号非常常见时,这个差距就很重要:一个占 99% 的符号仍然至少需要 1 个完整的比特,尽管它只携带约 0.015 比特的信息。算术编码以及较新压缩器中的非对称数字系统避开了这一限制。
无处不在的霍夫曼编码
霍夫曼编码很少单独使用,而是构成许多格式的最后一个阶段。ZIP、gzip 和 PNG 中使用的 Deflate 先用引用替换重复内容,再用霍夫曼编码写出结果。JPEG 用它来编码图像经过变换后剩下的数字,MP3 用它来编码音频数据,传真机用它来编码黑白游程的长度。各种格式通常传送范式霍夫曼编码,这种编码只需存储码长,因为编码本身可以根据码长重建。
动手探索
打开霍夫曼编码构建器,一步一步构建 ABRACADABRA、MISSISSIPPI RIVER、你自己的句子或任何其他文本的树。观察每一步中最轻的两棵树如何合并,点击一片叶子查看它的编码,在编码后的比特中跟踪一个符号,并把总数与定长编码、UTF-8 和熵进行比较。
常见问题
霍夫曼编码和香农-法诺编码有什么区别?
香农-法诺编码从顶部构建树,一次又一次地把符号分成权重几乎相等的两组。它通常不错,但并不总是最优的。霍夫曼编码通过合并最轻的两棵树从底部构建树,总能得到最短的前缀码。
解码器需要这棵树吗?
需要,它需要同一套编码。因此压缩文件会把它存储下来,通常存为范式编码的码长列表,只占几十个字节。对于短文本,这部分开销可能超过节省的量;本构建器只计算编码后的比特。
霍夫曼编码会让文件变大吗?
对于同样的符号,编码后的符号所占的比特永远不会多于定长编码。但编码表也必须存储,所以对于非常短或几乎随机的数据,结果可能比原始数据略大。
克拉夫特不等式说的是什么?
码长为 l₁、l₂、… 的前缀码存在,当且仅当对所有符号求和的 2 的 −l 次幂之和不超过 1。对于每个内部节点都有两个子节点的树,例如每棵至少有两个符号的霍夫曼树,这个和恰好等于 1。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开霍夫曼编码构建器