HuffmanTreeとHuffmanCode

HuffmanTreeとHuffmanCoding
1.HuffmanTree
HuffmanTreeは最適二叉木とも呼ばれ,重み付き経路長が最適な木である.
n個の葉の結点を有する二叉木を構築する、各葉の結点帯権がwiであるとすると、その中で帯権経路長WPLが最小である二叉木を最適二叉木(HuffmanTree)と呼ぶ.
1.1 HuffmanTreeの構築方法
ヘフマンアルゴリズム:

は、与えられたn個の重み{w 1,w 2,...,wn}に基づいて、n個の二叉木の集合F={T 1,T 2,...,Tn}として構成され、そのうち、各二叉木Tiのうち重みwiのルートノードは1個のみであり、その左右のノードはいずれも空である.

Fで2本のルートノードの重み値が最も小さいツリーを左右のサブツリーとして1本の新しい二叉木を構築し、新しい二叉木ルートノードの重み値を左右のサブツリーノードの重み値の和とする.

この2つのツリーをFから削除し、同時に新しく得られたツリーをFセットに追加する.

は、集合Fに1つのツリーのみが含まれるまで2を循環する.この木はハフマンの木

です
1.2 HuffmanTreeの実装
n個のリーフノード、1個のHuffmanTreeノード数は2 n−1個であり、すべてのノードを順次記憶するのに必要な記憶空間は(2 n−1)*sizeof(HTNode)、前のn個の記憶空間はn個のリーフノード、後のn−1個の記憶空間は非リーフノードを記憶する.

//    HuffmanTree
typedef struct{
	int weight; //    
	int parent,lchird,rchird; //        
}HTNode,* HuffmanTree;

Status Select(HuffmanTree HT,int endindex,int *s1,int *s2);
/**
 *
 *  *w = weight[] ,      
 *   n ，      , n     
 */
Status createHuffmanTree(HuffmanTree &HT,int *w,int n){
	if(n < 1) return False;

	int m = 2*n - 1;  // n                   
	HT = (HTNode *)malloc((m + 1)*sizeof(HTNode));//    0       
	*HT = {0,0,0,0};
	int i = 1; HuffmanTree p = HT+1;
	for(; i < n+1; i++,p++,w++) *p = {*w, 0, 0, 0}; //                
	for(;i < m+1;i++,p++) *p = {0, 0, 0, 0};

	for(i = n + 1; i < m+1; i++){
		int s1,s2;
		// HT[0]   ， HT[1,...,i-1]   parent  0   weight      s1,s2      
		Select(HT,i-1,&s1,&s2); // i n+1    1 i-1         n     
		HT[i].lchird = s1;HT[i].rchird = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
		HT[s1].parent = i;HT[s2].parent = i;
	}
	for(int i = 1; i < m+1; i++){
		printf("HT[%d] { weight = %d,parent = %d,lchird= %d,rchird= %d }
",i,HT[i].weight,HT[i].parent,HT[i].lchird,HT[i].rchird);
	}
	return OK;
}
Status Select(HuffmanTree HT,int endindex,int *s1,int *s2){
	int indexnum = 0;
	for(int i = 1; i <=endindex;i++){
		if(HT[i].parent == 0) indexnum++;
	}
	int index[indexnum];
	for(int i = 1,j=0; i <=endindex;i++){
		if(HT[i].parent == 0) index[j++] = i;
	}
	int minindex = index[0];
	for(int i = 1; i < indexnum;i++){
		if(HT[index[i]].weight < HT[minindex].weight) minindex = index[i];
	}
	*s1 = minindex;

	minindex = index[0];
	if(minindex == *s1) minindex=index[1];
	for(int i = minindex; i < indexnum;i++){
		if(i != *s1){
			if(HT[index[i]].weight <= HT[minindex].weight) minindex = index[i];
		}
	}
	*s2 = minindex;

2.HuffmanCoding
2.1HuffmanCoding
ヘフマン符号化は、1枚の符号化テーブルを用いてソース文字を符号化し、符号化テーブルでは、確率の高い短い符号化を用い、確率の低い長符号化を用いる
HuffmanCodingデータ無損圧縮用
例:圧縮文字列「ABACCDA」合計4文字
バイナリ符号化、2ビットバイナリ即時符号化、A:00 B:01 C:10 D:11、符号化結果“000110101101”、復号は2ビット
圧縮された文字列をより短い符号化で表すには、短い符号化を多く繰り返し、少ない符号化を繰り返す.
符号化A:0 B:00 C:1 D:01、符号化結果「000011010」がありますが、復号する場合があります
この場合、どの文字符号化も別の文字符号化の中接頭辞ではなく、この符号化を接頭辞符号化と呼ぶ.
このとき我々は構造HuffmanTreeを用いて,左分岐が0,右分岐が1であることを約束した.
プレフィックス符号化、A:0 B:101 C:10 D:111
2.2 HuffmanCoding実装

typedef char ** HuffmanCode; //         ，  Huffman   
/**
 *  HT,      HuffmanTree,
 *  HC,      
 *  n,        ，      
 */
Status HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n){
	//HT       1  
	//                  
	HC = (HuffmanCode)malloc((n+1)*sizeof(char *)); //  n+1, 1             
	char *cd = (char *)malloc(n*sizeof(char)); //             ,n-1          ，          
	cd[n-1] = '\0';
	for(int i = 1; i < n+1; i++){
		int start = n-1;
		for(int c = i,f = HT[i].parent; f != 0; f = HT[f].parent ){
			if(HT[f].lchird == c) cd[--start] = '0';
			else cd[--start] = '1';
		}
		HC[i] = (char*)malloc((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);
	}
	free(cd);
	return OK;
}

3.Test

int main() {
	HuffmanTree ht;
	int weight[6] = {2,3,4,5,6,7};
	createHuffmanTree(ht,weight,6);
	HuffmanCode hc;
	HuffmanCoding(ht,hc,6);
	for(int i = 1; i < 7; i++){
		printf("hc[%d]:%s 
",i,hc[i]);
	}
	return 0;
}

result:

HT[0] { weight = 0,parent = 0,lchird= 0,rchird= 0 }
HT[1] { weight = 2,parent = 7,lchird= 0,rchird= 0 }
HT[2] { weight = 3,parent = 7,lchird= 0,rchird= 0 }
HT[3] { weight = 4,parent = 8,lchird= 0,rchird= 0 }
HT[4] { weight = 5,parent = 9,lchird= 0,rchird= 0 }
HT[5] { weight = 6,parent = 9,lchird= 0,rchird= 0 }
HT[6] { weight = 7,parent = 10,lchird= 0,rchird= 0 }
HT[7] { weight = 5,parent = 8,lchird= 1,rchird= 2 }
HT[8] { weight = 9,parent = 10,lchird= 3,rchird= 7 }
HT[9] { weight = 11,parent = 11,lchird= 4,rchird= 5 }
HT[10] { weight = 16,parent = 11,lchird= 6,rchird= 8 }
HT[11] { weight = 27,parent = 0,lchird= 9,rchird= 10 }
hc[1]:1110 
hc[2]:1111 
hc[3]:110 
hc[4]:10 
hc[5]:11 
hc[6]:10 

詳細ソース:https://github.com/linrenyao/datastructure