一、问题引入
在计算机中需要用0-1字符串作为代码来表示信息，为了正确解码，必须要求任何字符的代码不能作为其他字符代码的前缀，这样的码称为二元前缀码。二元前缀码的存储通常采用二叉树结构，令每个字符作为树叶，对应这个字符的前缀码看作根到这片树叶的一条路径，规定每个结点通向左儿子的边记作0，通向右儿子的边记作1。
不同学符在信息中出现的频率不同．设 C ={x1,x2,...,xn}是 n 个字符的集合，xi的频率是 f(xi), i =1,2,..., n ，那么存储一个字符所使用的二进制位数的平均值是：
其中 是表示字符 的二进制位数，也就是的码长。由于一个二元前缀码对应了一棵二叉树，码字就是这棵树的树叶，表示码字的二进制 数就是从根到这片树叶的路径长度，即树叶的深度．那么存储一个字符的平均二进制位数恰好就是这棵树在给定频率下的平均深度，也称为这棵树的权．图中每个码学的频率分别是：
00000：5%，00001：5%，0001:10%，001:15%，
01:25%，100:10%，101:10%，11:20%
存储这个码的一个字符平均需要的二进制位数是：
不难看出，对应于同一组频率可以构造出不同的二叉树这些二叉树所对应的前缀码的平均字符占用的位数也不一样，占用位数越少的压缩效率越高，压缩效率最高、即每个码字平均使用二进制位数最少的前缀码，称为最优二元前缓码，根据上面的分析不难看出，在给定频率下，对应于最优二元前缀码的二叉树是平均深度最小，即权最小的二叉附，如果叶片数 n 怡好是，且每个码字的频率都是1/n，那么这棵树应该是一棵均衡的二叉树，每片树叶都分布在第k层上。但是，对于任意给定的 n 个频率f(x1),f(x2),...,f(xn),如何构道棵对应于最优二元前缀码的二义树？这就是我们需要解决的问题。
二、最优前缀码问题
给定字符集C={x1,x2,...,xn}和每个字符的频率f(xi),i=1,2,...,n，求关于C的一个最优前缀码。一个著名的构造最优前缀码的贪心算法就是哈夫曼（Huffman）算法。
1、伪代码：
算法4.4 最优前缀码问题（哈夫曼算法） Huffman（C）
输入：C={x1,x2,...,xn}是字符集，每个字符频率f(xi),i=1,2,...,n
输出：Q
- 中最小元
- 中最大元
2、算法分析：
该算法在行2需要 O ( nlogn ）的时间对频率排序，行3的 tor 值环执行 O（n）次，循环体内行8的插人操作需要 O（logn ）时间，于是算法时间复杂度是 O（nlogn ).
3、片段代码
声明结构体
struct Huffman{
int weight;//权值
char ch;//字符
int parent;//父亲节点
int left;//左孩子
int right;//右孩子
};
struct Hcode{
int code[100];//字符的哈夫曼编码的存储
int start;//开始位置
};Huffman（C，Q）函数：
void Huffman(char *C,int Q[]){
int n=strlen(C);
int i,j;
for(i=0;i<n;i++){
huffman[i].ch=C[i];
}
for(i=0;i<n*2-1;i++){//哈夫曼节点的初始化
huffman[i].weight=0;
huffman[i].parent=-1;
huffman[i].left=-1;
huffman[i].right=-1;
}
//赋权重
for(i=0;i<n;i++){
huffman[i].weight=Q[i];
// printf("%d\n",huffman[i].weight);
}
//每次找出权重最小的节点，生成新的节点，需要n-1次合并
int a,b,w1,w2;
for(i=0;i<n-1;i++){
a=b=-1;
w1=w2=10000;
for(j=0;j<n+i;j++){ //注意每次在n+i里面遍历
//得到权重最小的点
if(huffman[j].parent==-1&&huffman[j].weight<w1){//如果每次最小的更新了，那么需要把上次最小的给第二个最小的
w2=w1;
b=a;
a=j;
w1=huffman[j].weight;
}
//注意这里用else if而不是if,是因为它们每次只选1个就可以了
else if(huffman[j].parent==-1&&huffman[j].weight<w2){
b=j;
w2=huffman[j].weight;
}
}
//每次找到最小的两个节点后要记得合并成一个新的节点
huffman[n+i].left=a;
huffman[n+i].right=b;
huffman[n+i].weight=w1+w2;
huffman[a].parent=n+i;
huffman[b].parent=n+i;
}
}
以八进制字符集C={0,1,2,3,4,5,6,7}为例，其中字符的频率乘100分别为：
f(0)=f(1)=5，f(2)=10，f(3)=15，f(4)=25，f(5)=f(6)=10，f(7)=20
初始队列 Q ={5.5,10,10,10.15,20.25}，根据算法先找到频率最小的字符0和1做兄弟，其父结点频率是5+5=10，于是队列 Q ={10,10,10,10.15,20.25}．第二步找频率为10和10的两个结点做兄弟，其父结点的频率是20，于是队列 Q ={10,10,15.20,20,25}，第三步还是找频率10和10的两个结点做兄弟，其父结点的频率是20，于是队列 Q ={15,20,20,20,25}．第四步找频率为15和20的结点做兄弟，父结点频率是35，于是队列 Q ={20,20,25,35}．第五步找到的结点频率是20和20，父结点频率是40，于是队列 Q ={25,35,40}。第六步找到的结点频率是25和35，父结点频率是60，于是队列 Q ={40,60}，最后一步把剩下的两个结点做兄弟得到树根，队列 Q =(100)，算法结束，从而得到一个二叉树（注意：如果频率相同的项不止一个，所构造的树与算法的实现有关，可能解不是唯一的，但是权值相等）。有了这棵树，根据树根到叶片的路径，就可以得到对应的二元前缀码．
4、完整代码
//算法4.4 最优前缀码问题（哈夫曼算法） Huffman（C）
//输入：C={x1,x2,...,xn}是字符集，每个字符频率f(xi),i=1,2,...,n
//输出：Q
#include<stdio.h>
#include<string.h>
struct Huffman{
int weight;//权值
char ch;//字符
int parent;//父亲节点
int left;//左孩子
int right;//右孩子
};
struct Hcode{
int code[100];//字符的哈夫曼编码的存储
int start;//开始位置
};
struct Huffman huffman[100];//最大字符编码数组长度
struct Hcode code[100];//最大哈夫曼编码结构体数组的个数
void Huffman(char *C,int Q[]){
int n=strlen(C);
int i,j;
for(i=0;i<n;i++){
huffman[i].ch=C[i];
}
for(i=0;i<n*2-1;i++){//哈夫曼节点的初始化
huffman[i].weight=0;
huffman[i].parent=-1;
huffman[i].left=-1;
huffman[i].right=-1;
}
//赋权重
for(i=0;i<n;i++){
huffman[i].weight=Q[i];
// printf("%d\n",huffman[i].weight);
}
//每次找出权重最小的节点，生成新的节点，需要n-1次合并
int a,b,w1,w2;
for(i=0;i<n-1;i++){
a=b=-1;
w1=w2=10000;
for(j=0;j<n+i;j++){ //注意每次在n+i里面遍历
//得到权重最小的点
if(huffman[j].parent==-1&&huffman[j].weight<w1){//如果每次最小的更新了，那么需要把上次最小的给第二个最小的
w2=w1;
b=a;
a=j;
w1=huffman[j].weight;
}
//注意这里用else if而不是if,是因为它们每次只选1个就可以了
else if(huffman[j].parent==-1&&huffman[j].weight<w2){
b=j;
w2=huffman[j].weight;
}
}
//每次找到最小的两个节点后要记得合并成一个新的节点
huffman[n+i].left=a;
huffman[n+i].right=b;
huffman[n+i].weight=w1+w2;
huffman[a].parent=n+i;
huffman[b].parent=n+i;
}
}
//打印每个字符的哈夫曼编码
void PrintHuffmanTree(int n){
struct Hcode CurrentCode; //保存当前叶子节点的字符编码
int CurrentParent; //当前父节点
int c; //下标和叶子节点的编号
int i,j;
for(i=0;i<n;i++){
CurrentCode.start=n-1;
c=i;
CurrentParent=huffman[i].parent;
//父节点不等于-1才可以遍历
while(CurrentParent!=-1){
//判断当前父节点的左孩子是否为当前值，是则取0，否则取1
if(huffman[CurrentParent].left==c){
CurrentCode.code[CurrentCode.start]=0;
}
else{
CurrentCode.code[CurrentCode.start]=1;
}
CurrentCode.start--;
c=CurrentParent;//保存当前变量i
CurrentParent=huffman[c].parent;
}
//把当前叶子节点信息保存到编码结构体里面
for(j=CurrentCode.start+1;j<n;j++){
code[i].code[j] = CurrentCode.code[j];
}
code[i].start=CurrentCode.start;
}
}
int main(){
int n=0,i,j;
char C[]={'0','1','2','3','4','5','6','7','\0'};
int Q[]={5,5,10,15,25,10,10,20};
n=strlen(C);
Huffman(C,Q);
PrintHuffmanTree(n);
for(i=0;i<n;++i){
printf("字符%c的哈夫曼编码为:",huffman[i].ch);
for(j=code[i].start+1;j<n;++j){
printf("%d",code[i].code[j]);
}
printf("\n");
}
return 0;
}
运行结果：
文章来源：https://www.toymoban.com/news/detail-768752.html
文章来源地址https://www.toymoban.com/news/detail-768752.html
到了这里，关于【贪心法】最优前缀码（Huffman哈夫曼算法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
