허프만코드를 만드는 방법

허프만 코드란 주어진 문자열을 트리를 이용해 2진수로 압축하는 알고리즘의 하나입니다.

즉 일반적으로 문자 'A'를 표현하기 위해서는 'A'의 ASCII 값이 65 이므로 2진수로 표현하면  01000001 처럼 8비트를 사용하게 됩니다. 따라서 다음과 같은 데이터를 표현할때 다음과 같은 비트를 사용하게 됩니다.

AAAAAAAAAAB 라는 문자열을 표현하기 위해서는 다음과 같이 88비트를 사용하게 됩니다.

01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000010(B)

하지만 이것을 A는(00) B는(01) 과 같이 정의 하게 되면 다음과 같이 22비트만으로 위의 문자를 표현할 수 있습니다.

00(A)00(A)00(A)00(A)00(A)00(A)00(A)00(A)00(A)01(B) 

이렇게 하면 같은 데이터라고 해도 데이터 양이 1/4 이 줄어 들수 있기 때문에 압축 알고리즘으로 많이 사용하는 알고리즘입니다.

허프만 코드를 만드는 방법은 다음과 같습니다.

 

 

어떤 데이터가 a, b, c, d, e, f의 6개의 문자로 구성되어 있다. 각 문자의 빈도수는 a(7%), b(15%), c(7%), d(7%), e(49%), f(15%)이다. 허프만 코딩에 의하여 각 문자를 비트 스트링으로 표현하여 a=0100,b=000, d=0101, e=1, f=001의 결과로 나타났다고 하자. c의 코드는 무엇인가?

라는 문제를  풀어 봅니다.

 

1. 먼저 빈도수가 제일 낮은 두개이 트리를 합합니다. (a와 d = 14%) 이때는 ad(14%), b(15%), c(7%),  e(49%), f(15%)

2. 다음으로 빈도수가 낮은 숫자를 다시 합한다.( (ad)와 c = 21%) 이때는 adc(21%), b(15%), e(49%), f(15%)

3. 다음으로 빈도수가 낮은 숫자를 다시 합한다.( b와 f = 30%) 이때는 adc(21%), bf(30%), e(49%)

4. 다음으로 빈도수가 낮은 숫자를 다시 합한다.( adc와 bf = 51%) 이때는 adcbf(51%), e(49%)

5. 다음으로 빈도수가 낮은 숫자를 다시 합한다.( adcbf 와 e = 100%) 이때는 adcbfe(100%)

이렇게 합한 후 트리의 구조를 보면 다음과 같다.

여기에 트리의 맨 위에서 부터 왼쪽의 가지에는 1을 오른쪽의 가지에는 0 의 값을 주면 다음과 같은 트리의 값을 가질 수 있다. 

따라서 위의 트리에서 가장 많이 나오는 e 값은 1(1비트) 로 표현 할 수 있고 c의 값은 011(3비트) d의 값은 0101(4비트) a의 값은 0100(4비트) f의 값은 001(3비트) b의 값은 000(3비트) 로 표현 할 수 있다.

위와 같은 경우 e가 49% 절반 가까이 나오므로 압축률은 1/8 에 가깝게 된다. 즉 800M 데이터라면 100M 가 조금 넘는 데이터로 압축을 할 수 있게 된다.