dongyu

常用链接

统计

最新评论

关于huffman编码

    这几天都在做一个huffman编码的试验!这个东西有点烦。但里面还是涉及道了一些很基础的东西!如:
文件头的定义,huffman树的构造以及编码!码表的设计与定义等。但令我感到最烦的还是文件的I/O.看上去不是很复杂的东西!却扼杀了我大量的脑细胞。哎,要是学好了汇编!也就不至于这样了,汇编的对位操作应该是比较方便的,但自己汇编没怎么接触过,更谈不上在自己的代码中内嵌汇编了。暂且不说这些!到现在我都好不敢确信自己的bit位操作部分的正确性!因为这个东西毕竟太难验证了,汗。。。。
废话少说了!还是贴点实际的代码吧。希望大家能给点指点!
#include<iostream>
#include
<afxwin.h>
using namespace std;

typedef unsigned char  
BYTE;//8bits
typedef unsigned short WORD;
//16bits
typedef unsigned 
long  DWORD;//32bits

struct  HuffmanTree
{
    unsigned 
int Weight;
    unsigned 
int Parent;
    unsigned 
int lChild;
    unsigned 
int rChild;
    unsigned char code;    
//编码值0或1
    unsigned char source;  
//信源符号
};
struct HuffmanTable
{
    
BYTE SourceSignal_CodeLength; //高4bits为信源符号,    
    
//即从原始文件头开始以4bits为单位作为一个信源符号;
    
//低4bits指定该信源符号对应的Huffman码字的长度,即比特数
    WORD CodeBits;               
//信源符号的Huffman编码码字,为两个字节。其    
    
//码字从高位开始,若低位不足则补“0”。    
};

struct HUFFMANFILEHEADER
{
     WORD hfType;          
//指定文件类型,必须是0x4846,即字符串"HF" 
     DWORD hfSize;         
//指定文件大小,包括这12个字节  
     WORD FileNameLength;  
//指定被压缩文件名称的字节数 
     
BYTE SourceSignalNum; //指定信源符号的个数,也是HUFFMAN码表的项数。 
     WORD hfOffBits;       
//从文件头到实际数据的偏移字节数,
                           
//即前两个部分(文件头和码表)的长度之和。
     
BYTE ValidDataBitsNum; //(数据部分中)最后一个字节中有效的比特位数
} ;

typedef struct t_table
{
    WORD HCode;
    
BYTE length;
}TNode;
//////////////////////////////////////////////////////////////////////////////
int count[16];             //记录四比特码在文件中出现的次数
int full_count;            //记录整个文件有多少个四比特位
HuffmanTree 
*HT;
HuffmanTable f_table[
16];   //定义输出文件码表
TNode temp_table[
16];       //临时码表,编程方便
HUFFMANFILEHEADER f_head;
///////////////////////////////////////////////////////////////////////////////


void HuffmanCoding();                     
//对信源进行huffman编码

void CountTheSourceSignal(CFile 
*fp);    //计算每种信源的种类和个数,
                                         
//并且统计出信源总数
void SelectSmall(
int cnt, int *s1, int *s2);

void compress(CFile 
*fp);               //对文件压缩

void CountTheSourceSignal(CFile 
*fp)
{
    
int i;
    unsigned char buffer[
2];
    unsigned char ch[
1];
    
LONG off=0;
    
for(i=0;i<16;i++)
        count[i]
=0;
    full_count
=0;
    
int k=fp->GetLength();
    f_head.hfSize
=k+12;               //被压缩文件的大小
    
while(k)
    {
        fp
->Read(ch,1);
        
//buffer[0]=fgetc(fp);
        buffer[
0]=ch[0];
        buffer[
1]=buffer[0]&0x0F;
        buffer[
0]>>=4;
        
for(i=0;i<2;i++)
        {
            count[buffer[i]]
++;//buffer[i]恰好是count[i]的下标
            full_count
++;
        }
        off
++;
        fp
->Seek(off,CFile::begin);
        k
--;
    }
}
////////////////////////////////////////////////////////////////////////////////////
/*********************************    哈夫曼   ************************************/
/********************************** 编码核心代码***********************************/
////////////////////////////////////////////////////////////////////////////////////

void HuffmanCoding()
{
    
int i,j=1,LeafNum=0;/*叶结点的个数*/
    
int total;//总节点数
    
int s1,s2;
    
for (i=0;i<16;i++)
    {   
        
if(count[i]>0
            LeafNum
++;
    }
//    f_head.SourceSignalNum = (unsigned char)(LeafNum);
    total
=2*LeafNum-1;
//    HT=(HuffmanTree*)calloc((total+1),sizeof(HuffmanTree));
    HT
=new HuffmanTree[total+1];
    
/////////////////////节点初始化////////////////////////
    
for(i=1;i<=16;i++)
    {
        
if(count[i-1]>0)                               //判断是否为在文件中出现的原码
        {
            HT[j].Weight
=count[i-1];
            HT[j].Parent
=0;
            HT[j].lChild
=0;
            HT[j].rChild
=0;
            HT[j].source
=(unsigned char)(i-1);          //原码于count的下标相对应
            j
++;
        }
    }
    
//////////////////////////////////////////////////////////
    
///////////   对非叶结点进行赋初值  //////////////////////
    
//////////////////////////////////////////////////////////
    
    
for(i=LeafNum+1;i<=total;i++)         
        {                                         
         HT[i].Weight
=0;                       
             HT[i].Parent
=0;                         
             HT[i].lChild
=0;                        
             HT[i].rChild
=0;                         
    }                                         
    

    
/*///////////////////Create HuffmanTree////////////////*/
    
for(i=LeafNum+1;i<=total;++i)
    {
        SelectSmall(i
-1,&s1,&s2);
        HT[s1].Parent
=i;
        HT[s2].Parent
=i;
        HT[s1].code
='0';
        HT[s2].code='1';
        HT[i].lChild=s1;
        HT[i].rChild
=s2;
        HT[i].Weight
=HT[s1].Weight+HT[s2].Weight;
    }
    
/*///////////////填充临时码表///////////////////*/
    
for(i=0;i<16;i++)                          //初始化临时码表
    {    
        temp_table[i].length
=0;
        temp_table[i].HCode
=0;
    }
    
    
for(i=1;i<=LeafNum;i++)
    {
        
int f=i;
        j
=(int)HT[f].source;
        
while(f!=total)
        {
//get temp_table[i].HCode
            switch(HT[f].code)
            {
            
case '0':
                {
                    temp_table[j].HCode
<<=1;
                    temp_table[j].length
++;
                    break;
                }
            
case '1':
                {
                    temp_table[j].HCode
<<=1;
                    temp_table[j].HCode|
=0x01;
                    temp_table[j].length
++;
                    break;
                }
            }
//end of switch
            f
=HT[f].Parent;
        }
        temp_table[j].HCode
<<=(16-temp_table[j].length);
    }
    
/*///////////////////////填充文件码表////////////////////////*/
    j
=0;
    
for(i=0;i<16;i++)
    {
        
if(temp_table[i].length!=0)
        {
            f_table[j].SourceSignal_CodeLength 
= (unsigned char)(i);
            f_table[j].SourceSignal_CodeLength 
<<= 4;
            f_table[j].SourceSignal_CodeLength |
= temp_table[i].length;
            f_table[j].CodeBits
=temp_table[i].HCode;
            j
++;
        }
    }
}

/*////////(*s1) is smallest,(*s2) is smaller.///////*/
void SelectSmall(
int cnt, int *s1, int *s2)
{
     
int i;
     unsigned 
int temp1=0;
     unsigned 
int temp2=0;
     unsigned 
int temp3;
     
for(i=1;i<=cnt;i++)
     {
         
if(HT[i].Parent==0)          //只对未还未确定双亲节点的点进行选择
         {
             
if(temp1==0)
             {
                 temp1
=HT[i].Weight;
                 (
*s1)=i;
             }
             
else
             {
                 
if(temp2==0)
                 {
                     temp2
=HT[i].Weight;
                     (
*s2)=i;
                     
if(temp2<temp1)
                     {
                         temp3
=temp2;        //把小权值和大权值交换,得到相应的小权值存
                         temp2
=temp1;        //放在temp1中
                         temp1
=temp3;
                         
                         temp3
=(*s2);        //把相应的下标也换了过来,得到s1对应
                         (
*s2)=(*s1);        //小权值的下标
                         (
*s1)=temp3;
                     }
                 }
                 
else
                 {
                     
if(HT[i].Weight<temp1)
                     {
                         temp2
=temp1;
                         temp1
=HT[i].Weight;
                         
                         (
*s2)=(*s1);
                         (
*s1)=i;
                     }
                     
if(HT[i].Weight>temp1&&HT[i].Weight<temp2)      //当HT[i].Weight的权值小于
                     {                                               
//temp2时,将s2设置为i
                         temp2
=HT[i].Weight;
                         (
*s2)=i;
                     }
                 }
             }
         }
     }
}

///////////////////////////////////////////////////////////////////////////////
/////                   Compress File                                     /////
///////////////////////////////////////////////////////////////////////////////
void compress(CFile 
*sfp, CFile *fp,CString str)
{
    
int i,j;
    
BYTE ch=0,buffer[2];
    unsigned char vanl[
3],tch,R_van=0;
    WORD 
*p1;
    
int remain=0,byte_num=0;
    
LONG off=0;
    fp
->Seek((LONG)12,CFile::begin);
    CFile
* fp2=fp;
    CArchive ar(fp2,CArchive::store);
    
for(i=0;i<16;i++)
    {
        ar
<<f_table[i].SourceSignal_CodeLength<<f_table[i].CodeBits;
    }
    
LONG k=sfp->GetLength();
    
while(k)
    {                            
        
//读原始文件
        
//编码写文件
        p1
=(WORD*)(&vanl[0]);
        sfp
->Read(buffer,1);
        buffer[
1]=buffer[0]&0x0F;//buffer[1] lower 4 bits
        buffer[
0]>>=4;//buffer[0] higher 4 bits
        
for(i=0;i<2;i++)
        {
            ch
=buffer[i];
            
*p1 = temp_table[ch].HCode;
            byte_num
=((int)temp_table[ch].length+remain)/8;
            tch
=vanl[1];
            
*p1=*p1<<(8-remain);
            tch
=tch>>remain;
            vanl[
2]=tch|R_van;
            
for(j=0;j<byte_num;j++)
            {
                fp
->Write(&vanl[2-j],1);
                f_head.hfSize
++;
            }
            R_van
=vanl[2-j];
            remain
=(temp_table[ch].length+remain)%8;
            
        }
        off
++;
        sfp
->Seek(off,CFile::begin);
        k
--;
    }
    
if(remain!=0)
    fp
->Write(&R_van,1);
    f_head.hfType
=0x4648;
    f_head.hfSize
++;
    f_head.hfOffBits
=f_head.SourceSignalNum*3+12;
    f_head.ValidDataBitsNum
=remain;
    fp
->SeekToBegin();
    CFile
*    fp1=fp;
    CArchive ar1(fp1,CArchive::store);
    ar1
<<f_head.hfType<<f_head.FileNameLength<<f_head.hfOffBits<<f_head.hfSize
        
<<f_head.SourceSignalNum<<f_head.ValidDataBitsNum;
}
    



///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////
int main()
{
    CString str;
    char
* pFileName = "test.txt";
    char
* CpFileName="compress.hfm";
    CFile f(pFileName,CFile::modeRead); 
    CFile::typeBinary;
    CFile pf(CpFileName, CFile::modeCreate | CFile::modeWrite );
    str
=CString(pFileName);
    f_head.hfType
=0x4846;
    f_head.FileNameLength
=str.GetLength();
    CountTheSourceSignal(
&f);
    HuffmanCoding();
    compress(
&f,&pf,str);
    cout
<<full_count<<endl;
    return 
0;
}


posted on 2008-04-06 20:15 dongyu 阅读(533) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理