Huffman Coding

안녕하세요 Geeks_Company 입니다.

이곳에 설명에 사용 되는 모든 자료는 http://en.wikipedia.org/ 에서 참조를 하였습니다.

오늘 소개 해드릴 자료는 허프만 코딩입니다.

허프만의 전체 이름은 David Albert Huffman 이며 1925년 8월 9일 태어 나서,
1999년 10월 7일 74 세의 나이로 생을 마감 하였습니다.

허프만 코딩은 Lossless data compression 이며, 그 코딩의 핵심은 아래와 같이 효율적인 트리를 만드는데 있습니다.

http://en.wikipedia.org/wiki/File:Huffman_tree_2.svg

트리 생성 순서.


1. 특정 파일안에 구성원소(char)의 빈도수를 계산 합니다.


2. Freequency 계산이 끝난 후 가장 작은 빈도수를 갖는 구성 원소 2개를 선택한후 , 빈도수의 합을 Parent로 하고, 구성원소 2개를 Child로 만듭니다.



3. 2의 과정을 1개의 Parent가 남을때까지 반복 합니다.






위의 생성된 트리를 기준으로 해서 Code 표를 만듭니다.

Char	Freq	Code
space	7	111
a	4	010
e	4	000
f	3	1101
h	2	1010
i	2	1000
m	2	0111
n	2	0010
s	2	1011
t	2	0110
l	1	11001
o	1	00110
p	1	10011
r	1	11000
u	1	00111
x	1	10010

코드표를 만드는 방식은 간단 합니다.

Root(36)의 좌측 노드는 '0'을 우측 노드는 '1' 을 부여합니다.

Ex ) Space의 경우 36 , 20 , 12 , ' ' 이므로 루트->우측(20)->우측(12)->우측(Space) 이므로 111 이 됩니다.


이렇게 해서 나온 코드 Table을 바탕으로 해당 문자를 코드로 변환을 시킵니다.

참구로 위의 트리는 "this is an example of a huffman tree"를 변환한것으므로, 해당 String 코드 Table을 토대로 Bit로 변환을 합니다. 

변환된 Bits를 Char로 변환을 하기 위해서는 8 비트로 나눠야 하며, 나눠진 8 비트를 함수를 통해서 1 Byte로  변환이 됩니다

이렇게 해서 저장을 시킬경우 압축된 형태로 파일이 저장이 되어 파일 용량이 줄어 듭니다.