十七. java数据结构 - 赫夫曼编码概述

1.基本介绍

1. 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法

2. 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。

3. 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间

4. 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码

2. 原理剖析

1.通信领域中信息的处理方式 1-定长编码

赫夫曼编码原理

2.通信领域中信息的处理方式 2-变长编码

信息的处理方式

3.步骤：

构成赫夫曼树的步骤：

1. 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树

2. 取出根节点权值最小的两颗二叉树

3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4. 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

注意事项:

注意, 这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是 *wpl* 是一样的，都是最小的, 最后生成的赫夫曼编码的长度是一样，比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为:

image.png