[译文]5分钟系列-快速理解Huffman Coding(霍夫曼编码)

原文链接What is Huffman Coding?

什么是霍夫曼编码 ( Huffman Coding )

霍夫曼编码是很多压缩算法的基础,比如著名的 DEFLATE (常用的图片格式 png 就用到了 DEFLATE ) 和 Gzip

为什么要了解霍夫曼编码?

有没有偶然的瞬间,或是通勤途中的地铁上,抑或是入眠前的思绪畅游,脑海中有如下疑问:

  • 如果做到无损压缩数据?
  • 为什么同一个文件,不同的压缩算法会有不结果(压缩率,压缩/解压时间)?
  • Gzip 是如何工作的?

5 分钟带你走入哈夫曼编码

压缩

假设我们想压缩一段字符串 (哈夫曼编码可以压缩任意数据,本文只是讲解基本原理,选用字符串最容易理解)

通常一段文本中,有些字符出现的频率会比另外一些字符更高;而哈夫曼编码就正是利用了这一点,对这段文本中出现的全部字符重新编码,让出现频率更高的字符占用更少的空间从而达到压缩的目的

就用 Yoda 大师的经典名言 “do or do not” 来当作示例,这句话一共 12 个字符。按照计算机默认编码格式 (关于编码格式,你可以参考UTF百科),每个英文字符占用 8 比特 (bit) , 一共占用96比特 ;那么采用霍夫曼编码以后一共占用多少比特呢?

首先,我们得先构建哈夫曼树。出现频率最高的字符,就距离树的根节点最近。依次类推,下图就是字符串 “do or do not” 的哈夫曼树

最常见的字符 ‘o’和 ‘ ‘ (空格) 距离根节点只有 2 步,而最不常见的 t 则距离根节点有 3 步。哈夫曼编码最神奇的事情来了,我们存储的不再是字符本身,而且存储从根节点到达它的路径。具体什么意思呢?

我们从根节点开始,然后沿着树像要编码的字符前进。如果走了左侧路径,则标记为 0,走了右侧路径,我们则标记为 1

因此,字符 d 的编码为:’100′ ,而字符 d 的默认编码是:’ 01100100 ‘,整个字符串编码以后的结果如下:

最终需要消耗 96 比特的字符串,采用哈夫曼编码以后,只需要 29 字节,足足压缩了2/3

解压

怎么解压呢?就是照着存储路径,依次从哈夫曼树拿到该路径对应的真实字符

聪明的你是不是早已想到,如果我只把压缩后的数据发给别人,别人没有对应的哈夫曼树,就没法解压。是的,大概来说有 3 种办法:

  • 将哈夫曼树和压缩后的文本一起发给对方,就可以根据你发的哈夫曼树来解压
  • 可以双方都同意同一颗已知的哈夫曼树,压缩和解压就可以都用它
  • 发送足够的信息,对方可以根据这些信息构建出哈夫曼树从而达到解压的目的(Gzip的工作方式),但是请注意:同样的信息,也有可能构建出不同的哈夫曼树,因此发送的信息要确保构建的哈夫曼树一致

课堂疑问

  • 上面的示例,为什么哈夫曼树是 4 层 ?所有的哈夫曼树都是 4 层吗?
  • 一大段 中文文本 和 英文文本 ,压缩比例会一样吗 ?

课外延申