霍夫曼编码平均位数霍夫曼编码( 二 )

0.18 ， 0.15｝。
根据字符出现的概率来构造平均长度最短的异字头码字。
霍未曼编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。
霍夫曼编码具有一些明显的特点：
1)
编出来的码都是异字头码，保证了码的唯一可译性。
2)
由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。
3)
编码长度不统一，硬件实现有难度。
4)
对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。
5)
由于"0"与"1"的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能
2、都差不多，个人感觉c++更好学
霍夫曼编码(Huffman Coding)如果一个码的任何一个码字都不是其他码字的前缀，称为前缀码, 也称即时码.
即时码的特点: 1. 唯一可译 2. 译码时没有延时.
二进制霍夫曼编码步骤:
References :
信息论与编码陈运主编第二版
什么是霍夫曼编码霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，根据待压缩数据的特征，一个可压缩掉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 (; i2*n; ++i)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
/*构造霍夫曼树*/
for (i=n+1; i2*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次。
abcdef
频度（千字）4513121695
固定代码字000001010011100101
变长代码字010110011111011100
表1一个字符编码问题。大小为100 000个字符的一个数据文件仅包含字符a~f ，每个字符出现的频度如表中所示。如果对每个字符赋予一个三位的编码，则该文件可被编码为300000位。如果利用表中的可变长度编码，该文件可被编码为224000位。
可以用很多种方式来表示这样一个文件。采用固定长度编码，则需要三位二进制数字来表示六个字符：a=000 ， b=001 ， … ， f=101 。这种方法需要300 000来对整个原文件编码。

霍夫曼编码平均位数 霍夫曼编码( 二 )

秒懂生活扩展阅读

霍夫曼编码平均位数霍夫曼编码( 二 )