Huffman编码
- Huffman编码
- 怎么在matlab中添加霍夫曼编码函数(huffencode())
- 用MATLAB生成哈夫曼编码,急求,在线等
- 哈夫曼编码的matlab程序，求注释！！谢谢了
- 哈夫曼编码的程序实现
- Huffman编码MATLAB实现
- 霍夫曼编码 matlab 文字编码：输入一段字符串（由小写英文字母组成），通过调用函数实现对 字符串的编解码
这个是一个简单的，没有文件导入，需要编码的是自己输入的数组，你将它换成文件读取基本就可以实现对文章中的字符进行Huffman编码，这是我自己曾经做的一个程序，是VC6.0的,没有解码部分，解码部分你反过来推一下算法然后编一下代码就可以了。我还有一个是文件是用matlab作的huffman编码，你要的话给我邮箱，我给你发过去。
#include《iostream.h》
#include《string.h》
#define N 100
typedef struct
{
int wei; //权值
int prt; //父节点
int lch; //左子节点
int rch; // 右子节点
int tmp; //中间变量，tmp=0 还未进行遍历 tmp=1 已近进行过向左遍历 tmp=2 已经进行过左右遍历 向上找到节点
char code;
}huffmantree;
void input();
void print(huffmantree );
void select(huffmantree *HT,int n,int &i,int &j)
{
int k;
i=1;
while(HT.prt!=0)
{
i++;
}
for(k=i+1;k《=n;k++)
{
if((HT.wei))
i=k;
}
j=1;
while((j==i)||(HT.prt!=0))
{
j++;
}
for(k=j+1;k《=n;k++)
{
if((HT.wei)
j=k;
}
}
void huffman(int w,huffmantree *HT,int n) //w存放n个字符的权值
{
int m=2*n-1;
int i,k,j;
huffmantree *p=0;
for(p=HT+1,i=1;i《=m;i++,p++)
{
HT.prt=0;
HT.lch=0;
HT.rch=0;
}
for(p=HT+1,i=1;i《=n;i++,p++)
{
HT;
}
for(p=HT+n+1,i=n+1;i《=m;i++,p++)
{ HT.wei=0;}
for(k=n+1;k《=m;k++)
{
select(HT,k-1,i,j); // 找最小值和次小值的位置
HT.prt=k; // 找到i j 的父节点付给k
HT.rch=j; // 父节点的左右指针分别指向i, j
HT.wei;
}
}
void huffmancoding(huffmantree *HT,int n) //n个叶子结点的huffman编码 从根节点开始编码
{
int BT=2*n-1;
int m=BT;
int l,r,p;
char s1=“1“;
for(int i=0;i《=m;i++) //中间变量赋初值
{ HT.tmp=0; }
strcpy(HT.code,“ “);
while(1)
{
l=HT.lch;
r=HT.rch;
p=HT.prt;
if(p==0&&HT.tmp==2)
break;
if(l==0||r==0)
{
HT.tmp=2; //如果是叶子结点则给中间变量赋值2向上返回一节结点
}
if(HT.tmp==0) //未进行过遍历，开始向左遍历
{
HT.tmp=1; //已经进行过向左遍历
l=HT.lch;
strcpy(HT.code);
strcat(HT.code,s1);
BT=l;
}
else
if(HT.tmp==1)
{
HT.tmp=2;
r=HT.rch;
strcpy(HT.code);
strcat(HT.code,s2);
BT=r;
}
else if(HT.tmp==2)
{
p=HT.prt;
BT=p;
}
}
}
void print(huffmantree HT,int n) //总共n个叶子节点
{
int i;
cout《《“源码：“《《endl;
for(i=1;i《=n;i++)
cout《《HT.wei《《endl;
cout《《“Huffman编码：“《《endl;
for(i=1;i《=n;i++)
{
cout《《HT.code《《endl;
}
}
void input(int w,int n)
{
int t,*p;
int i=0;
cout《《“对应的输入源码出现权值：(以-1结束)“《《endl;
cin》》t;
while(t》=0)
{
p=new int;
*p=t;
w=*p;
i++;
cin》》t;
}
}
void main()
{
int n,m;
cout《《“输入源码个数：“;
cin》》n;
int *w;
w=new int;
input(w,n);
m=2*n-1;
huffmantree *HT;
HT=new huffmantree;
huffman(w,HT,n);
huffmancoding(HT,n);
print(HT,n);
delete w,HT;
}
没用过，但是检查，matlab程序自带huffmancoding基本上你需要
1。测试图像灰度（SIG）找出来，
2，然后统计灰度分布（p），
3。然后生成一个字典（字典），
4。然后就可以直接使用huffmanenco编码，
5。然后huffmandeco恢复。
奇怪的是不是无损压缩哈夫曼编码它，为什么会出现损失呢？等待丹尼尔回答
看看下面的例子：
SIG = repmat（，1,50）;％的数据来编码
符号= ;％不同的数据码元出现在SIG
p值= 的每个数据符号的％概率
字典= huffmandict（码元，p）的;％创建
hcode = huffmanenco字典（SIG，字典）;。％编码
dhsig = huffmandeco数据（hcode，字典）;％解码的代码。
clear all;
I=;
len=length(I);
t=2;
biaozhi=0;
b(1)=I(1);
for i=2:len
for j=1:i-1
if I(j)==I(i)
biaozhi=1;
break;
end
end
if biaozhi==0
b(t)=I(i);
t=t+1;
end
biaozhi=0;
end
fprintf(’信源总长度:
’);
disp(len); %信源总长度
fprintf(’字符:
’);
disp(b );
L=length(b);
for i=1:L
a=0;
for j=1:len
if b(i)==I(j)
a=a+1;
count(i)=a;
end
end
end
count=count/len;%各字符概率
fprintf(’各字符概率:
’);
disp(count);
p=count;
%%%%%%%%%%%%%%%%%%%%%%%%%%%
s=0;
l=0;
H=0;
N=length(p);
for i=1:N
H=H+(- p(i)*log2(p(i)));%计算信源信息熵
end
fprintf(’信源信息熵:
’);
disp(H);
tic;
for i=1:N-1 %按概率分布大小对信源排序
for j=i+1:N
if p(i)《p(j)
m=p(j);
p(j)=p(i);
p(i)=m;
end
end
end
Q=p;
m=zeros(N-1,N);
for i=1:N-1 %循环缩减对概率值排序，画出由每个信源符号概率到1.0 处的路径，
=sort(Q);
m(i,:)=;
Q=;
end
for i=1:N-1
c(i,:)=blanks(N*N);
end
c(N-1,N)=’0’;
c(N-1,2*N)=’1’;
for i=2:N-1 %对字符数组c码字赋值过程，记下沿路径的“1”和“0”；
c(N-i,1:N-1)=c(N-i+1,N*(find(m(N-i+1,:)==1))-(N-2):N*(find(m(N-i+1,:)==1)));
c(N-i,N)=’0’;
c(N-i,N+1:2*N-1)=c(N-i,1:N-1);
c(N-i,2*N)=’1’;
for j=1:i-1
c(N-i,(j+1)*N+1:(j+2)*N)=c(N-i+1,N*(find(m(N-i+1,:)==j+1)-1)+1:N*find(m(N-i+1,:)==j+1));
end
end
for i=1:N
h(i,1:N)=c(1,N*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*N);%码字赋值
ll(i)=length(find(abs(h(i,:))~=32)); %各码字码长
end
l=sum(p.*ll); %计算平均码长
n=H/l; %计算编码效率
fprintf(’编码的码字:
’);
disp(h) %按照输入顺序排列的码字
fprintf(’平均码长:
’);
disp(l) %输出平均码长
fprintf(’编码效率:
’);
disp(n) %输出编码效率
fprintf(’计算耗时time= %f
’,toc);
里面有一段看了几个小时都看不懂
%哈夫曼编码的MATLAB实现（基于0、1编码）：
clc;
clear;
A=;%原概率序列
%A=A/sum(A);
%A=fliplr(sort(A));%按降序排列
T=A;
=size(A);
B=zeros(n,n-1);%空的编码表（矩阵）
for i=1:n
B(i,1)=T(i);%生成编码表的第一列
end
r=B(i,1)+B(i-1,1);%最后两个元素相加
T(n-1)=r;
T(n)=0;
T=fliplr(sort(T));
t=n-1;
for j=2:n-1%生成编码表的其他各列
for i=1:t
B(i,j)=T(i);
end
K=find(T==r);
B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在该列的位置
r=(B(t-1,j)+B(t,j));%最后两个元素相加
T(t-1)=r;
T(t)=0;
T=fliplr(sort(T));
t=t-1;
end
B%输出编码表
END1=sym(’’);%给最后一列的元素编码
END=END1;
t=3;
d=1;
j=2,i=1: 2
//-------------------------------
//从这里开始就看不懂，帮我注释一下行吗？还有这个算法有错吗？我觉得有点问题啊
for j=n-2:-1:1%从倒数第二列开始依次对各列元素编码
for i=1:t-2
if i》1 & B(i,j)==B(i-1,j)
d=d+1;
else
d=1;
end
B(B(n,j+1),j+1)=-1;
temp=B(:,j+1);
x=find(temp==B(i,j))
END(i)=END1(x(d));
end
y=B(n,j+1);
END(t-1)=;
END(t)=;
t=t+1;
END1=END;
END
end
//上面这段求帮忙了，看了几个小时都看不懂，求帮忙每个注释一下
A%排序后的原概率序列
END%编码结果
for i=1:n
=size(char(END(i)));
L(i)=b;
end
avlen=sum(L.*A)%平均码长
H1=log2(A);
H=-A*(H1’)%熵
P=H/avlen%编码效率
#include 《stdio.h》
#include 《stdlib.h》
#include 《string.h》
#include 《math.h》
#define M 100
typedef struct Fano_Node
{
char ch;
float weight;
}FanoNode;
typedef struct node
{
int start;
int end;
struct node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
//建立队列
void EnterQueue(LinkQueue *q,int s,int e)
{
LinkQueueNode *NewNode;
//生成新节点
NewNode=(LinkQueueNode*)malloc(sizeof( LinkQueueNode ));
if(NewNode!=NULL)
{
NewNode-》start=s;
NewNode-》end=e;
NewNode-》next=NULL;
q-》rear-》next=NewNode;
q-》rear=NewNode;
}
else
{
printf(Error!);
exit(-1);
}
}
//按权分组
void Divide(FanoNode f,int s,int *m,int e)
{
int i;
float sum,sum1;
sum=0;
for(i=s;i《=e;i++)
sum+=f.weight;//
*m=s;
sum1=0;
for(i=s;i《e;i++)
{
sum1+=f.weight;
*m=fabs(sum-2*sum1)》fabs(sum-2*sum1-2*f.weight)?(i+1):*m;
if(*m==i) break;
}
}
void main()
{
int i,j,n,max,m,h;
int sta,end;
float w;
char c,fc;
FanoNode FN;
LinkQueueNode *p;
LinkQueue *Q;
//初始化队Q
Q=(LinkQueue *)malloc(sizeof(LinkQueue));
Q-》front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
Q-》rear=Q-》front;
Q-》front-》next=NULL;
printf( ***FanoCoding***
);
printf(Please input the number of node:);
//输入信息
scanf(%d,&n);
//超过定义M,退出
if(n》=M)
{
printf(》=%d,M);
exit(-1);
}
i=1; //从第二个元素开始录入
while(i《=n)
{
printf(%d weight and node:,i);
scanf(%f %c,&FN.ch);
for(j=1;j《i;j++)
{
if(FN.ch)//查找重复
{
printf(Same node!!!
); break;
}
}
if(i==j)
i++;
}
//排序(降序)
for(i=1;i《=n;i++)
{
max=i+1;
for(j=max;j《=n;j++)
max=FN.weight?j:max;
if(FN.weight)
{
w=FN.weight;
FN.weight;
FN.weight=w;
c=FN.ch;
FN.ch;
FN.ch=c;
}
}
for(i=1;i《=n;i++) //初始化h
h=0;
EnterQueue(Q,1,n); //1和n进队
while(Q-》front-》next!=NULL)
{
p=Q-》front-》next; //出队
Q-》front-》next=p-》next;
if(p==Q-》rear)
Q-》rear=Q-》front;
sta=p-》start;
end=p-》end;
free(p);
Divide(FN,sta,&m,end); /*按权分组*/
for(i=sta;i《=m;i++)
{
fc=’0’;
++h;
}
if(sta!=m)
EnterQueue(Q,sta,m);
else
fc=’0’;
for(i=m+1;i《=end;i++)
{
fc=’1’;
++h;
}
if(m==sta&&(m+1)==end)
//如果分组后首元素的下标与中间元素的相等，
//并且和最后元素的下标相差为1，则编码码字字符串结束
{
fc=’0’;
fc=’0’;
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i《=n;i++) /*打印编码信息*/
{
printf(%c:,FN.ch);
printf(%s
,fc);
}
system(pause);
} #include 《stdio.h》
#include 《stdlib.h》
#include 《string.h》
#define N 100
#define M 2*N-1
typedef char * HuffmanCode;//haffman编码
typedef struct
{
int weight;//权值
int parent;//父节节点
int LChild;//左子节点
int RChild;//右子节点
}HTNode,Huffman;//huffman树
typedef struct Node
{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}WNode,WeightNode;
/***产生叶子结点的字符和权值***/
void CreateWeight(char ch,int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for(i=0;ch!=’0’;i++)
{
tag=1;
for(j=0;j《i;j++)
if(ch)
{
tag=0;
break;
}
if(tag)
{
CW;
CW.weight=1;
for(k=i+1;ch!=’0’;k++)
if(ch)
CW.weight++;//权值累加
}
}
*s=i;//字符串长度
}
/********创建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼树
for(i=1;i《=n;i++)
{
ht.weight;
ht.parent=0;
ht.LChild=0;
ht.RChild=0;
}
for(i=n+1;i《=2*n-1;i++)
{
ht.weight=0;
ht.parent=0;
ht.LChild=0;
ht.RChild=0;
}
for(i=n+1;i《=2*n-1;i++)
{
for(j=1;j《=i-1;j++)
if(!ht.parent)
break;
s1=j; //找到第一个双亲为零的结点
for(;j《=i-1;j++)
if(!ht.parent)
s1=ht.weight?j:s1;
ht.parent=i;
ht.LChild=s1;
for(j=1;j《=i-1;j++)
if(!ht.parent)
break;
s2=j; //找到第二个双亲为零的结点
for(;j《=i-1;j++)
if(!ht.parent)
s2=ht.weight?j:s2;
ht.parent=i;
ht.RChild=s2;
ht.weight;//权值累加
}
}
/***********叶子结点的编码***********/
void CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd=’0’;//末尾置0
for(i=1;i《=n;i++)
{
start=n-1; //cd串每次从末尾开始
c=i;
p=ht.parent;//p在n+1至2n-1
while(p) //沿父亲方向遍历,直到为0
{
start--;//依次向前置值
if(ht.LChild==c)//与左子相同,置0
cd=’0’;
else //否则置1
cd=’1’;
c=p;
p=ht.parent;
}
weight.num=n-start; //二进制码的长度(包含末尾0)
h=(char *)malloc((n-start)*sizeof(char));
strcpy(h);//将二进制字符串拷贝到指针数组h中
}
free(cd);//释放cd内存
system(pause);
}
/*********所有字符的编码*********/
void CrtHuffmanCode(char ch,HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i《m;i++)
{
for(k=1;k《=n;k++) /*从weight相等的下标K*/
if(ch.c)
break;
hc.num)*sizeof(char));
strcpy(hc); //拷贝二进制编码
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf(***StringInformation***
);
while(i《m)
{
p=2*n-1;//从父亲节点向下遍历直到叶子节点
for(j=0;hc!=’0’;j++)
{
if(hc==’0’)
p=ht.LChild;
else
p=ht.RChild;
}
printf(%c,w.c); /*打印原信息*/
i++;
}
}
/*****释放huffman编码内存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i《=n;i++)//释放叶子结点的编码
free(h);
for(i=0;i《m;i++) //释放所有结点的编码
free(hc);
}
void main()
{
int i,n=0; /*n为叶子结点的个数*/
int m=0; /*m为字符串ch的长度*/
char ch存放输入的字符串*/
Huffman ht; /*Huffman二叉数*/
HuffmanCode h,hc; /*h存放叶子结点的编码，hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf( ***HuffmanCoding***
);
printf(please input information :);
gets(ch); /*输入字符串*/
CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息，m为字符串ch的长度*/
printf(***WeightInformation***
Node );
for(i=1;i《=n;i++) /*输出叶子结点的字符与权值*/
printf(%c ,weight.c);
printf(
Weight );
for(i=1;i《=n;i++)
printf(%d ,weight.weight);
CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/
printf(
***HuffamnTreeInformation***
);
printf( i weight parent LChild RChild
);
for(i=1;i《=2*n-1;i++) /*打印Huffman树的信息*/
printf( %d %d %d %d %d
,i,ht.RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/
printf( ***NodeCode***
); /*打印叶子结点的编码*/
for(i=1;i《=n;i++)
{
printf( %c:,weight.c);
printf(%s
,h);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/
printf(***StringCode***
); /*打印字符串的编码*/
for(i=0;i《m;i++)
printf(%s,hc);
system(pause);
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/
FreeHuffmanCode(h,hc,n,m);
system(pause);
} Matlab 中简易实现Huffman编译码：
n=input(’Please input the total number: ’);
hf=zeros(2*n-1,5);
hq=;
for ki=1:n
hf(ki,1)=ki;
hf(ki,2)=input(’Please input the frequency: ’);
hq=;
end
for ki=n+1:2*n-1
hf(ki,1)=ki;
mhq1=min(hq);
m=size(hq);
m=m(:,2);
k=1;
while k《=m%del min1
if hq(:,k)==mhq1
hq=;
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq1|hf(k,5)==1%find min1 location
k=k+1;
end
hf(k,5)=1;
k1=k;
mhq2=min(hq);
k=1;
while k《=m%del min2
if hq(:,k)==mhq2
hq=;
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq2|hf(k,5)==1%find min2 location
k=k+1;
end
hf(k,5)=1;
k2=k;
hf(ki,2)=mhq1+mhq2;
hf(ki,3)=k1;
hf(ki,4)=k2;
hq=;
end
clc
choose=input(’Please choose what you want:
1: Encoding
2: Decoding
3:.Exit
’);
while choose==1|choose==2
if choose==1
a=input(’Please input the letter you want to Encoding: ’);
k=1;
while hf(k,2)~=a
k=k+1;
if k》=n
display(’Error! You did not input this number.’);
break
end
end
if k》=n
break
end
r=;
while hf(k,5)==1
kc=n+1;
while hf(kc,3)~=k&hf(kc,4)~=k
kc=kc+1;
end
if hf(kc,3)==k
r=;
else
r=;
end
k=kc;
end
r
else
a=input(’Please input the metrix you want to Decoding: ’);
sa=size(a);
sa=sa(:,2);
k=2*n-1;
while sa~=0
if a(:,1)==0
k=hf(k,3);
else
k=hf(k,4);
end
a=a(:,2:sa);
sa=sa-1;
if k==0
display(’Error! The metrix you entered is a wrong one.’);
break
end
end
if k==0
break
end
r=hf(k,2);
end
choose=input(’Choose what you want:
1: Encoding
2: Decoding
3:.Exit
’);
clc;
end
if choose~=1&choose~=2
clc;
end
function =huffman(p)
if (length(find(p《0))~=0)
error(’Not a prob,negative component’);
end
if (abs(sum(p)-1)》10e-10)
error(’Not a prob.vector,component do not add to 1’)
end
n=length(p);
q=p;
m=zeros(n-1,n);
for i=1:n-1
=sort(q);
m(i,:)=;
q=;
end
for i=1:n-1
c(i,:)=blanks(n*n);
end
c(n-1,n)=’0’;
c(n-1,2*n)=’1’;
for i=2:n-1
c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)==1))...
-(n-2):n*(find(m(n-i+1,:)==1)));
c(n-i,n)=’0’;
c(n-i,n+1:2*n-1)=c(n-i,1:n-1);
c(n-i,2*n)=’1’;
for j=1:i-1
c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,...
n*(find(m(n-i+1,:)==j+1)-1)+1:n*find(m(n-i+1,:)==j+1));
end
end
for i=1:n
h(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n);
ll(i)=length(find(abs(h(i,:))~=32));
end
l=sum(p.*ll);
h
l
参考资料：赵永强
没用过，但查了一下，matlab 自带huffmancoding 的程序，基本上是你需要
1. 把测试图像的灰度(sig)找出来，
2, 然后统计灰度的分布(p)，
3. 然后生成一个字典(dict)，
4. 然后直接就可以用huffmanenco进行编码，
5. 再用huffmandeco进行恢复。
奇怪的是 huffman coding不是无损压缩么，为什么会有损失？ 等待大牛回答
sig = repmat(,1,50); % Data to encode
symbols = ; % Distinct data symbols appearing in sig
p = ; % Probability of each data symbol
dict = huffmandict(symbols,p); % Create the dictionary.
hcode = huffmanenco(sig,dict); % Encode the data.
dhsig = huffmandeco(hcode,dict); % Decode the code.
相关tag:哈夫曼编码matlab程序
本站部分资源来源于网络，如果侵犯了您的权益，请联系我们删除1354090129@qq.com