【开卷数据结构 】哈夫曼编码

在上文中,我们了解了哈夫曼树的基本概念和构造算法,那么哈夫曼树究竟有什么用呢?接下来讲的哈夫曼编码就是哈夫曼树的应用。

目录

哈夫曼编码

固定长度编码

哈夫曼编码

前缀编码

文件的编码与译码

编码

译码


94536690f848438fab30aa17191a6ea2.png

哈夫曼编码

如果有一段文字【ABCDEF】要网络传输给别人,在进行数据压缩时,最简单的编码方法就是固定长度编码。

固定长度编码


Q:什么是固定长度编码

A:在数据通信中,若对每个字符用相同的二进制位表示,称这种编码方式为固定长度编码。


有一段文字BADCADFEED ,我们可以用相应的二进制的数据表示,如图所示

字母 A B C D E F
二进制字符 000 001 010 011 100 101

这样真正传输的数据就是编码后的 【001000011010000011101100100011三十个字符),对方接收时可以按照3位一分来译码。如果一篇文章很长,这样的二进制串也将长的非常的可怕,那么有没有什么方法可以对其进行压缩的吗?


哈夫曼编码

我们假设各字母出现的频率如下

假设六个字母的频率为 A:27  B:8  C:15  D:15  E:30  F:5 ,合起来正好是 100 ,那就意味着,我们完全可以重新按照赫夫曼树来规划它们。

【开卷数据结构 】哈夫曼编码_第1张图片

 我们将左分支权值改为0,右分支权值改为1,那么该哈夫曼树就变成了

【开卷数据结构 】哈夫曼编码_第2张图片

这时,我们对着六个字母用其从树根到叶所经过路径的 0 与 1 来编码,按照新的字母对应的二进制字符对BADCADFEED 进行编码,通过对比可以很明显的发现,字符数量减少了。

  • 固定长度编码:001000011010000011101100100011(共30个字符)
  • 哈夫曼编码:    1001010010101001000111100         (共25个字符)

哈夫曼编码的特点:

  1. 对频率高的字符赋以短编码。
  2. 对频率较低的字符则赋予较长一些的代码。
  3. 从而使得字符的平均编码长度减短,起到压缩数据的效果。
  4. 哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

前缀编码

Q:什么是前缀编码

A:前缀编码是指对字符集进行编码时,要求字符集中任一字符的编码都不是其它字符的编码的前缀。

仔细观察,哈夫曼编码其实就是一种前缀编码

Q:前缀编码有什么优点

A:通过观察前缀编码(哈夫曼编码)【1001010010101001000111100】,以及其对应的哈夫曼树,我们发现不会出现容易混淆的编码,比如不会出现与1000,1001混淆的10,100编码。

【开卷数据结构 】哈夫曼编码_第3张图片

对前缀编码的解析很简单,因为没有一个编码是其他编码的前缀。所以识别出第一个编码,将它翻译成原码,再对余下的编码文件重复同样的解码操作即可。例如,码串 00101100 可被唯一的翻译成 0,0,101,100 .

文件的编码与译码

编码

有了字符集的哈夫曼编码表之后,对数据文件的编码过程是:依次读人文件中的字符c,在哈夫曼编码表HC中找到此字符,将字符c转换为编码表中存放的编码串

译码

对编码后的文件进行译码的过程必须借助于哈夫曼树。具体过程是:依次读入文件的二码,从哈夫曼树的根结点(即HT[m])出发,若当前读入0,则走向左孩子,否则走向右孩子。一旦到达某一叶子HT[i]时便译出相应的字符编码HT[i]。然后重新从根出发继续译码,直至文件结束。

你可能感兴趣的