侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

压缩算法的基础(下):赫夫曼编码及其应用

kaixindeken
2021-04-22 / 0 评论 / 0 点赞 / 94 阅读 / 1,393 字

赫夫曼树是为了解决远距离通信(主要是电报)数据传输的最优问题。

比如,我们需要在网络上传输 BADCADEEFD 字符串序列给其他人,每个字符占一个字节,如果要压缩的话可以通过二进制编码的方式进行传输,这个字符串包含了 6 个字符:ABCDEF,我们可以用对应的二进制表示如下:

字符ABCDEF
进制000001010011100101

这样,真正传输的数字编码就是 001000011010000011100100101011,对方接收时按照 3 位一分来译码,如果文章很长,这个序列串也会非常长。

而事实上,不管是英文还是中文,不同字母或汉字的出现频率是不同的,我们能否参考上篇文章按照不同成绩区间分布概率不同构建赫夫曼树的方式将这里的字符编码进行优化呢?

答案是可以,这种通过赫夫曼树对字符数据进行编码的方式就叫做赫夫曼编码。

具体实现方式如下:

上述 BADCADEEFD 中不同字符的出现大致概率是这样的:

字符ABCDEF
概率20%10%10%30%20%10%

合起来是 100%,我们可以这样来构建赫夫曼树(按照上篇文章赫夫曼树构建规则构建):

1.png

然后我们将权值左分支改为 0,右分支改为 1,对应的赫夫曼树如下:

1.png

我们按照这六个字母经过路径的权值对字母进行重新编码:

字符ABCDEF
新编码1110010101001000

这样一来我们就得到了新的字符编码,这就是赫夫曼编码,我们通过赫夫曼编码对字符串 BADCADEEFD 进行重新编码:

  • 原编码二进制串:001000011010000011100100101011(30个字符)
  • 新编码二进制串:1001101101110100100100001(25个字符)

这样一来,我们的数据被压缩了,节省了约 17% 的传输成本,随着字符串长度增加,重复字符增多,效果更明显,并且重复字符越多,压缩效果越好。

最后,在接收方如何解码呢?赫夫曼编码的结果是不同字符编码长短不一,很容易混淆,这就要求发送方和接收方约定好同样的编码规则,就好比二战时期,我们情报人员都要保有同样的密码本一样。

0

评论区