什么是赫夫曼编码?

赫夫曼编码算法是许多压缩算法的基础,如DEFLATE–用于PNG图像格式和GZIP格式。

关注赫夫曼编码的原因?

你将会知道:

  • 我们如何在不丢失任何数据的情况下开展压缩活动?
  • 为什么有些事物的压缩效果比其他的好?
  • GZIP的工作原理是什么?

用最多5分钟的时间:

假设我们想压缩一个字符串(赫夫曼编码可用于任何数据,在这里字符串是一个很好的例子)。

不可避免的是,在被压缩的文本中,一些字符会比其他字符出现得更频繁。赫夫曼编码利用这个现实,对文本进行编码,使最常用的字符比不常用的字符占得空间更少。

对字符串进行编码

让我们用赫夫曼编码来压缩尤达的一句话(部分);“做或不做”。

yoda

"做或不做 "是12个字符的长度,它有几个重复的字符,所以压缩起来很容易。

为了便于讨论,我们假设存储每个字符需要8比特(字符编码完全是另一个话题),所以这个句子将需要96比特,但我们用赫夫曼编码可以做得更好。

我们首先建立一个树状结构。我们的数据中最常见的字符将靠近树的根部,而离根部最远的节点代表不常见的字符。

下面是 "做或不做 "字符串的赫夫曼树。

1

我们的字符串中最常见的字符是’o’(出现4次)和空格(出现3次)。注意,这些字符的路径离根只有两步之遥,而最不常见的字符(‘t’)则有三步之遥。

现在,我们可以不存储字符本身,而是存储通往该字符的路径。

我们从根节点开始,沿着树的方向向我们想要编码的字符前进。如果我们走左边的路径,我们将存储一个 0 , 如果我们走右边的路径,则存储一个 1

下面是我们如何使用这棵树对第一个字符 d 进 行编码。

2

最终的结果是1 0 0 - 3位,而不是8位。 这已经改善了很多!

整个编码后的字符串看起来像以下这样。

3

是29位而不是96位,而且没有丢失数据。这太棒了!

解码我们的字符串

为了解码我们的文本,我们简单地跟踪每个 0 (左分支)或 1 (右分支),直到我们到达其中的一个字符,我们把这个字符写下来,然后再从头开始。

4

发送编码后的文本

但是,等一下…当我们把经过编码后的文本发送给其他人时,他们是不是需要这棵树呢?到哪当然! 另一方也需要同样的赫夫曼树树,以便正确解码文本。

最简单但效率最低的方法是仅将树和压缩文本一起发送。

我们也可以先一起选择一棵树,并使用这棵树对任何字符串进行编码或解码。当我们可以提前预测字符的分布,并且可以在不看到要编码的具体内容的情况下建立一个相对有效的树时,这种方法是可行的(例如,我们可以用英文文本)。

另一个选择是发送足够的信息,让对方和我们建立同样的树(这就是GZIP的工作原理)。例如,我们可以发送每个字符出现的总次数。但我们必须小心:对于同一个文本块,会有多个可能的赫夫曼树,所以我们必须确保要以完全相同的方式构建树。

原文作者 Dave
原文链接 https://www.baseclass.io/newsletter/huffman-coding

推荐阅读
作者信息
AgoraTechnicalTeam
TA 暂未填写个人简介
文章
125
相关专栏
精选文章
85 文章
本专栏仅用于分享音视频相关的技术文章,与其他开发者和 Agora 研发团队交流、分享行业前沿技术、资讯。发帖前,请参考「社区发帖指南」,方便您更好的展示所发表的文章和内容。