허프만 코드

이진트리로 메시지의 내용을 압축한다.

각 글자의 비트수를 최소로 해서 문자를 압축하는 것이다.

 

예로 e, t, n, i, s 5개의 문자로 이루어진 문자열이 있다고 가정해보자.

그럼 각 글자의 빈도수와 표현에 필요한 비트수를 구해본다.

( 한 글자를 표현할때 필요한 비트는 3비트라고 가정)

글자	빈도수	비트수
e	15	3x15=45
t	12	3x12=36
n	8	3x12=24
i	6	3x6=18
s	4	3x4=12

즉 e t s i s 로 각각 해당 문자의 빈도수만큼 표현한 문자열은 총 비트수가 135이다. 즉, 135 비트를 차지함

 

하지만 아래와 같이 허프만 코드를 이용해 압축을 한다면

글자	빈도수	비트코드	비트수
e	15	00	30
t	12	01	24
n	8	11	16
i	6	100	18
s	4	101	12
합계			100

100비트로 표현이 가능하다. 압축이 된 것이다. 그럼 각 글자에 해당하는 비트 코드를 어떻게 생성할까?

아래와 같은 원리로 비트코드를 구한다.

 

각 빈도수를 이용해 트리를 만드는것이다.

(1)

4의 빈도수는 s, 6의 빈도수는 i, 8의 빈도수는 n, ... 이다.

 

이제 반복적으로 최소 힙에 있는 가장 작은 노드 두 개를(뽑아) 연결할 것인데 그 두 개의 부모는 두개의 노드 합으로 만들어

연결시키기를 반복할 것이다. 그리고 다시 최소 힙에 넣는 것이다.  -> 최소 힙에 노드가 하나가 남을 때까지 반복

이 과정을 그림으로 나타내겠다.

 

(2)

(3)

(4)

(완성)

이진 트리가 만들어졌다.

이제 이것으로 어떻게 비트 코드를 만드느냐

왼쪽 간선을 타고 가면 1이고 오른쪽 간선을 타고 가면 0이라고 하는 것이다.

 

일단 리프노드(가장 아래에 있는 노드)에 해당하는 빈도수는 그 문자라고 생각하자,

 

4를 가진 노드까지 타고 내려가면 101이 된다.

즉 s는 101로 나타내는 것이다.

이런 방법으로 위의 비트 코드를 만들어 낸 것이다.

 

허프만 코드 생성 절자

• 허프만 트래 내의 각 노드들은 최소 힙에 삽입된다.
• 최소 힙에서 두 개의 노드를 삭제한다.
• 그 두개의 노드를 하나로 연결해 하나의 노드로 만든 후, 연결된 노드를 최소 힙에 다시 삽입한다.
• 위의 과정을 최소 힙에 하나의 노드만 존재할 때까지 반복한다.