C言語／C++/huffman - Sample is best!

開発環境	Microsoft Visual C++ 2010 Express (SP1)
実行環境	Microsoft Windows XP Home Edition (SP3)
プロジェクトの種類	Win32 コンソール アプリケーション
プロジェクト名	huffman
アプリケーションの種類	コンソール アプリケーション
追加のオプション	空のプロジェクト

作成中。

参考

ハフマン符号 - Wikipedia

huffman.cpp

#include <map>
 
// 型定義
typedef unsigned char	UCHAR;
 
typedef struct {
	int	aiChild[2];
} TreeNode;
 
typedef struct {
	int	iCode;
	int	iSize;
} CodeInfo;
 
typedef struct {
	int	iCount;
	int	iIndex;
} DecIndex;
 
typedef struct {
	int	iCode;
	int	iValue;
} DecTable;
 
typedef std::multimap<int,int> mmii;
 
// 関数プロトタイプ宣言
void dfs(int iIndex, int iCode, int iSize);
int Encode(int iCode, int iSize);
int Decode(int iDataLen);
int FetchBit();
 
// グローバル変数
static TreeNode	g_aTreeNode[511];
static CodeInfo	g_aCodeInfo[256];
static DecIndex	g_aDecIndex[16];
static DecTable	g_aDecTable[256];
static UCHAR	g_aucCode[1024];
static int	g_iCodeIndex = 0;
static UCHAR	g_aucDecBuf[1024];
static int	g_iDecIndex;
 
int main()
{
	UCHAR	aucData[] = "government of the people, by the people, for the people";
	int	aiCount[256] = {0};
	mmii	mmQueue;
	mmii::iterator	it;
	char	acStr[32+1];
	int	iCount;
	int	i;
 
	// 各バイト値の発生回数を数える
	int iDataLen = strlen((char*)aucData);
	for (i = 0; i < iDataLen; i++) {
		aiCount[aucData[i]]++;
	}
	for (i = 0; i < 256; i++) {
		if (aiCount[i] == 0) {
			continue;
		}
		printf("'%c'=%d\n", i, aiCount[i]);
	}
 
	// ハフマン木を作成
	for (i = 0; i < 256; i++) {
		if (aiCount[i]) {
			mmQueue.insert(mmii::value_type(aiCount[i], i));
		}
	}
	int iIndex = 256;
	while (1 < mmQueue.size()) {
		int aiKey[2];
		iCount = 0;
		for (i = 0; i < 2; i++) {
			it = mmQueue.begin();
			aiKey[i]			= (*it).first;
			g_aTreeNode[iIndex].aiChild[i]	= (*it).second;
			mmQueue.erase(it);
			iCount += aiKey[i];
		}
		mmQueue.insert(mmii::value_type(iCount, iIndex));
		printf("0x%02X(%d) = 0x%02X(%d) + 0x%02X(%d)\n", iIndex, iCount,
			g_aTreeNode[iIndex].aiChild[0], aiKey[0],
			g_aTreeNode[iIndex].aiChild[1], aiKey[1]);
		iIndex++;
	}
	it = mmQueue.begin();
	int iRoot = (*it).second;
 
	// 深さ優先探索でバイト値→符号情報を作成
	dfs(iRoot, 0, 0);
	for (i = 0; i < 256; i++) {
		int iSize = g_aCodeInfo[i].iSize;
		if (iSize == 0) {
			continue;
		}
		_ltoa_s(0x80000000 | g_aCodeInfo[i].iCode, acStr, _countof(acStr), 2);
		printf("'%c'=%d %s\n", i, iSize, acStr + 32 - iSize);
	}
 
	// 符号化
	for (i = 0; i < iDataLen; i++) {
		Encode(g_aCodeInfo[aucData[i]].iCode, g_aCodeInfo[aucData[i]].iSize);
	}
	Encode(0, 0);
	for (i = 0; i < g_iCodeIndex; i++) {
		_ltoa_s(0x100 | g_aucCode[i], acStr, _countof(acStr), 2);
		printf("%s%c", acStr + 1, "   -   \n"[i % 8]);
	}
	if (i % 8) {
		printf("\n");
	}
 
	// 復号テーブル作成
	int iDecIndex = 0;
	for (iIndex = 0; iIndex < 16; iIndex++) {
		g_aDecIndex[iIndex].iIndex = iDecIndex;
		iCount = 0;
		for (i = 0; i < 256; i++) {
			if (g_aCodeInfo[i].iSize != iIndex + 1) {
				continue;
			}
			g_aDecTable[iDecIndex].iValue = i;
			g_aDecTable[iDecIndex].iCode = g_aCodeInfo[i].iCode;
			iDecIndex++;
			iCount++;
		}
		g_aDecIndex[iIndex].iCount = iCount;
	}
 
	// 復号
	Decode(iDataLen);
 
	g_aucDecBuf[g_iDecIndex] = 0x00;
	printf("%s\n", g_aucDecBuf);
	return 0;
}
 
// 深さ優先探索でバイト値→符号情報を作成
void dfs(int iIndex, int iCode, int iSize)
{
	if (iIndex < 256) {
		g_aCodeInfo[iIndex].iCode = iCode;
		g_aCodeInfo[iIndex].iSize = iSize;
	} else {
		dfs(g_aTreeNode[iIndex].aiChild[0], iCode << 1, iSize + 1);
		dfs(g_aTreeNode[iIndex].aiChild[1], iCode << 1 | 1, iSize + 1);
	}
}
 
// 符号化
int Encode(int iCode, int iSize)
{
	static int	s_iCode;
	static int	s_iSize = 0;
 
	if (iSize == 0) {
		if (s_iSize) {
			s_iCode = s_iCode << (8 - s_iSize) | 0xFF >> s_iSize;
			g_aucCode[g_iCodeIndex++] = s_iCode;
		}
		return 0;
	}
	s_iCode = s_iCode << iSize | iCode;
	s_iSize += iSize;
	while (8 <= s_iSize) {
		s_iSize -= 8;
		g_aucCode[g_iCodeIndex++] = s_iCode >> s_iSize;
	}
	return 0;
}
 
// 復号
int Decode(int iDataLen)
{
	int	iCode;
	int	iSize;
	int	iBit;
	int	iIndex;
	int	iValue;
	int	i;
 
	for (g_iDecIndex = 0; g_iDecIndex < iDataLen; g_iDecIndex++) {
		iCode	= 0;
		iSize	= 0;
		for (iValue = -1; iValue == -1; ) {
			iBit = FetchBit();
			iCode = iCode << 1 | iBit;
			iSize++;
			iIndex = g_aDecIndex[iSize - 1].iIndex;
			for (i = 0; i < g_aDecIndex[iSize - 1].iCount; i++) {
				if (g_aDecTable[iIndex + i].iCode == iCode) {
					iValue = g_aDecTable[iIndex + i].iValue;
					break;
				}
			}
		}
		g_aucDecBuf[g_iDecIndex] = iValue;
	}
	return 0;
}
 
int FetchBit()
{
	static int	iCodeIndex = 0;
	static int	iCodeBit = 7;
	int		i;
 
	i = g_aucCode[iCodeIndex] >> iCodeBit & 0x01;
	if (--iCodeBit < 0) {
		iCodeIndex++;
		iCodeBit = 7;
	}
	return i;
}
 

出力

' '=9
','=2
'b'=1
'e'=11
'f'=2
'g'=1
'h'=3
'l'=3
'm'=1
'n'=2
'o'=6
'p'=6
'r'=2
't'=4
'v'=1
'y'=1
0x100(2) = 0x62(1) + 0x67(1)
0x101(2) = 0x6D(1) + 0x76(1)
0x102(3) = 0x79(1) + 0x2C(2)
0x103(4) = 0x66(2) + 0x6E(2)
0x104(4) = 0x72(2) + 0x100(2)
0x105(5) = 0x101(2) + 0x68(3)
0x106(6) = 0x6C(3) + 0x102(3)
0x107(8) = 0x74(4) + 0x103(4)
0x108(9) = 0x104(4) + 0x105(5)
0x109(12) = 0x6F(6) + 0x70(6)
0x10A(14) = 0x106(6) + 0x107(8)
0x10B(18) = 0x20(9) + 0x108(9)
0x10C(23) = 0x65(11) + 0x109(12)
0x10D(32) = 0x10A(14) + 0x10B(18)
0x10E(55) = 0x10C(23) + 0x10D(32)
' '=3 110
','=5 10011
'b'=6 111010
'e'=2 00
'f'=5 10110
'g'=6 111011
'h'=5 11111
'l'=4 1000
'm'=6 111100
'n'=5 10111
'o'=3 010
'p'=3 011
'r'=5 11100
't'=4 1010
'v'=6 111101
'y'=5 10010
11101101 01111010 01110010 11111110-00010111 10101100 10101101 10101011
11100110 01100010 01110000 01001111-01110101 00101101 01011111 00110011
00010011 10000010 01111010 11001011-10011010 10111110 01100110 00100111
00000111 
government of the people, by the people, for the people