什么是霍夫曼编码

哈夫曼编码是什么？~

霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。

霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，根据待压缩数据的特征，一个可压缩掉20%~90%。这里考虑的数据指的是字符串序列。要理解霍夫曼编码，先要理解霍夫曼树，即最优二叉树，是一类带权路径长度最短的树。

路径是指从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。

树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积，树的带权路径长度为树中所有叶子结点的带权路径长度之和.

霍夫曼树是指所有叶子结点的二叉树中带权路径长度最小的二叉树.

当给定了n个叶子结点的权值后，构造出的最优二叉树的结点数目m就确定了，即m=2n-1,所以可用一维结构树组来存储最优二叉树

#define MAXLEAFNUM 50 /*最优二叉树中最大叶子树目*/

struct node{

char ch; /*当前结点表示的字符，对于非叶子结点，此域不用*/

int weight; /*当前结点的权值*/

int parent; /*当前结点的父结点的下标，为0时表示无父结点*/

int lchild,rchild; /*当前结点的左，右孩子结点的下标，为0时表示无孩子结点*/

}HuffmanTree[2 * MAXLEAFNUM];

typedef char *HuffmanCode[MAXLEAFNUM + 1]；

创建最优二叉树

void createHTree(HuffmanTree HT, char *c, int *w, int n)

{

/*数组c[0..n-1]和w[0..n-1]存放了n个字符及其概率，构造霍夫树HT*/

int i, s1, s2;

if (n <= 1)

return;

/*根据n个权值构造n棵只有根结点的二叉树*/

for (i=1; i<=n; i++)

{

HT[i].ch = c[i-1];

HT[i].weight = w[i-1];

HT[i].parent = HT[i].lchild = HT[i].rchild = 0;

}

for (; i<2*n; ++i)

{

HT[i].parent = 0;

HT[i].lchild = 0;

HT[i].rchild = 0;

}

/*构造霍夫曼树*/

for (i=n+1; i<2*n; i++)

{

/*从HT[1..i-1]中选择parent为0且weight最小的两棵树，其序号为s1和s2*/

select(HT,i-1,s1,s2);

HT[s1].parent = i;

HT[s2].parent = i;

HT[i].lchild = s1;

HT[i].rchild = s2;

HT[i].weight = HT[s1].weight + HT[s2].weight;

}

}

应用霍夫曼编码

假设有一个包含100 000个字符的数据文件要压缩存储。各字符在该文件中的出现频度见表1。仅有6种不同字符出现过，字符a出现了45000次。

a b c d e f

频度（千字） 45 13 12 16 9 5

固定代码字 000 001 010 011 100 101

变长代码字 0 101 100 111 1101 1100

表1 一个字符编码问题。大小为100 000个字符的一个数据文件仅包含字符a~f，每个字符出现的频度如表中所示。如果对每个字符赋予一个三位的编码，则该文件可被编码为300000位。如果利用表中的可变长度编码，该文件可被编码为224000位。

可以用很多种方式来表示这样一个文件。采用固定长度编码，则需要三位二进制数字来表示六个字符：a=000，b=001，…，f=101。这种方法需要300 000来对整个原文件编码。

而可变长度编码是对频度高的字符赋以短编码，而对频度低的字符赋以较长一些的编码。表1显示了这种编码，其中一位串0表示a，四位串1100表示f。这种编码方式需要

（45*1+13*3+12*3+16*3+9*4+5*4）*1000 = 224 000 位

来表示整个文件，即可压缩掉约25%。这其实就是最优字符编码（霍夫曼编码）

前缀编码

我们这里考虑的编码方案中，没有一个编码是另一个编码的前缀。这样的编码称为前缀编码（或许“无前缀编码“是个更好的名字，但是前缀编码是标准的书面语）。

对任何一种二进制字符编码来说编码总是简单的，这只要将文件中表示每个字符的编码并置起来即可。利用表1的可变长度编码，把包含三个字符的文件abc编成

0 . 101 . 100 = 0 101 100,其中“.“表示并置。

在前缀编码中解码也是很方便的。因为没有一个码是其他码的前缀，故被编码文件的开始处的编码是确定的。我们只要识别出第一个编码，将它翻译成原文字符，再对余下的编码文件重复这个解码过程即可。在我们的例子中，可将串001 011 101唯一地分析为0.0.101.1101，因此可解码为aabe。

解码过程需要有一种关于前缀编码的方便表示，使得初始编码可以很容易地被识别出来。有一种表示方法就是叶子为给定字符的二叉树。在这种树中，我们将一个字符的编码解释为从根至该字符的路径，其中0表示“转向左子结点”，1表示“转向右子结点“。如下给出最优二叉树，如图1。

图1

以下给出查找最优二叉树叶子结点编码的算法

typedef char *HuffmanCode[MAXLEAFNUM + 1]；(本文开头也有说明)

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n)

{

/* n个叶子结点在霍夫曼树HT中的下标为1~n,*/

/*第i（1<= i <= n）个叶子的编码存放HC[i]中*/

char *cd;

int i,start,c,f;

if (n<=1)

return;

/*分配n个字节的内存，用来存放当前得到的编码*/

/*n个叶子结点最大的编码长度为n所以分配n个字节*/

cd = (char*)malloc(n)

cd[n-1] = ‘/0’;

for (i=1; i<=n; i++)

{

start = n -1;

for (c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)

/*从叶子结点开始查找编码*/

/*叶子结点的父结点的左子树为叶子结点，则编码为0*/

/*否则就为父结点的右子树，则编码为1*/

if (HT[f].lchild = = c) cd[--start] = ‘0’;

else cd[--start] = ‘1’;

/*分配内存，分配内存的字节数为当前得到的字符编码数*/

HC[i] = (char*)malloc(n-start);

strcpy(HC[i], &cd[start]);

}

free(cd);

}

译码算法为：

从根结点出发，按二进制位串中的0和1确定是进入左分支还是右分支，当到达叶子结点时译出该叶子对应的字符。数据文件（包含编码）未结束，则回到根结点继续进行上述过程。

给出如下函数：

void Decoding(HuffmanTree HT, int n, char *buff)

{

/*利用具有n个叶子结点的最优二叉树（存储在数组HT中）进行译码，叶子的下标*/

/*为1~n，buff指向数据文件的编码序列*/

int p = 2*n -1; /*指向根结点*/

while (*buff)

{

if ((*buff) = = ‘0’) p = HT[p].lchild; /*进入左分支*/

else p = HT[p].rchild; /*进入右分支*/

/*到达一个叶子结点*/

if（HT[p].lchild = = 0 && HT[p].rchild = = 0）

{

printf(“%c”, HT[p].ch);

p = 2*n – 1; /*回到根结点*/

}

buff++;

}

}

---

兴城市13056823721： 霍夫曼编码 - 搜狗百科？
阚要双醋： 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种.Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码).

兴城市13056823721： 什么是霍夫曼编码? - ？
阚要双醋： 霍夫曼(Huffman)编码原理 霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码.属于无损压缩编码. 霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长.这样...

兴城市13056823721： 什么是霍夫乱编码 - ？
阚要双醋： 霍夫曼编码是可变字长编码(VLC)的一种. Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就称Huffman编码.具体维基百科了

兴城市13056823721： 什么是赫夫曼树? - ？
阚要双醋： 1、是一种利用二叉树实现的编码原理 霍夫曼(Huffman)编码原理 霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码.属于无损压缩编码. 霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出...

兴城市13056823721： typedef char **HuffmanCode;是什么意思哦 - ？
阚要双醋： 这表示HuffmanCode是一个char**类型的代名词.char*可以理解为指向一个字符串第一个字的指针.char**可以理解为字符串数组,char **a = new char* [10]; for (int i = 0; i 这就创建了一个a,a[n]代表第n+1个字符串,a[n][m]表示第n+1个字符串的第m+1个字符.

兴城市13056823721： 霍夫曼编码的思想是什么 - ？
阚要双醋： 哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种.uffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作Huffman...

兴城市13056823721： 利用哈夫曼编码进行压缩压缩率一般达到多少? - ？
阚要双醋： 哈夫曼编码压缩率很低的举个例子:用三位二进行数进行的等长编码平均长度为3,而根据哈夫曼树编码的平均码长为: 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87% 其平均码长是等长码的87%. 所以平均压缩率为13%.所以应该是你算法有问题……

兴城市13056823721： Huffman(霍夫曼)编码是如何运算的? - ？
阚要双醋： 霍夫曼(Huffman)编码原理 霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码.属于无损压缩编码. 霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较...

兴城市13056823721： 多媒体技术主要有什么 - ？
阚要双醋： 很巧我们这学期正好就在学多媒体技术,用的是林福宗的那本书,讲的主要是音频格式,各种音频格式的区别,编码技术,霍夫曼编码,算术编码,词典编码等,压缩技术,有损压缩,无损压缩,mepg-1,-2,-4,-7的技术特征及应用,还有图像格式,颜色模型,颜色的空间转换,还有数字电视,因为课时有限,还剩下一些错误校验与校正,另外HTML,JAVASCRIPT等脚本语言都要用到,c++和数据结构也在霍夫曼编码的实现中用到了.