哈夫曼树(Huffman Code)

定义

给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,则称之为最优二叉树,也就是哈夫曼树。

特点

  • 变长编码,压缩数据,减少数据量大小
  • 数据都存储在叶子节点,解码时不会出现重复编码的冲突
  • 根据数据的权重(出现频率)来决定编码,进一步压缩数据

使用场景

主要用于文件的不等长编码的无损压缩,如视频、文件等

构建Haffuman树

假如,有一个文件中有一串文本:hello,huffman,接着需要对该文件进行压缩。

在压缩前,文本使用ASCII进行编码,每一个字符都占用1个字节,8bit,那么写入文件后会占用13个字节,共占用104bit。

如果使用Huffuman编码进行压缩的话,会需要这几个步骤:

  1. 统计字符出现的次数,统计权重

字符

h

f

l

e

o

,

u

m

a

n

次数

2

2

2

1

1

1

1

1

1

1

  1. 根据权重构建Huffman树
  • 从权重最小的开始构建树的叶子节点,即an

构建A与N

  • 同样再构建权重排序后的最小的叶子节点,即um

构建U与M

  • 同理,构建O,的叶子节点

构建O与,

  • 接着开始找到权重最小的两个节点,也就是O,组成的子树以及E,来构建一个新的子树,然后再根据权重重新排序

构建O与,与E的子树

  • 接着按照权重再构建子树,也就是通过后两个子树构建新的子树

构建新子树

  • 同理构建FL的子树

构建F与L的子树

  • 最后,通过一层层子树的堆叠,就变成了以下的样子,而这就是最终的Huffman树

最优二叉树

  • 最终在树的左右子树中,加入01的编码,而对应的编码也就是Huffman编码。 部分编码如下:

字符

A

H

L

M

编码

0000

11

011

0011

由于所有的字符都在Huffman树的叶子节点上,所以编码与解码不会有冲突。

通过这棵编码树,就可以对文件进行编解码,来压缩与解压文件了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券