哈夫曼编码算法
- 格式：doc
- 大小：224.54 KB
- 文档页数：5
usingnamespacestd;
#defineLEFT(i) (2*i)
#defineRIGHT(i) (2*i+1)
structnode
{
charc;
intfreq;
node* left;
node* right;
};
voidExchange( node& x, node& y )
{
node temp = x;
《算法设计与分析》上机报告
姓名：
学号：
日期：
上机题目：
哈夫曼编码算法
实验环境：
CPU: 2.10GHz ;内存: 6G ;操作系统：Win7 64位;软件平台：Visual Studio2008 ;
一、算法设计与分析：
题目:
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。
else
smallest = i;
if( r<=n && a[r].freq < a[smallest].freq )
smallest = r;
if( smallest != i )
{
Exchange( a[i], a[smallest] );
i = smallest;
}
else
break;
}
}
voidBuildMaxHeap( node a[],intn )
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
二、核心代码：
node* huffman(node C[],int n)
node* pRes = huffman(a,6);
cout<<endl<<"生成的Huffman树为a(前序遍括历)："<<endl;
print(pRes);
cout<<endl;
system("pause");
return0;
}
}
node* huuildMaxHeap(C,n);
for(inti=1;i<n;i++)
{
node* z =newnode;
z->left = extract_min(C,n-i+1);
z->right = extract_min(C,n - i);
z->freq = z->left->freq + z->right->freq;
{
BuildMaxHeap(C,n);
for(int i=1;i<n;i++)
{
node* z = new node;
z->left = extract_min(C,n-i+1);
z->right = extract_min(C,n - i);
z->freq = z->left->freq + z->right->freq;
C[n - i] = *z;
MaxHeapify(C,n - i,n - i);
}
return &C[1];
}
三、结果与分析：
其中“？”表示该结点没有字符
最优性：
二叉树T表示字符集C的一个最优前缀码，x和y是树T中的两个叶子且为兄弟，z是它们的父亲。若将z当作是具有频率f(z)=f(x)+f(y)的字符，则树T’=T-{x,y}表示字符集C’=C-{x, y}∪{ z}的一个最优前缀码。因此，有：
C[n - i] = *z;
MaxHeapify(C,n - i,n - i);
}
return&C[1];
}
voidprint(node* pRes)
{
if(pRes != NULL)
{
cout << pRes->c <<'-'<<pRes->freq<<',';
print(pRes->left);
print(pRes->right);
}
}
intmain()
{
node a[7]={{' ',0},{'e',9},{'f',5},{'c',12},{'a',45},{'d',16},{'b',13}};
cout<<"输入的表为："<<endl;
for(inti=1;i<7;i++)
cout << a[i].c <<'-'<<a[i].freq<<',';
如果T’不是C’的最优前缀码，假定T”是C’的最优前缀码，那么有
，显然T”’是比T更优的前缀码，跟前提矛盾！故T'所表示的C'的前缀码是最优的。
由贪心选择性质和最优子结构性质可以推出哈夫曼算法是正确的，即HuffmanTree产生的一棵最优前缀编码树。
附录（源代码）
算法源代码（C++描述）
#include<iostream>
{
for(inti=n/2;i>0;i--)
MaxHeapify(a,i,n);
}
node *extract_min(node a[],intn)
{
node *temp =newnode;
*temp = a[1];
a[1] = a[n];
MaxHeapify(a,1,n-1);
returntemp;
哈夫曼编码步骤：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。
x = y;
y = temp;
}
voidMaxHeapify( node a[],inti,intn )
{
while( 1 )
{
intl = LEFT( i );
intr = RIGHT( i );
intsmallest;
if( l<=n && a[l].freq < a[i].freq )
smallest = l;
#defineLEFT(i) (2*i)
#defineRIGHT(i) (2*i+1)
structnode
{
charc;
intfreq;
node* left;
node* right;
};
voidExchange( node& x, node& y )
{
node temp = x;
《算法设计与分析》上机报告
姓名：
学号：
日期：
上机题目：
哈夫曼编码算法
实验环境：
CPU: 2.10GHz ;内存: 6G ;操作系统：Win7 64位;软件平台：Visual Studio2008 ;
一、算法设计与分析：
题目:
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。
else
smallest = i;
if( r<=n && a[r].freq < a[smallest].freq )
smallest = r;
if( smallest != i )
{
Exchange( a[i], a[smallest] );
i = smallest;
}
else
break;
}
}
voidBuildMaxHeap( node a[],intn )
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
二、核心代码：
node* huffman(node C[],int n)
node* pRes = huffman(a,6);
cout<<endl<<"生成的Huffman树为a(前序遍括历)："<<endl;
print(pRes);
cout<<endl;
system("pause");
return0;
}
}
node* huuildMaxHeap(C,n);
for(inti=1;i<n;i++)
{
node* z =newnode;
z->left = extract_min(C,n-i+1);
z->right = extract_min(C,n - i);
z->freq = z->left->freq + z->right->freq;
{
BuildMaxHeap(C,n);
for(int i=1;i<n;i++)
{
node* z = new node;
z->left = extract_min(C,n-i+1);
z->right = extract_min(C,n - i);
z->freq = z->left->freq + z->right->freq;
C[n - i] = *z;
MaxHeapify(C,n - i,n - i);
}
return &C[1];
}
三、结果与分析：
其中“？”表示该结点没有字符
最优性：
二叉树T表示字符集C的一个最优前缀码，x和y是树T中的两个叶子且为兄弟，z是它们的父亲。若将z当作是具有频率f(z)=f(x)+f(y)的字符，则树T’=T-{x,y}表示字符集C’=C-{x, y}∪{ z}的一个最优前缀码。因此，有：
C[n - i] = *z;
MaxHeapify(C,n - i,n - i);
}
return&C[1];
}
voidprint(node* pRes)
{
if(pRes != NULL)
{
cout << pRes->c <<'-'<<pRes->freq<<',';
print(pRes->left);
print(pRes->right);
}
}
intmain()
{
node a[7]={{' ',0},{'e',9},{'f',5},{'c',12},{'a',45},{'d',16},{'b',13}};
cout<<"输入的表为："<<endl;
for(inti=1;i<7;i++)
cout << a[i].c <<'-'<<a[i].freq<<',';
如果T’不是C’的最优前缀码，假定T”是C’的最优前缀码，那么有
，显然T”’是比T更优的前缀码，跟前提矛盾！故T'所表示的C'的前缀码是最优的。
由贪心选择性质和最优子结构性质可以推出哈夫曼算法是正确的，即HuffmanTree产生的一棵最优前缀编码树。
附录（源代码）
算法源代码（C++描述）
#include<iostream>
{
for(inti=n/2;i>0;i--)
MaxHeapify(a,i,n);
}
node *extract_min(node a[],intn)
{
node *temp =newnode;
*temp = a[1];
a[1] = a[n];
MaxHeapify(a,1,n-1);
returntemp;
哈夫曼编码步骤：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。
x = y;
y = temp;
}
voidMaxHeapify( node a[],inti,intn )
{
while( 1 )
{
intl = LEFT( i );
intr = RIGHT( i );
intsmallest;
if( l<=n && a[l].freq < a[i].freq )
smallest = l;
