这几天都在做一个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;
}