有关哈夫曼编码压缩与解压缩的问题.
你好,由于内容比较多,先概述一下先。如图所示,为我写的一个压缩软件,原理是利用哈弗曼算法实现的。我将资料整理好稍后就发到你邮箱,但在这里简要说明一下代码。
请看我的空间
http://hi.baidu.com/%D2%B6%BF%C6%C1%BC/blog
中的文章共5篇(太长了)
http://hi.baidu.com/%D2%B6%BF%C6%C1%BC/blog/item/93c35517bb528146f2de32fd.html
1.HuffmanTextEncoder类完成压缩功能,可直接运行,压缩测试用文本文件。
2.HuffmanTextDecoder类完成解压缩功能,可直接运行,解压缩 压缩后的文本文件。
3.BitReader,工具类,实现对BufferedInputStream的按位读取。
4.BitWriter,工具类,实现按位写入的功能。该类来自网络。
5.MinHeap ,模板工具类,实现了一个最小堆。生成Huffman树时使用。
建立一棵赫夫曼树,设每个父节点的左子节点为1,右子节点为0,然后由根节点到所要编码的字符的叶节点的路径确定字符的编码。比如要编码a,假设a在第三层,则由根节点到a的路径为:根节点——右子节点(0)——左子节点(1)。那么a的编码就为01。就这样把所有字符进行编码,建立一个赫夫曼编码表。利用这个编码表把字符串编码就是压缩了,解压缩就是把参照赫夫曼编码表把编码转为字符串。
压缩代码非常简单,首先用ASCII值初始化511个哈夫曼节点:CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
然后,计算在输入缓冲区数据中,每个ASCII码出现的频率:
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然后,根据频率进行排序:
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
现在,构造哈夫曼树,获取每个ASCII码对应的位序列:
int nNodeCount = GetHuffmanTree(nodes);
构造哈夫曼树非常简单,将所有的节点放到一个队列中,用一个节点替换两个频率最低的节点,新节点的频率就是这两个节点的频率之和。这样,新节点就是两个被替换节点的父节点了。如此循环,直到队列中只剩一个节点(树根)。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;
这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个,但我分配了511个(CHuffmanNode nodes[511]),前255个记录ASCII码,而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接着,压缩的最后一步是将每个ASCII编码写入输出缓冲区中:
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
(nDesIndex&7): &7 得到最高位.
注意:在压缩缓冲区中,我们必须保存哈夫曼树的节点以及位序列,这样我们才能在解压缩时重新构造哈夫曼树(只需保存ASCII值和对应的位序列)。
解压缩
解压缩比构造哈夫曼树要简单的多,将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住,这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此,为了用ASCII值替换编码,我们必须用位流搜索哈夫曼树,直到发现一个叶节点,然后将它的ASCII值添加到输出缓冲区中:
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}
过程
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<math.h>
#define M 10
typedef struct Fano_Node
{
char ch;
float weight;
}FanoNode[M];
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!");
}
//***按权分组***//
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;
}
}
main()
{
int i,j,n,max,m,h[M];
int sta,mid,end;
float w;
char c,fc[M][M];
FanoNode FN;
LinkQueueNode *p;
LinkQueue *Q;
//***初始化队Q***//
Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
Q->rear=Q->front;
Q->front->next=NULL;
printf("\t***FanoCoding***\n");
printf("Please input the number of node:"); /*输入信息*/
scanf("%d",&n);
i=1;
while(i<=n)
{
printf("%d weight and node:",i);
scanf("%f %c",&FN.weight,&FN.ch);
for(j=1;j<i;j++)
{
if(FN.ch==FN[j].ch)
{
printf("Same node!!!\n");
break;
}
}
if(i==j)
i++;
}
for(i=1;i<=n;i++) /*排序*/
{
max=i+1;
for(j=max;j<=n;j++)
max=FN[max].weight<FN[j].weight?j:max;
if(FN.weight<FN[max].weight)
{
w=FN.weight;
FN.weight=FN[max].weight;
FN[max].weight=w;
c=FN.ch;
FN.ch=FN[max].ch;
FN[max].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[h]='0';
h++;
}
if(sta!=m)
EnterQueue(Q,sta,m);
else
fc[sta][h[sta]]='\0';
for(i=m+1;i<=end;i++)
{
fc[h]='1';
h++;
}
if(m==sta&&(m+1)==end) //如果分组后首元素的下标与中间元素的相等,
{ //并且和最后元素的下标相差为1,则编码码字字符串结束
fc[m][h[m]]='\0';
fc[end][h[end]]='\0';
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i<=n;i++) /*打印编码信息*/
{
printf("%c:",FN.ch);
printf("%s\n",fc);
}
system("pause");
}
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];
typedef struct
{
char weight;
int parent;
int LChild;
int RChild;
}HTNode,Huffman[M+1];
typedef struct Node
{
int weight; /*叶子结点的权值*/
char c; /*叶子结点*/
int num; /*叶子结点的二进制码的长度*/
}WNode,WeightNode[N];
/***产生叶子结点的字符和权值***/
void CreateWeight(char ch[],int *s,WeightNode *CW,int *p)
{
int i,j,k;
int tag;
*p=0;
for(i=0;ch!='\0';i++)
{
tag=1;
for(j=0;j<i;j++)
if(ch[j]==ch)
{
tag=0;
break;
}
if(tag)
{
(*CW)[++*p].c=ch;
(*CW)[*p].weight=1;
for(k=i+1;ch[k]!='\0';k++)
if(ch==ch[k])
(*CW)[*p].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 =w.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).parent=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!(*ht)[j].parent)
break;
s1=j; /*找到第一个双亲不为零的结点*/
for(;j<=i-1;j++)
if(!(*ht)[j].parent)
s1=(*ht)[s1].weight>(*ht)[j].weight?j:s1;
(*ht)[s1].parent=i;
(*ht).LChild=s1;
for(j=1;j<=i-1;j++)
if(!(*ht)[j].parent)
break;
s2=j; /*找到第一个双亲不为零的结点*/
for(;j<=i-1;j++)
if(!(*ht)[j].parent)
s2=(*ht)[s2].weight>(*ht)[j].weight?j:s2;
(*ht)[s2].parent=i;
(*ht).RChild=s2;
(*ht).weight=(*ht)[s1].weight+(*ht)[s2].weight;
}
}
/***********叶子结点的编码***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode *h,WeightNode *weight,int m,int n)
{
int i,j,k,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
c=i;
p=ht.parent;
while(p)
{
start--;
if(ht[p].LChild==c)
cd[start]='0';
else
cd[start]='1';
c=p;
p=ht[p].parent;
}
(*weight).num=n-start;
(*h)=(char *)malloc((n-start)*sizeof(char));
p=-1;
strcpy((*h),&cd[start]);
}
system("pause");
}
/*********所有字符的编码*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode *hc,WeightNode weight,int n,int m)
{
int i,j,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*从(*weight)[k].c中查找与ch相等的下标K*/
if(ch==weight[k].c)
break;
(*hc)=(char *)malloc((weight[k].num+1)*sizeof(char));
for(j=0;j<=weight[k].num;j++)
(*hc)[j]=h[k][j];
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf("***StringInformation***\n");
while(i<m)
{
p=2*n-1;
for(j=0;hc[j]!='\0';j++)
{
if(hc[j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf("%c",w[p].c); /*打印原信息*/
i++;
}
}
main()
{
int i,n,m,s1,s2,j; /*n为叶子结点的个数*/
char ch[N],w[N]; /*ch[N]存放输入的字符串*/
Huffman ht; /*二叉数 */
HuffmanCode h,hc; /* h存放叶子结点的编码,hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf("\t***HuffmanCoding***\n");
printf("please input information :");
gets(ch); /*输入字符串*/
CreateWeight(ch,&m,&weight,&n); /*产生叶子结点信息,m为字符串ch[]的长度*/
printf("***WeightInformation***\n Node "); /*输出叶子结点的字符与权值*/
for(i=1;i<=n;i++)
printf("%c ",weight.c);
printf("\nWeight ");
for(i=1;i<=n;i++)
printf("%d ",weight.weight);
CreateHuffmanTree(&ht,weight,n); /*产生Huffman树*/
printf("\n***HuffamnTreeInformation***\n");
for(i=1;i<=2*n-1;i++) /*打印Huffman树的信息*/
printf("\t%d %d %d %d\n",i,ht.weight,ht.parent,ht.LChild,ht.RChild);
CrtHuffmanNodeCode(ht,ch,&h,&weight,m,n); /*叶子结点的编码*/
printf(" ***NodeCode***\n"); /*打印叶子结点的编码*/
for(i=1;i<=n;i++)
{
printf("\t%c:",weight.c);
printf("%s\n",h);
}
CrtHuffmanCode(ch,h,&hc,weight,n,m); /*所有字符的编码*/
printf("***StringCode***\n"); /*打印字符串的编码*/
for(i=0;i<m;i++)
printf("%s",hc);
system("pause");
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/
system("pause");
}
如何用二进制打开一个txt的文档....file.open的参数设置一下就OK了.
本人不懂 但是有点资料 希望对你有帮助
二进制文件复制的类的代码
Byte数组作为缓冲区,打开两个文件,一个读,一个写
Option Explicit
Public Event FileProgress(ByVal sngPercentage As Single)
Private mbCancel As Boolean
Public Sub DoCopy(ByVal strSourFile As String, ByVal strDestFile As String, Optional ByVal lngBufferSize As Long = 32768)
On Error GoTo errHande
ReDim abytBuffer(lngBufferSize - 1) As Byte
Dim lngFileSize As Long, lngRemain As Long '文件长度字节数,剩余的字节数
Open strSourFile For Binary Access Read As #1
Open strDestFile For Binary Access Write As #2
lngFileSize = LOF(1)
lngRemain = lngFileSize
While lngRemain > 0
If lngRemain < lngBufferSize Then
lngBufferSize = lngRemain
ReDim abytBuffer(lngBufferSize - 1)
End If
Get #1, , abytBuffer
Put #2, , abytBuffer
lngRemain = lngRemain - lngBufferSize
RaiseEvent FileProgress((lngFileSize - lngRemain) / lngFileSize)
DoEvents
If mbCancel Then
Err.Raise vbObjectError + 513, "CopyFile", "用户取消操作"
End If
Wend
Close #1
Close #2
Erase abytBuffer
RaiseEvent FileProgress(1)
Exit Sub
errHande:
MsgBox Err.Description & ",文件复制没有完成"
Close #1
Close #2
Erase abytBuffer
If Len(Dir(strDestFile)) > 0 And Len(strDestFile) > 0 Then Kill strDestFile
End Sub
Public Sub cancel()
mbCancel = True
End Sub
哈夫曼编码的算法是怎样?
Faller等人提出了动态哈夫曼编码方法,它对数据编码的依据是动态变化的哈夫曼树,也就是说,对第t+1个字符编码是根据原始数据中前t个字符得到的哈夫曼树来进行的。压缩和解压子程序具有相同的初始化树,每处理完一个字符,压缩和解压方使用相同的算法修改哈夫曼树,因而该方法不需要为解压而保存树的有...
深入探索数据压缩:哈夫曼编码与其同类技术的原理与C++ 实现
数据压缩技术有很多种,其中哈夫曼编码是一种广泛应用的方法。它通过分析数据的统计特性,为每个数据单元分配一个唯一的、变长的编码。这种方法的高效性和普适性使其成为了数据压缩的重要工具。但哈夫曼编码并不孤单,还有其他的编码技术,如阿尔法赫曼编码、LZW编码和游程编码等。每种技术都有其独特的应...
哈夫曼编码是怎样进行压缩的?
哈夫曼编码进行压缩的压缩率是根据平均码长来计算的,压缩率比较低。例如:用三位二进行数进行的等长编dao码平均长度为3,而根据哈夫曼树编码的平均码长为:4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61\/3=0.87=87 其平均码长是等长码的87%,所以...
有关哈夫曼编码压缩与解压缩的问题.
解压缩 解压缩比构造哈夫曼树要简单的多,将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住,这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此,为了用ASCII值替换编码,我们必须用位流搜索哈夫曼树,直到发现一个叶节点,然后将它的ASCII值添加到输出缓冲区中: int nDesIndex = 0; DWOR...
算法解析:哈夫曼(huffman)压缩算法
哈夫曼压缩算法,一种利用字符出现频率构建最优编码的高效数据压缩方法。当计算机存储字符数据时,原始二进制形式占据大量空间,如"ABRACADABRA!"需96 bits。通过哈夫曼编码,我们可以设计一个特殊表格,将字符映射到更短的二进制序列。关键在于构建一棵特殊的树,树的节点代表字符,左边为0,右边为1。节点的...
哈夫曼编码
哈夫曼编码是一种用于无损数据压缩的熵编码算法。哈夫曼编码利用可变长度编码表对源数据进行压缩。它会根据数据中符号出现的频率进行编码,使得出现频率较高的符号以较短的编码表示,而频率较低的符号则使用较长的编码。这种编码方式可以显著降低编码后数据的总长度,从而实现数据压缩。具体来说,哈夫曼编码...
哈夫曼编码运用到了哪种数据结构?
哈夫曼编码是一种用于无损数据压缩的算法。在哈夫曼编码中,树形数据结构,特别是哈夫曼树,起到了核心作用。哈夫曼树是一种特殊的二叉树,其构建过程是根据数据源中字符的出现频率来决定的。具体来说,哈夫曼编码利用哈夫曼树来完成以下任务:1. 构建哈夫曼树:根据数据中各字符的出现频率,选择频率最...
哈夫曼树的加权平均长度
哈夫曼树的加权平均长度描述了使用哈夫曼编码对数据源进行编码时,平均每个信息单元(如字符)所需的编码位数。这个指标反映了压缩算法的效率,即压缩后数据的平均长度与原始数据长度之间的关系。哈夫曼树的加权平均长度是一个介于0和1之间的数值,数值越接近0表示压缩效果越好,即数据被压缩得越紧凑。
[数据结构]哈夫曼树&K叉哈夫曼树&范式哈夫曼编码&编码位数的限制...
以A~E字母为例,原本ASCII编码需要48比特,但通过哈夫曼编码,我们能将其压缩至仅需15比特,这得益于树中频繁出现的符号获得了更短的编码,如A的编码为2001,B为11,C为01,D为000,E为10。哈夫曼编码的构建过程巧妙地利用了堆结构,如std::priority_queue,通过合并权值最小的节点,形成编码规则。
压缩算法原理
哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示,而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而,它并不处理符号的顺序和重复或序号的序列。2.1 原理 我...
弭胁风湿: 建立一棵赫夫曼树,设每个父节点的左子节点为1,右子节点为0,然后由根节点到所要编码的字符的叶节点的路径确定字符的编码.比如要编码a,假设a在第三层,则由根节点到a的路径为:根节点——右子节点(0)——左子节点(1).那么a的编码就为01.就这样把所有字符进行编码,建立一个赫夫曼编码表.利用这个编码表把字符串编码就是压缩了,解压缩就是把参照赫夫曼编码表把编码转为字符串.
忻城县19238352610: 如何用哈夫曼编码实现英文文本的压缩和解压缩? - ?
弭胁风湿: 哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件.哈夫曼压缩属于可变代码长度算法一族.意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代.因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列.有人用C函数写了这个编码,见下面链接http://baike.baidu.com/view/189694.htm
忻城县19238352610: 用哈夫曼树算法设计对文件文件的压缩和解压缩的实验程序解析 - ?
弭胁风湿: 楼主可以去看看最优二叉树的编码问题. 1、哈夫曼编码 在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符.例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R...
忻城县19238352610: 利用哈夫曼编码进行压缩压缩率一般达到多少? - ?
弭胁风湿: 哈夫曼编码进行压缩的压缩率是根据平均码长来计算的,压缩率比较低. 例如:用三位二进行数进行的等长编码平均长度为3,而根据哈夫曼树编码的平均码长为: 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87...
忻城县19238352610: 利用哈夫曼编码进行压缩压缩率一般达到多少? - ?
弭胁风湿: 哈夫曼编码压缩率很低的举个例子:用三位二进行数进行的等长编码平均长度为3,而根据哈夫曼树编码的平均码长为: 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87% 其平均码长是等长码的87%. 所以平均压缩率为13%.所以应该是你算法有问题……
忻城县19238352610: y采用哈夫曼编码思想实现文件的压缩和恢复功能,并提供压缩前后的占用空间之比! - ?
弭胁风湿: 一.模型表示: 计算机使用数字代码来存储字符,ASC II码是最常用的编码.一个ASC II码值占一个字节(8个二进制位),其最高位(b7)用作奇偶校验位,共128个.要对一个文本文件进行压缩,就是要对文件内的字符重新编码,使出现次数...
忻城县19238352610: 哈夫曼编码压缩概念的基本思想?如何回答(精简的说) - ?
弭胁风湿: A,e的出现概率很高,而z的出现概率则最低,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作Huffman编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)...
忻城县19238352610: 哈夫曼编码的压缩实现 - ?
弭胁风湿: 压缩代码非常简单,首先用ASCII值初始化511个哈夫曼节点: CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; 其次,计算在输入缓冲区数据中,每个ASCII码出现的频率: for(nCount = ...
忻城县19238352610: 什么是哈夫曼编码? - ?
弭胁风湿: 哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种. Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作...
忻城县19238352610: 用哈夫曼树算法设计对文件文件的压缩和解压缩的程序怎么写? - ?
弭胁风湿: #include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h> struct head { unsigned char b; /*the charactor*/ long count; /*the frequency*/ long parent,lch,rch; /*make a tree*/ char bits[256]; /*the haffuman code*/ } header[512],tmp; void ...