huffman编码怎样计算? 最好是有一个实例.
霍夫曼编码具有一些明显的特点:
1) 编出来的码都是异字头码,保证了码的唯一可译性。
2) 由于编码长度可变。因此译码时间较长,使得霍夫曼编码的压缩与还原相当费时。
3) 编码长度不统一,硬件实现有难度。
4) 对不同信号源的编码效率不同,当信号源的符号概率为2的负幂次方时,达到100%的编码效率;若信号源符号的概率相等,则编码效率最低。
5) 由于"0"与"1"的指定是任意的,故由上述过程编出的最佳码不是唯一的,但其平均码长是一样的,故不影响编码效率与数据压缩性能。
设某个Huffman编码加权和为sigma(Ai*Pi),若存在更优的非H编码,不妨设其中与H编码中权重Pi的位置Ai与Pj的位置Aj调换位置(Pi>Pj),则有Pi*Aj+Pj*Ai>Pi*Ai+Pj*Aj,整理得(Pi-Pj)*Aj>(Pi-Pj)*Ai,即Aj>Ai,与H编码矛盾,因此不存在更优的编码。
为了便于说明,我们先进行一些定义。原始数据:需要被压缩的数据
压缩数据:被压缩过的数据
n:字母表的长度
a〔,j〕:字母表中第j个字符
t:已处理的原始数据中字符的总个数
k:已处理数据中各不相同字符的个数
显然1j,kn
在压缩开始前,需要引进一个空叶结点,它的重量值始终为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〕为初始的当前结点,重复地将当前结点与具有同样重量的序号最大的结点进行交换,并使得后者的父结点成为新的当前结点,直到遇到根结点为止。
不知道你学的是什么,但是给你一个代码吧,是对26个大写英文字母以及空格键的编码,译码:
#define MAXSIZE 256
#include<iostream>
using namespace std;
#include<cstring>
typedef char ElemType;
typedef struct
{
ElemType ch;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char* *HuffmanCode;
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n);
//w存放n个字符的权值,构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
void 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 HTree;
HuffmanCode HCode;
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<<"哈夫曼编码为:"<<endl;
HuffmanCoding(HTree,HCode,weight,27);
cout<<"************************************************"<<endl;
cout<<"\t\t************编码************"<<endl;
cout<<"请输入一段字符(空格和大写英文字母):"<<endl;
c=getchar();
while(c!='\n')
{
len++;
chars[len]=c;
c=getchar();
}
cout<<"编码后结果是:"<<endl;
for(i=1;i<=len;i++)
{
for(j=1;j<=27;j++)
{
if(chars[i]==HTree[j].ch)
cout<<HCode[j];
}
}
cout<<"\n请输入一个01构成的电文"<<endl;
cin>>code;
cout<<"原文为:"<<endl;
Decoding(HTree,code);
return 0;
}
///////////////////Huffman.cpp////////
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
if(n<=1)
return;
int m,i;
m=2*n-1;
HT=new HTNode[m+1];
for(i=1;i<=n;i++)
{
if(i==1)
HT[i].ch=' ';
else
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].weight;
}
//-----从叶子到根逆向求每个字符的哈夫曼编码-----
int start,f,c;
char *cd;
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].parent;f!=0;c=f,f=HT[f].parent)
if (HT[f].lchild == c)
cd[--start]='0';
else
cd[--start]='1';
HC[i] = new char [n-start];
strcpy(HC[i],&cd[start]);
}
delete []cd;
cout<<"空格的哈夫曼编码为:"<<HC[1]<<endl;
for(i=2;i<=n;i++)
cout<<HT[i].ch<<"的哈夫曼编码为:"<<HC[i]<<endl;
}
void Decoding(HuffmanTree HT,char *buff)
{
int m,p;
for(m=1;HT[m].parent!=0;m++)//只有根节点的parent为零
p=m; //求根节点
p++;
while (*buff!= '\0'&& p!= 0)
{
if ((*buff)=='0')
p = HT[p].lchild; //进入左分支
else
p = HT[p].rchild; //进入右分支
buff++;
if (!HT[p].lchild &&!HT[p].rchild)//进入叶子结点
{
cout << HT[p].ch;
p = m; //重新从树根出发进行译码
}//if
}//while
}//Decoding
void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
int i,j;
unsigned min=65535;
if(n<=1)
return;
for(i=1;i<=n;i++)
{
if(HT[i].weight<min&&HT[i].parent==0)
{
j=i;
min=HT[i].weight;
}
}
s1=j;
min=65535;
for(i=1;i<=n;i++)
{
if(HT[i].weight<min&&HT[i].parent==0&&i!=s1)
{
j=i;
min=HT[i].weight;
}
}
s2=j;
} // Select
Huffman(霍夫曼)编码是如何运算的?
霍夫曼(Huffman)编码原理 霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度。步骤进行:l)将信号源的...
什么是哈夫曼编码?
哈夫曼编码是一种编码方式,它是一种线性的前缀编码方式,它利用了信源符号的统计特性,将出现概率高的符号用短码编码,出现概率低的符号用长码编码。这样可以使得编码后的平均码长最短,可以最大化压缩效果。哈夫曼编码是1952年由David A. Huffman提出的,通常使用哈夫曼树来实现。哈夫曼树是一种带权...
什么是哈夫曼编码
详情请查看视频回答
霍夫曼解码原理是什么
霍夫曼解码就是根据霍夫曼树,根据二进制码找到对应的叶子结点并得到原符号的过程。总之霍夫曼编码是在编码过程中基于符号出现的概率,将符号进行编码,使得出现概率大的符号编码长度短,出现概率小的符号编码长度长。这样就可以达到压缩数据的目的。而霍夫曼解码就是根据霍夫曼树还原出编码前的符号。
哈夫曼编码是什么?
哈夫曼编码是在哈夫曼树的基础上进行的,其编码步骤为:(1)利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树,并在叶子结点上注明对应的字符。(2)在树中从根结点到叶子结点都有一条路径,对路径上的各分支约定指向左子树根的分支表示“0”码,指向右子树的分支表示“1”码。(2)取从根...
三进制的哈夫曼编码怎么算的?
5、则m-s的数值就是m进制哈夫曼编码第一部所需要取的符号个数。(既然我们与理想状况相差s个,那我们第一步就用m-s个进行编码吧)k其实就是信源缩减的次数。说的有点绕,理一理思路我再回来更口语化地修改答案。例题:信源有8个信源符号,所以X = 3 + 2 * 3 = 9 > 8 理想情况下是9个...
哈夫曼编码原理
只要传送时不出错,收端仍可分离各个码字,不致混淆。哈夫曼编码,又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码。
霍夫曼编码
霍夫曼(Huffman)在1952年提出 是一种从下到上的编码方法,即从叶子逐步往上生成编码树 编码算法实际上是一个构造霍夫曼树的过程(根据资料出现频率的多寡来建造的树,霍夫曼树的树叶节点用以储存资料元素 ( Data Element ) ,若该元素出现的频率越高,则由该元素至树根所经过的节点数越少)(1) 对...
哈夫曼编码码长怎么算
设某信源产生有五种符号u1、u2、u3、u4和u5,对应概率P1=0.4,P2=0.1,P3=P4=0.2,P5=0.1。霍夫曼编码是变长编码,思路:对概率大的编的码字短,概率小的编的码字长,这样一来所编的总码长就小,这样编码效率就高。上面那样求是不对的,除非你这6个码字是等概率的,各占1\/6。应该用...
哈夫曼编码的原理是什么?
每次相 加时都将“0”和“1”赋与相加的两个概率,读出时由该符号开始一直走到最后的“1”, 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好。哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把...
董希瑞科: 传统哈夫曼编码借助树形结构构造,算法实现时使用链表或静态链表结构,空间的每个结点内有左、右子树、双亲指针.本文给出了哈夫曼编码的另一种实现算法,该算法抛开树结构,用一个数组模拟二叉树的创建过程并得到符号的深度,然后根据这一信息为每个符号分配编码.对于大型文件来说,整个编码、译码过程中需要的空间比传统哈夫曼编码要少得多
塔城市19584702640: huffman编码怎样计算? 最好是有一个实例. - ?
董希瑞科: 为了便于说明,我们先进行一些定义. 原始数据:需要被压缩的数据 压缩数据:被压缩过的数据 n:字母表的长度 a〔,j〕:字母表中第j个字符 t:已处理的原始数据中字符的总个数 k:已处理数据中各不相同字符的个数 显然1„j,k„n 在压缩开始前,需要引进一个空叶结点,它的重量值始终为0.在以后的压缩和解压过程中,如果k
塔城市19584702640: 哈夫曼编码的编码方法怎样? ?
董希瑞科: 哈夫曼编码是一种编码方式,是可变字长编码(VLC)的一种.以哈夫曼树-即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩. 在计算机信息处理中,“...
塔城市19584702640: 什么是变字长最佳编码原理 - ?
董希瑞科: 哈夫曼编码(Huffman Coding),又称霍夫曼编码最佳编码定理:在变字长码中,对于出现概率大的信息符号编以短字长的码;对于出现概率小的信息符号编以长字长的码,如果码字长度严格按照符号概率的大小的相反顺序排列,则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度.Huffman编码步骤:概率统计,得到n个不同概率的信号;将n个信源信息符号的n个概率,按概率大小排序;将最后两个小概率相加,概率个数减为n-1;将n-1个概率重新排序;再将最后两个小概率相加,概率个数减为n-2;如此反复n-2次,得到只剩两个概率序列;以二进制码元(0,1)赋值,构成Huffman码字.
塔城市19584702640: Huffman(霍夫曼)编码是如何运算的? - ?
董希瑞科: 霍夫曼(Huffman)编码原理 霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码.属于无损压缩编码. 霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较...
塔城市19584702640: huffman编码方式 - ?
董希瑞科: 先计算每一个字符出现的次数(即频率) 在根据频率构建huffman (一个最优二叉树)之后根据0左1右 求出每个字符对应的0 1 编码 这样就行了
塔城市19584702640: 如何证明huffman编码是最优编码? - ?
董希瑞科: 设某个Huffman编码加权和为sigma(Ai*Pi),若存在更优的非H编码,不妨设其中与H编码中权重Pi的位置Ai与Pj的位置Aj调换位置(Pi>Pj),则有Pi*Aj+Pj*Ai>Pi*Ai+Pj*Aj,整理得(Pi-Pj)*Aj>(Pi-Pj)*Ai,即Aj>Ai,与H编码矛盾,因此不存在更优的编码.
塔城市19584702640: Huffman编码的算法举例学通信的,只要算法举例就可以,不用编程,就是每一步具体怎么做,书上没有例子,马上要期末考了,急,比如设信号源为 s={s1,s... - ?
董希瑞科:[答案] 出现概率小的在树底,大的在树顶.以达到加权平均最小.
塔城市19584702640: 如何计算压缩比?急!! - ?
董希瑞科: 采用ASCII编码:长度为14*8=112bit 采用Huffman编码: 编码表为: 空格:01 a :111 t :110 i :000 m :1011 s :1010 u :1001 d :1000 e :0011 n :0010 占用长度为:2*3+3*2+3*2+3+6*4=45bit 编码率为45/112=40.2%