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