Home > Zlib library에서 사용하는 알고리즘 > Huffman Coding Algorithm

Huffman Coding Algorithm

Simple Example

‘ABCABCAACDE’라는 문자가 있다.

데이터	코드
A	01
B	10
C	111
D	101
E	11111
F	11
G	110

위의 표와 같이 데이터에 따른 코드가 할당된 경우 문자열은 ‘01101110110111010111110111111’로 표현된다. 열한개의 문자열이 총 29비트로 표현되는 것이다.

이 예제에서는 임의로 코드를 만들었다. 그러나 허프만 코드를 만들 때는 허프만 트리라는 것을 만들어야 한다. 그렇지 않으면 문제가 발생할 수 있다.

’11110’이라는 코드가 있다면, 그것이 ‘FG’로 해석될지 ‘CB’로 해석될 지 알 수 없다. 하지만 허프만 트리를 만들면 이런 문제가 해결된다. 즉, 어떻게 해석되더라도 한 가지로만 해석이 된다.

Huffman Tree

허프만 트리를 만들기 위해서는 0~255까지의 데이터가 몇 개나 있는지 그 빈도수를 세어야 한다. 그리고 가장 수가 적은 것끼리 묶어서 트리를 구성하기 시작한다.

< 예제 소스 >

void GetDataNumber(FILE* _fp,int* _data)

{

fseek(_fp,0L,SEEK_SET);

int data;

while(!feof(_fp))

{

data=fgetc(_fp);

_data[data]++;

}

}

< 과정 1 > 다음과 같이 빈도수가 나왔다고 가정해보자.

A	B	C	D	E	F
3	1	1	2	3	4

< 과정 2 > 빈도수가 가장 작은 B와 C를 하나의 노드로 묶는다.

A		B+C		D	E	F
3		2		2	3	4
	B		C
	1		1

< 과정 3 > 다시 가장 빈도수가 적은 두 노드를 선택한다. B+C노드와 D를 묶어준다.

A		B+C+D		E	F
3		4		3	4
	B+C		D
	2		2
B		C
1		1

< 과정 4> 이번에는 A와 E가 가장 빈도수가 작으므로 두 개를 묶어준다.

		B+C+D			A+E		F
		4			6		4
	B+C		D	A		E
	2		2	3		3
B		C
1		1

< 과정 5 > 다시 F와 B+C+D 노드를 묶어준다.

			B+C+D+F			A+E
			8			6
		B+C+D		F	A		E
		4		4	3		3
	B+C		D
	2		2
B		C
1		1

< 과정 6 > 마지막으로 남은 두 개의 노드를 묶어 주면 허프만 트리가 완성된다.

					A+B+C+D+E+F
					14
			B+C+D+F				A+E
			8				6
		B+C+D		F		A		E
		4		4		3		3
	B+C		D
	2		2
B		C
1		1

< 결과 > 허프만 트리를 정리하면 다음과 같은 코드 값을 얻을 수 있다.

데이터	코드	길이
A	10	2
B	0000	4
C	0001	4
D	001	3
E	11	2
F	01	2