huffman编码怎样计算? 最好是有一个实例._百度知道
huffman编码怎样计算? 最好是有一个实例.
我有更好的答案
为了便于说明，我们先进行一些定义。 原始数据：需要被压缩的数据 压缩数据：被压缩过的数据 n：字母表的长度 a〔，j〕：字母表中第j个字符 t：已处理的原始数据中字符的总个数 k：已处理数据中各不相同字符的个数 显然1j，kn 在压缩开始前，需要引进一个空叶结点，它的重量值始终为0。在以后的压缩和解压过程中，如果k＜n，我们用它来表示n－k个字母表中还未出现的字符。初始化的哈夫曼树中只有一个根结点和空叶结点。 压缩子程序读进一个字符后，它将该字符加到根结点的右分枝上，而空叶结点仍留在左分枝上，然后将该字符以ASCII码方式输出。解压子程序对其哈夫曼树作同样的调整。 以后每读进一个字符a〔，it〕，压缩子程序都执行以下的步骤：首先它检查a〔，it〕是否出现在编码树中，如果是，压缩子程序就以静态哈夫曼编码中相同的方式对a〔，it〕进行编码；如果a〔，it〕不在编码树中，压缩子程序首先对空叶结点进行编码，然后将a〔，it〕以ASCII码方式输出，最后在编码树中增加两个结点：在空叶结点的右分枝上加入一个新结点，并将a〔，it〕放在里面，然后在其左分枝上加入一个新的空叶结点。 解压子程序对解压树也做同样的调整，因为它和压缩子程序具有相同的哈夫曼树。当它遍历到空叶结点时，解压子程序就从压缩数据中取出一个ASCII字符，然后对解压树做与压缩子程序相同的调整。 每处理一个字符，压缩和解压程序都需要修改各自的哈夫曼树，为了修改的方便，树中每个结点都具有一个序号，它是根据结点的重量由大到小排列而确定的一个递减序列。 对于图1中的例子，现在已处理了32个字符，即t＝32，a〔，it＋1〕＝“b”，此时并不是简单地将叶结点a〔，it＋1〕和它的祖先结点的重量加1，因为这样做之后，该树就不再是哈夫曼树，且各结点的序号也不再是按结点重量由大到小排列而确定的递减序列，结点4和结点6的重量为6，而结点5的重量为5。 动态哈夫曼编码技术的关键就是如何将前t个字符的哈夫曼树调整成一棵前t＋1个字符的哈夫曼树。为了解决上述问题，我们分两步来进行。第一步我们把前t个字符的哈夫曼树转换成它的另一种形式，在该树中只需在第二步中简单地把由根到叶结点a〔，it＋1〕路径上的所有结点重量加1，就可以变成前t＋1个字符的哈夫曼树。其过程就是以叶结点a〔，it＋1〕为初始的当前结点，重复地将当前结点与具有同样重量的序号最大的结点进行交换，并使得后者的父结点成为新的当前结点，直到遇到根结点为止。
采纳率：69%
来自团队：
不知道你学的是什么，但是给你一个代码吧，是对26个大写英文字母以及空格键的编码，译码：#define MAXSIZE 256#include&iostream&#include&cstring&typedef char ElemTtypedef struct{ ElemT
unsigned int parent,lchild,}HTNode,*HuffmanTtypedef char* *HuffmanCvoid HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n);//w存放n个字符的权值,构造哈夫曼树HT,并求出n个字符的哈夫曼编码HCvoid Decoding(HuffmanTree HT,char *buff);//将二进制编码翻译回信息原文，m是树根的编号void Select(HuffmanTree HT,int n,int &s1,int &s2);//选择parent为0且weight最小的两个节点,序号为是是s1,s2/////////////////////////main.cpp/////////int main(){ int i,j,len=0; char c,chars[MAXSIZE+1],code[MAXSIZE+1]; HuffmanTree HT HuffmanCode HC int weight[28]={'\0',186,64,13,22,32,103,21,15,47,57,1,5,32,20,67,63,15,1,48,51,80,23,8,18,1,16,1}; cout&&&哈夫曼编码为:&&& HuffmanCoding(HTree,HCode,weight,27); cout&&&************************************************&&& cout&&&\t\t************编码************&&& cout&&&请输入一段字符(空格和大写英文字母):&&& c=getchar(); while(c!='\n') {
chars[len]=c;
c=getchar(); } cout&&&编码后结果是:&&& for(i=1;i&=i++) {
for(j=1;j&=27;j++)
if(chars[i]==HTree[j].ch)
cout&&HCode[j];
} } cout&&&\n请输入一个01构成的电文&&& cin&& cout&&&原文为:&&& Decoding(HTree,code); return 0;}///////////////////Huffman.cpp////////void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ if(n&=1)
int m,i; m=2*n-1; HT=new HTNode[m+1]; for(i=1;i&=n;i++) {
HT[i].ch=' ';
HT[i].ch=(i+63);
HT[i].weight=w[i];
HT[i].parent=0;
HT[i].lchild=HT[i].rchild=0; } for(;i&=m;i++) {
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=HT[i].rchild=0; } for(i=n+1;i&=m;i++) {//在HT[1..n-1]选择parent为0且weight最小的两个结点,其序号为s1,s2
int 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]. } //-----从叶子到根逆向求每个字符的哈夫曼编码----- int start,f,c; char * HC = new char*[n+1];
cd = new char [n];
cd[n-1] = '\0'; for(i=1; i&=n; i++)
start = n-1;
for(c=i,f=HT[i].f!=0;c=f,f=HT[f].parent)
if (HT[f].lchild == c)
cd[--start]='0';
cd[--start]='1';
HC[i] = new char [n-start];
strcpy(HC[i],&cd[start]);
} delete [] cout&&&空格的哈夫曼编码为:&&&HC[1]&& for(i=2;i&=n;i++)
cout&&HT[i].ch&&&的哈夫曼编码为:&&&HC[i]&& }void Decoding(HuffmanTree HT,char *buff){
int m,p; for(m=1;HT[m].parent!=0;m++)//只有根节点的parent为零
//求根节点 p++; while (*buff!= '\0'&& p!= 0) {
if ((*buff)=='0')
p = HT[p]. //进入左分支
p = HT[p]. //进入右分支
if (!HT[p].lchild &&!HT[p].rchild)//进入叶子结点
cout && HT[p].
p = //重新从树根出发进行译码
}//if }//while}//Decoding
void Select(HuffmanTree HT,int n,int &s1,int &s2){
unsigned min=65535;
for(i=1;i&=n;i++)
if(HT[i].weight&min&&HT[i].parent==0)
min=HT[i].
min=65535;
for(i=1;i&=n;i++)
if(HT[i].weight&min&&HT[i].parent==0&&i!=s1)
min=HT[i].
s2=j;} // Select
为您推荐：
其他类似问题
您可能关注的内容
huffman的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。第三方登录：Huffman编码_图文_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&10W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
Huffman编码
&&信息论与信源编码实验报告
阅读已结束，下载本文需要
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩9页未读，
定制HR最喜欢的简历
你可能喜欢话说huffman编码是如何识别编码长度的？ | 死理性派小组 | 果壳网 科技有意思
895487人加入此小组
感觉上huffman编码没有编码开始标记啊，那它是如何识别某段数是1个编码还是几个？（对不起，表述不太清楚，将就下吧）
科学松鼠会成员，信息学硕士生
huffman是一种前缀码，所以不用识别编码长度……
话说哈夫曼编码就是为了解决这个问题啊算法可以使用二叉树方法来获得，不过我忘了。。。。
观察Huffman树的结构，每一个字符的位置都在树叶上，所以你只需按照0, 1在树上走，走到树叶了就得到一个字符，然后从新从root出发。换句话说，Huffman编码是非前缀编码（不会存在某一个编码是另一个编码的前缀）
huffman编码的每个编码都不为另外一个编码的前缀，所以不会有二义性反之那么一段编码究竟是理解成某个字符的，还是另一个字符的前缀呢，这个时候编码的长度就是必须的了
(C)果壳网&&&&京ICP证100430号&&&&京网文[-239号&&&&新出发京零字东150005号&&&&
违法和不良信息举报邮箱：&&&&举报电话：&&&&&&&&