97c935be3e00b0fa16cd95fedab49001
霍夫曼编码

1 概述

  霍夫曼编码是一种基于最小冗余编码的压缩算法。最小冗余编码是指,如果知道一组数据中符号出现的频率,就可以用一种特殊的方式来表示符号从而减少数据需要的存储空间。霍夫曼编码过程如下:

2 统计字符频率

  例如:有如下字符串:
  A A C B C A A D D B B A D D A A B B

得到各个字符频率如下表:

字符 频率
A 7
B 5
C 2
D 4

3 构造霍夫曼树

3.1 霍夫曼树定义

  霍夫曼树:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。结合第2节中的字符串,将字符串出现频率作为权值。

3.2 构造流程

(1)选取权值最小和次小的节点作为左右子树,构造一棵二叉树。
(2)将步骤1构造的二叉树的根节点的权值设置为,左右子树之和。
(3)去除步骤1中已经选过的节点,将新的二叉树的根节点加入至待选集合
(4)继续重复步骤1,直至仅剩一个元素未选中。

3.3 图解过程

  通过构造的霍夫曼树可以看出,权值越大的节点距离根节点越近,其深度越小,权值越小的节点,距离根节点越远,其深度越大。

4 霍夫曼编码

  在经过步骤3,构造出霍夫曼树后,对霍夫曼树执行遍历。将向左子树路径标记为0,向右子树的路径标记为1。则标记后的霍夫曼树为:

图4.1

图4.1

  按照图4.1进行霍夫曼编码为:

数据 编码
A 0
B 10
C 111
D 110

  A A C B C A A D D B B A D D A A B B 编码后的数据长度为:
  0 0 111 10 111 0 0 110 110 10 10 0 110 110 0 0 10 10 编码长度为35。

  若采用等长编码为:

数据 编码
A 00
B 01
C 10
D 11

  则A A C B C A A D D B B A D D A A B B对应编码为:
  00 00 10 01 10 00 00 11 11 01 01 00 11 11 00 00 01 01
  编码长度为36。可以看出使用霍夫曼编码可以缩短数据编码长度,达到数据压缩的效果。当字符数目较少时不能体现霍夫曼编码带来的压缩效果,但是当字符数目较多时,霍夫曼编码的压缩效率将显著提高。

5 代码实现

```

include

include

using namespace std;

struct Node
{
double weight; //存储权值
string ch; //存储字符
string code; //编码
int lchild, rchild, parent;//分别存储左孩子、右孩子、父节点位置
};

void Select(Node huffTree[], int *a, int *b, int n)//找权值最小的两个a和b
{
int i;
double weight = 0; //找最小的数
for (i = 0; i <n; i++)
{
if (huffTree[i].parent != -1) //判断节点是否已经选过
continue;
else
{
if (weight == 0)
{
weight = huffTree[i].weight;
*a = i;
}
else
{
if (huffTree[i].weight < weight)
{
weight = huffTree[i].weight;
*a = i;
}
}
}

top Created with Sketch.