#include "huffman_g.h"/*A. Moffat和J. Katajainen設(shè)計(jì)的使用最少內(nèi)存空間計(jì)算最小冗余編碼（Huffman編碼）的算法源代碼。在元素權(quán)值已從小到大排序的前提下，此算法通過(guò)對(duì)數(shù)組進(jìn)行3次遍歷，不使用額外數(shù)組空間，即可得到所有元素的Huffman碼長(zhǎng)（bit length）。經(jīng)此函數(shù)計(jì)算碼長(zhǎng)后，利用Canonical Huffman編碼方法，可以得到所有元素的編碼。參數(shù)	A	包含各元素的權(quán)值的數(shù)組，調(diào)用前，應(yīng)將數(shù)組A中的權(quán)值按從小到大排序	n	數(shù)組A中元素的個(gè)數(shù)*/void huffman_g::calculate_minimum_redundancy(unsigned long A[], int n) {	int root; /* 在第1次遍歷中是當(dāng)前子樹(shù)的根結(jié)點(diǎn)，在第3次遍歷中是當(dāng)前深度中的分支結(jié)點(diǎn) */	int leaf; /* 只用于第1次遍歷，是下一個(gè)要考察的葉子結(jié)點(diǎn) */	int next; /* 在第1次遍歷中，是下一個(gè)合并用的結(jié)點(diǎn)（子樹(shù)），該位置將存儲(chǔ)該子樹(shù)					的兩個(gè)分支合并后的權(quán)值總和；					在第2次遍歷中，是簡(jiǎn)單循環(huán)變量；					在第3次遍歷中，是將要填入碼長(zhǎng)值的元素位置 */	int avbl; /* 用于第3次遍歷，是當(dāng)前深度中可用結(jié)點(diǎn)數(shù)量。					最初等于該層結(jié)點(diǎn)總數(shù)，由上一層分支結(jié)點(diǎn)總數(shù)乘2得來(lái)。					然后逐一排除分支結(jié)點(diǎn)，剩下的就是該層葉子結(jié)點(diǎn)總數(shù) */	int used; /* 用于第3次遍歷，是當(dāng)前深度中分支結(jié)點(diǎn)總數(shù) */	int dpth; /* 用于第3次遍歷，當(dāng)前深度，如果當(dāng)前層有葉子結(jié)點(diǎn)，即為該葉子結(jié)點(diǎn)的碼長(zhǎng) */	/* 邊界條件檢查	*/	if (n==0) {	return;	}	if (n==1) {	A[0] = 0; return; }	/* 		第1次遍歷，從左至右。		第1次遍歷的結(jié)果是，A[0]..A[n-3]對(duì)應(yīng)于所有分支結(jié)點(diǎn)（不包含根結(jié)點(diǎn)），其中的數(shù)值為該		分支結(jié)點(diǎn)的雙親結(jié)點(diǎn)索引；A[n-2]對(duì)應(yīng)于根結(jié)點(diǎn)，其中的數(shù)值是所有權(quán)值的總和。所有分支		結(jié)點(diǎn)的排列順序：從左到右是二叉樹(shù)中從下向上的順序（假定樹(shù)根在上），深度相同的分支		結(jié)點(diǎn)排列在一起。		參考：在Huffman樹(shù)中，所有分支結(jié)點(diǎn)都有左、右兩個(gè)子樹(shù)，這樣的二叉樹(shù)中，當(dāng)葉子結(jié)點(diǎn)數(shù)		量為n時(shí)，分支結(jié)點(diǎn)（含根結(jié)點(diǎn)）數(shù)量為n-1	*/	/*		首先將最小的兩個(gè)元素（葉子結(jié)點(diǎn)）合并為子樹(shù)，其權(quán)值之和存入A[0]中。這時(shí)，當(dāng)前子樹(shù)		根為數(shù)組中第0個(gè)元素，因此root=0，下一個(gè)要考察的葉子結(jié)點(diǎn)是第3個(gè)元素，因此leaf=2	*/	A[0] +=	A[1]; root = 0;	leaf = 2;	/* 從1到n-1循環(huán)，生成所有分支結(jié)點(diǎn)，并將它們連成完整的二叉樹(shù)	*/	for	(next=1; next <	n-1; next++) {		/* 在root所指的當(dāng)前子樹(shù)和leaf所指的葉子結(jié)點(diǎn)中選一個(gè)最小的，作為下一個(gè)子樹(shù)的一個(gè)分支	*/		if (leaf>=n	|| A[root]<A[leaf])	{			/* 如果root所指的當(dāng)前子樹(shù)比leaf所指的葉子結(jié)點(diǎn)小				則將root所指的當(dāng)前子樹(shù)作為下一個(gè)子樹(shù)的第一個(gè)分支				其值（當(dāng)前子樹(shù)的權(quán)值總和）存入next所指的下一子樹(shù)的根結(jié)點(diǎn)中				然后令root所指的當(dāng)前子樹(shù)的雙親結(jié)點(diǎn)等于next				同時(shí)root加1，考察下一個(gè)子樹(shù) */			/* 如果已考察完所有葉子結(jié)點(diǎn)，而next還小于n-1，則表明現(xiàn)有的子樹(shù)還沒(méi)有完全連入				1棵完整的Huffman樹(shù)（這相當(dāng)于沒(méi)有深度為n-1-next的葉子結(jié)點(diǎn)），這時(shí)也需要執(zhí)				行同樣的操作，以便將現(xiàn)有子樹(shù)連在一起	*/			A[next]	= A[root]; A[root++] = next;		} else			/* 如果root所指的當(dāng)前子樹(shù)大于等于leaf所指的葉子結(jié)點(diǎn)				則將leaf所指的葉子結(jié)點(diǎn)作為下一個(gè)子樹(shù)的第一個(gè)分支				其值（當(dāng)前子樹(shù)的權(quán)值總和）存入next所指的下一子樹(shù)的根結(jié)點(diǎn)中				leaf加1，繼續(xù)考察下一個(gè)葉子結(jié)點(diǎn) */			A[next]	= A[leaf++];		/* 在root所指的當(dāng)前子樹(shù)和leaf所指的葉子結(jié)點(diǎn)中選一個(gè)最小的，作為下一個(gè)子樹(shù)的另一個(gè)分支 */		if (leaf>=n	|| (root<next && A[root]<A[leaf])) {			A[next]	+= A[root];	A[root++] =	next;		} else			A[next]	+= A[leaf++];	}		/* 		第2次遍歷，從右至左，設(shè)置所有分支結(jié)點(diǎn)的深度。		第2次遍歷的結(jié)果是，A[n-2]..A[0]順序保存了從根結(jié)點(diǎn)到最底層的所有分支結(jié)點(diǎn)的深度信息。	*/	/* 將根結(jié)點(diǎn)的深度設(shè)置為0 */	A[n-2] = 0;	for	(next=n-3; next>=0;	next--)		/* 將每個(gè)分支結(jié)點(diǎn)的深度設(shè)置為其雙親結(jié)點(diǎn)深度加1 */ 		A[next]	= A[A[next]]+1;	/* 		第3次遍歷，從右至左，設(shè)置所有葉子結(jié)點(diǎn)的深度（碼長(zhǎng)） 		第3次遍歷的結(jié)果是，A[0]..A[n-1]順序保存了每個(gè)元素的碼長(zhǎng)（即元素在二叉樹(shù)中的深度）	*/	/* 		從根出發(fā)，因此root為n-2，當(dāng)前深度dpth為0；		used用于統(tǒng)計(jì)當(dāng)前深度中分支結(jié)點(diǎn)數(shù)目，其初始值為0；		avbl為根據(jù)上一層分支結(jié)點(diǎn)算出的當(dāng)前層結(jié)點(diǎn)數(shù)目，因初始時(shí)是根結(jié)點(diǎn)，所有結(jié)點(diǎn)數(shù)目為1；		next指向下一個(gè)要設(shè)置的元素位置，從最后一個(gè)元素開(kāi)始；		說(shuō)明：從右向左看，傳入此函數(shù)的元素權(quán)值最初是從大到小排列的，其深度值或碼長(zhǎng)必然是		從小到大排列的，而第2次遍歷后得到的分支結(jié)點(diǎn)深度是從0逐漸增大的，因此，只要從根開(kāi)		始，知道每一層葉子結(jié)點(diǎn)數(shù)目，在數(shù)組中填相應(yīng)數(shù)目的當(dāng)前深度值就可以了。	*/	avbl = 1; used = dpth =	0; root	= n-2; next	= n-1;	while (avbl>0) {		/* 對(duì)當(dāng)前層的所有分支結(jié)點(diǎn)循環(huán) */		while (root>=0 && A[root]==(unsigned int)dpth) { 			/* 分支結(jié)點(diǎn)計(jì)數(shù)used加1 */			used++;	root--;		}		/* 這時(shí)，avbl和used的差值就是當(dāng)前層的葉子結(jié)點(diǎn)數(shù)目 */		/* 對(duì)當(dāng)前層所有葉子結(jié)點(diǎn)循環(huán) */ 		while (avbl>used) { 			/* 從右至左設(shè)置元素的深度值（碼長(zhǎng)） */			A[next--] =	dpth; avbl--;		}		/* 下一層的結(jié)點(diǎn)總數(shù)等于當(dāng)前層分支結(jié)點(diǎn)乘2；深度值加1；used清0 */		avbl = 2*used; dpth++; used	= 0;	}}void huffman_g::generate_codes(int num, const unsigned long* weights){	if (num <= 1 || weights == NULL)		throw new huffman_exception("參數(shù)非法");	unsigned long* A = new unsigned long[num];		memcpy(A, weights, num * sizeof(unsigned long));	// 只計(jì)算權(quán)值非0的元素（因?yàn)閭魅氲臄?shù)據(jù)已從小到大排序，只簡(jiǎn)單忽略前面的0即可）	int i = 0;	while (A[i] == 0) i++;	calculate_minimum_redundancy(A + i, num - i);	code_lens.clear();	for (int i = 0; i < num; i++)		code_lens.push_back(A[i]);	generate_canonical_codes();		delete[] A;}