허프만 코드 (Huffman Code)

허프만 코드 (Huffman Code)는 최적 프리픽스 (Optimal prefix codes)를 사용하여 데이터를 효과적으로 압축 할 수 있는 알고리즘이다. 

이 알고리즘은 무손실 압축* (Lossless compression) 으로 데이터에 따라 20~90%까지 압축이 가능하다.

* 무손실 압축은 데이터를 압축하고 복원할 때, 복원한 데이터가 원형의 데이터와 동일한 것을 의미한다.

그럼 알고리즘을 설명하기 전에 몇 가지 기본적인 부분을 살펴보자.

위에서 언급했듯이 허프만 코드는 최적 프리픽스 코드를 사용한다. 여기서 프리픽스 코드는 앞의 문자가 뒤의 문자에 접두사 될 수 없는 것이다.

예를 들어 아래의 표를 보자.

a	b
0	101

표를 바탕으로 a의 코드는 0이고 b의 코드는 101이다. 

이 떄, 01010101 이렇게 코드가 나오면 앞 부터 abab이다. 그 이유는 인덱스 0 (01010101이 배열이라고 가정했을 때)에 포함되는 문자는 a 밖에 없기 떄문이다. (b는 1부터 시작하기 때문에) 

그렇기 때문에 허프만 코드는 이러한 접두사가 될 수 없는 프리픽스 코드만을 사용하여 데이터를 압축한다.

(한 가지 눈치 챌 수 있듯이, 프리픽스 코드를 나타내는 테이블이 항상 존재해야 압축을 하거나 풀 수 있다.)

그러면 구현 방식을 하나씩 살펴 보도록 하자.

아래는 허프만 코드의 의사코드이다. (언어별 코드는 구글링 하면 쉽게 찾을 수 있다.)

C : n 개의 문자로 이루어진 문자열 |C| : C의 문자 갯수 Q : 최소 우선 순위 큐 EXTRACT-MIN : 큐에서 가장 최소 값 추출 ---------------- 1. n = |C| 2. Q = C 3. for i = 1 to n - 1 4.     z.left = x = EXTRACT-MIN(Q) 5.     z.right = y = EXTRACT-MIN(Q) 6.     z.freq = x.freq + y.freq 7.     INSERT(Q, z) 8. return EXTRACT-MIN(Q)

의사 코드는 간단하다. 단순하게 최소 우선 순위 큐를 사용하여 자식 노드로 만들고 붙이는 것이다. (노드의 값은 문자의 빈도수이다.)

이를 그림으로 살펴보면 아래와 같다.

그림 1. Huffman Tree

그림 1은 문자열을 바탕으로 허프만 트리를 생성하였다. 해당 트리는 왼쪽은 무조건 0이고 오른쪽은 무조건 1을 나타내기 때문에 이를 기준으로 테이블을 만들면 아래와 같이 나타낼 수 있다.

E	U	D	L	C	Z	K	M
0	100	101	110	1110	111100	111101	11111

* 빈도수가 크면 클수록 코드가 나타내는 값은 작다.

** 내부 노드는 전체 문자 (적어도 하나의 문자) - 1개를 가지고 있다.

허프만 코드는 나온지 오래된 압축 알고리즘이다. (논문이 1952년이니까..) 때문에 허프만 코드보다도 성능이 좋은 압축 알고리즘은 여럿 존재한다.

그렇지만 아직도 널리 사용되고 있는데.. 허프만 코드가 알고리즘이 단순하고 빠르기 때문이다. 그래서 JPEG, MP3과 같은 codec에서 사용된다.

참조

- http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/huffman.php

- https://en.wikipedia.org/wiki/Huffman_coding