哈夫曼树(Huffman Code)

定义

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

特点

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

使用场景

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

构建Haffuman树

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

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

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

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

1. 根据权重构建Huffman树

• 从权重最小的开始构建树的叶子节点，即a与n

构建A与N

• 同样再构建权重排序后的最小的叶子节点，即u与m

构建U与M

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

构建O与,

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

构建O与,与E的子树

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

构建新子树

• 同理构建F与L的子树

构建F与L的子树

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

最优二叉树

• 最终在树的左右子树中，加入0与1的编码，而对应的编码也就是Huffman编码。 部分编码如下：

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

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