文章目录

• 为什么要编码
• 等长编码与非等长编码
  • 不等长编码方法需要解决的两个关键问题
• 哈夫曼编码树的构造过程
  • 如何写程序
  • 如何编码
• 为什么使用哈夫曼编码
• 如何解码
• 哈夫曼编码的应用

 

为什么要编码

因为计算机只能识别0和1，所以想要其他东西（如：图片、声音、文字、符号等）也能被计算机所识别，就需要把它们变为0和1。

计算机目前还无法表示的信息：如味道、痛觉等。

等长编码与非等长编码

• 等长编码：ASCII码（a：0110 0001）、区位码（王4585）等。
• 非等长编码：哈夫曼编码、费诺编码（Fano Coding）等。

ASCII码：ASCII (American Standard Code for Information Interchange)：美国信息交换标准代码是基于拉丁字母的一套电脑编码系统，主要用于显示现代英语和其他西欧语言。它是最通用的信息交换标准，并等同于国际标准 ISO/IEC 646。ASCII第一次以规范标准的类型发表是在1967年，最后一次更新则是在1986年，到目前为止共定义了128个字符

区位码：1980年，为了使每个汉字有一个全国统一的代码，我国颁布了汉字编码的国家标准：GB2312-80《信息交换用汉字编码字符集》基本集，基本集共收入汉字6763个和非汉字图形字符682个。整个字符集分成94个区，每区有94个位。每个区位上只有一个字符，因此可用所在的区和位来对汉字进行编码，称为区位码，它的前两位叫做区码，后两位叫做位码。

哈夫曼编码：哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

费诺编码：1949年费诺(R.M. Fano)提出了一种编码方法，称之为费诺码或Fano码。它属于概率匹配编码，但一般也不是最佳的编码方法。

不等长编码方法需要解决的两个关键问题

1. 编码尽可能短
   我们让使用频率最高的字符编码最短，使用频率低的编码长一些。
   这样可以提高压缩率，节省空间，也能提高处理和通信速度。
   例如五笔输入法。

2. 不能有二义性
   二义性：一词多义，表述不准确，因此不适合用来描述算法。

例如：如果ABCD这四个字符这样编码：A-0 B-1 C-01 D-10，如果现在有一串数字0110，该怎样翻译呢？
显然这就出现了很多种翻译方式：ABBA、ABD、CD等，因此这样的编码就是存在二义性的，不能准确表述事物。

经过系统研究，发现中文有很强的二义性，而英语则没有很强的二义性，这也就是为什么英文更适合用来表达意思。

• 如何消除二义性？
  解决的办法是：任何一个字符的编码不能是另一个字符编码的前缀，即前缀码特性。

哈夫曼编码树的构造过程

1. 选择与合并
   从序列中选择值最小的两个节点，使用值最小的两个节点作为左右子树，构造新的树，新的树的值为左右子树之和。

• 注意
  使用之最小的两个节点构建新的树时，应该将值较小的的节点作为左子树，权值较大的节点作为右子树。
  当存在两个值相同时，将深度较小的作为左子树或右子树均可，因此具有相同带权节点的哈夫曼树不唯一。

1. 增加与删除
   从序列中删除值最小的两个节点，然后将新创建的节点加入序列经过一次合并以后，序列的节点数目减一。（减少两个节点，新增一个节点）

2. 重复操作
   不断的重复上述两个步骤，直到序列只剩下一个元素为止，即最后哈夫曼树的根节点。
   至此，哈夫曼树的构造完成。

• 哈夫曼树的一个特点
  树的带权路径长度（WPL）最小。

• 树的带权路径长度(Weighted Path Length of Tree，简记为WPL)

带权路径长度公式：

其中W为节点的权值，l为路径长度。

• 哈夫曼树的带权路径长度：
  
• 其他二叉树的带权路径长度：
  

如何写程序

1. 构造哈夫曼树
   （1）定义结点：父结点、左孩子、右孩子、值

• 对于有 n 个叶子结点的哈夫曼树：结点总数为 2n - 1

为实现方便，将叶子结点集中存储在前面部分 1~n 个位置，而后面的 n-1 个位置存储其余非叶子结点。对两种结点初始化。

（2）建哈夫曼树，从叶子结点中选两个值最小的结点组成非叶子结点。

• 注意非叶子结点是没有权值的，他只是由叶子结点相加得到的值。

1. 对哈夫曼树进行编码
   从根结点出发
   判断这个结点是否有左分支，如果有，就标0
   判断这个结点是否有右分支，如果有，就标1

2. 把编码输出

• 代码实现如下：

在这里插入代码片

如何编码

在哈夫曼树的节点的左分支标0，右分支标1

把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的字符编码

如下图所示：

为什么使用哈夫曼编码

• 两个优点

1. 解决了编码的前缀问题（避免二义性）
2. 与等长编码相比编码长度更短

如何解码

从哈夫曼树根开始，对待译码电文逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一但到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。

如图所示，解码后的内容为：yujialingtuwei（俞家岭突围）

哈夫曼编码的应用

• 网络搭建
  交流频率搞的网站可以离服务器近一些，反之远一些。

• 通信编码

• 图像压缩