[Algorithm] 허프만 코드

허프만 코드는 문자를 데이터로 표현할 때 더 적은 데이터양을 사용하면서 문자를 표현하기 위해 압축하는데 사용하는 방법으로 Greedy Algorithm중 하나입니다.

 

문자의 빈도수를 이용하여 사용빈도수가 높은 문자는 짧은 비트로 표현, 사용빈도수가 낮은 문자는 긴 비트로 표현합니다.

즉, 가변 길이 코드이다.

 

예시를 들어 설명하겠습니다.

EX) 압축하고자 하는 문자열 : bacbca

-> 고정 길이 코드 : a~c. 3개의 문자를 구분하기 위해 2bit 필요하고 총 12bit를 사용한다

-> 가변 길이 코드 : 허프만 코드를 이용해서 나온 값으로 10bit로 줄어든다

 

 

그러나 여기서 의문점이 있다.

010을 ac(0/10)인지 ba(01/0)인지 구분이 안간다

 

 

즉 이진 코드를 다시 문자열로 변환할 때 어디에서 끊어서 문자를 해독해야하는지 알 수 없다는 문제가 생긴다.

이렇게 되면 계산에 걸리는 시간이 오래걸리기도 하고 잘못된 해석이 될 수 있다.

이 문제를 해결하기 위해 전치 코드(prefix code) 개념 등장하였는데

 

전치코드란?

이진 코드의 집합이 서로 접두어가 되지 않은 코드

간단하게 "이미 쓰인 코드는 다른 코드의 앞에 등장하지 않는다"라는 규칙을 추가한 것이다

 

전치코드는 트리구조를 사용하며

만드는 과정은 아래와같다

1) 발생 빈도가 가장 낮은 두 문자를 선택하고 하나로 합친다.

2) 왼쪽에는 빈도수가 낮고 오른쪽에는 높은순으로 배치한다.

3) 빈도수가 같은 것 중에서는 작은 것을 우선으로 연결한다. 

4) 트리가 완성이 되면 0과 1을 부여한다

 

예시

"ILIKEAPPLEJUICE"를 한번 압축해보겠습니다

일단 빈도수가 낮은 순서대로 정렬을 합니다.

A:1 / C:1 / J:1 / K:1 / U :1 / L:2 / P:2 / E:3 / I:3

 

1) 발생 빈도가 가장 낮은 두 문자를 선택하고 하나로 합친다.

 

 

2)왼쪽에는 빈도수가 낮고 오른쪽에는 높은 순으로 배치한다(U 1개 < L 2개)

 

3) 빈도수가 같은 것 중에서는 작은 것을 우선으로 연결한다. (A C 트리가 J K트리보다 작기때문에 연결한다)

 

 

이를 반복하여

E와 JK 트리를 합치고 (5)  I와 UL트리를 합친후

또 만들어진 빈도수가 낮은 트리끼리 합친다

 

 

 

이를 반복하여 완성한 트리 노드의 왼쪽 간선에는 0, 오른쪽 간선에는 1 가중치를 둡니다.

 문자들을 루트로부터 탐색했을 때 지난 간선들의 가중치들의 합이 허프만 코드(가변 길이 코드)가 됩니다.

 

 

 

 

아스키 코드와 비교를 통해 확실하게 압축이 되었음을 알 수 있다.

 

관련된 포스팅

[Algorithm] Greedy

[Algorithm] 최소 신장 트리(MST), Kruskal & Prim algorithm

[Algorithm] 다익스트라 알고리즘(Dijkstra Algorithm)

[Algorithm] Scheduling

[Algorithm] Greedy Code 모음