adaptivehuffmanencode.txt

有关自适应HUFFMAN文本压缩方面的代码

定义的结构：
typedef struct {
	int parent,rchild,lchild;
    int letter;
	unsigned long weigth;
}Tree;


typedef struct {
	int Bits[128];
	int start;
}code1;
/*******************************************************************
函数名：InitHuffman
返回值：void
说明：初始化Huffman树结构，并把逸出码NYT赋给根结点
*******************************************************************/
void InitHuffman()
{
	int i;
	for(i=0;i<=256;i++)
	{   
		tree[i].lchild=0;
	    tree[i].parent=0;
		tree[i].rchild=0;
		tree[i].weigth=0;
		tree[i].letter=none;
	}
	tree[256].letter=NYT;
	NYTplace=256;
	root1=256;
}


/**********************************************************************
函数名：FindChar
返回值：int
说明：若该字符在Huffman树结构中出现过，则返回该结点的位置，否则返回-1
***********************************************************************/
int FindChar(char newchar){
	int i;
    int j=-1;
    for(i=0;i<=256;i++)
	{
		if(tree[i].letter==(int)newchar)
			 j=i;
	}
	return j;    
}


/************************************************************************
函数名：HighInBlock
返回值：int 
说明：权值相等，若在huffman树结构中找到最大结点编号，就返回其位置，否则
      返回-1
************************************************************************/
int HighInBlock(unsigned long weigth)
{
	int i;
	int highest=-1;
	for(i=0;i<=256;i++)
	{
		if(tree[i].weigth==weigth)
			highest=i;
		
	}
    return highest;
}


/****************************************************************************
函数名：SwapNodes
返回值：void
说明：若HighInBlock函数返回值不是-1；就把当前结点与最大结点编号的结点进行交换
*****************************************************************************/
void SwapNodes(int first,int second)
{
    int temp;
	int tempchar;
   
	//交换左指针
	temp=tree[second].lchild;
	tree[second].lchild=tree[first].lchild;
	tree[first].lchild=temp;
	//交换右指针
	temp=tree[second].rchild;
	tree[second].rchild=tree[first].rchild;
	tree[first].rchild=temp;
	 //交换返回指针
	tree[tree[first].lchild].parent=first;
	tree[tree[first].rchild].parent=first;
	tree[tree[second].lchild].parent=second;
	tree[tree[second].rchild].parent=second;
	//交换数据
	tempchar=tree[second].letter;
	tree[second].letter=tree[first].letter;
	tree[first].letter=tempchar;
    //交换权值
	temp=tree[second].weigth;
	tree[second].weigth=tree[first].weigth;
	tree[first].weigth=temp;

}


/************************************************************************
函数名：Encode
返回值：void
说明：对该字符进行编码，若该字符在Huffman树中出现过，输出其编码，否则输出
      NYT编码在跟这该原始字符
*************************************************************************/
void Encode(char newchar)
{
    int location;
	location=FindChar(newchar);
    
	cd.start=128;
	
	if(location==-1)
	{
        int current,currentnext,j,root;
		current=NYTplace-1;
		currentnext=NYTplace-2;
		//用新包含的叶子结点和NYT结点代替原NYT结点，并输出编码
        tree[NYTplace].rchild=current;
		tree[NYTplace].lchild=currentnext;
		tree[current].parent=NYTplace;
		tree[currentnext].parent=NYTplace;
        tree[current].letter=newchar;
		tree[currentnext].letter=NYT;
		tree[NYTplace].letter=none;
		CString str1;
		CString str3;
        str1=newchar;
        chLength=chLength+1;
	    j=NYTplace;
        root=tree[j].parent;
		while(root!=0)
		{
            cd.start=cd.start-1;
			if(tree[root].lchild==j)
			    cd.Bits[cd.start]=0;
			else 
				cd.Bits[cd.start]=1;
            
			j=root;
			root=tree[root].parent;
		}
		int k;
		for(k=cd.start;k<=127;k++)
		{
			str3.Format("%d",cd.Bits[k]);
			adapstr=adapstr+str3;
            Length++;
		}
		adapstr=adapstr+str1;
		//将原NYT结点和新叶子结点的权值赋1
		tree[NYTplace].weigth=1;
		tree[current].weigth=1;
	    newplace=NYTplace;  //保存将要交换的结点的位置
		//改变当前NYT结点为原NYT结点
		NYTplace=currentnext;
	
	}
	else
	{   //对该结点编码
        int current,root,j;
		current=location;
		CString str4;
		j=current;
		root=tree[j].parent;
        while(root!=0)
		{
            cd.start=cd.start-1;
			if(tree[root].rchild==j)
			    cd.Bits[cd.start]=1;
			else 
				cd.Bits[cd.start]=0;
            
			j=root;
			root=tree[root].parent;
		}
		for(j=cd.start;j<=127;j++)
		{
			str4.Format("%d",cd.Bits[j]);
			adapstr=adapstr+str4;
            Length++;
		} 
	       
		int maxblock=HighInBlock(tree[current].weigth);
		if(tree[current].parent!=maxblock&&maxblock!=current&&maxblock!=-1)
		{
			SwapNodes(current,maxblock);
		    current=maxblock;
		}
		tree[current].weigth=tree[current].weigth+1;
        newplace=current;  //保存刚加入的结点的位置
	}
    
}



/***********************************************************************
函数名：UpdateTree
返回值：void
说明：若该结点不是根结点，递归是其父结点的权值加一，若该结点不是所属块的
      的最大结点，就与最大结点交换
************************************************************************/
void UpdateTree()
{
      int maxblock,current;
      current=newplace;
	  while(treeroot!=current)
	  {
		  current=tree[current].parent;  //往Huffman树上层走
	      maxblock=HighInBlock(tree[current].weigth);
          if(tree[current].parent!=maxblock&&maxblock!=current&&maxblock!=-1)    //当前结点不是最大块，交换
		  {
			  SwapNodes(current,maxblock);       //交换当前结点与最大块结点
              current=maxblock;     //把最大块结点的位置赋给current
		  }
		  tree[current].weigth=tree[current].weigth+1;  //当前结点权值加1
            
      }
     
}