뼈속 깊이 이해하기 :: 1. 허프만 코딩

시작하면서

인터넷에 허프만 코딩을 검색하면 허프만 코딩은 상당히 쉽다고 설명하면서 허프만 트리를 그려놓고 있다. 그렇지만 어떤 이론도 처음 창안해내는 사람의 관점에서 생각하기는 쉽지 않은 일이다. 지식은 창시자를 떠나 많은 사람을 거쳐서 배울 수록 이해가 아닌 암기가 되기 싶다. 그래서 암기하기 쉬운 지식을 쉬운 지식이라고 말하고 있지는 않은가 싶다. 많은 어려운 이론들을 배우지만 아주 사소한 것도 생산하지 못하는 학생이 되는 것을 경계한다. 그런 관점에서 허프만이 되어 허프만 코딩을 뼈속 깊이 이해하는 것은 쉽지 않은 것 같다

사전 지식

컴퓨터가 정보를 전달하기 위해서는 텍스트를 0과 1로 이루어진 숫자 조합을 보내고 받는 쪽에서 이를 해석해 다시 텍스트로 바꾸는 과정이 필요하다.
고정 길이 코드란 고정된 크기만큼의 비트를 사용해서 정보를 인코딩해서 보내는 인코딩방식이다. 우리가 알고있는 ASCII, UNICODE가 이에 해당한다. ASCII는 8비트를 사용해서 인코딩하고 UNICODE는 더 큰 비트를 사용한다.
접두어 코드(Prefix-code) 란 한 코드가 다른 코드의 앞부분이 되는 인코딩 방식이다. 예를 들어 모스 부호는 알파뱃 S를 "· · ·"로 , 알파뱃 E를 "·"로 인코딩한다. 따라서 알파뱃 E를 표현하는 "·"는 알파뱃 S를 표현하는 "···"의 앞부분과 완전히 일치한다. 이 경우 "···"코드를 전달할 때는 코드를 전달받는 사람이 (· · ·)를 EEE가 아닌 S로 해석하기를 기도해야 한다. 이와 같이 접두어 코드는 일련의 코드 조합이 의도하지 않은 방향으로 해석될 수 있는 해석의 어려움을 갖는다.
Prefix-free-code 란 한 코드가 다른 코드의 접두어가 되지 않는 코딩방식이다. 우리가 오늘 다룰 주제인 허프만 코딩이 그 대표적인 방법이다. {“0”, “1”, “01”}의 인코딩 조합은 "0"이 "01"의 접두사가 되기 때문에 접두어 코드이지만 {“1”, “10”, “010”}의 인코딩 조합은 어떤 코드도 다른 코드의 접두어가 될 수 없기 때문에 prefix-free-code이다. 이 인코딩은 해석자가 해석할 때 훨씬 자연스럽고 빠르다.

문제

“ABCDEABC…” 다 섯개의 알파뱃으로 이루어진 총 30자의 텍스트가 있다고 생각해 보자. 이 텍스트에서 각각의 알파뱃이 등장하는 비율을 세어보니 A: 10번, B: 8번, C: 7번, D: 4번, E: 1번으로 나타났다. 이때 정보를 전달하는데 드는 비트 수는 얼마나 들겠는가.

생각의 흐름

위의 사전지식은 잠깐 잊고 어떻게 하면 정보를 전달할 수 있을지 바닥부터 생각해보도록 하려고 한다. 알파뱃을 표현하는 데 사용되는 비트수를 어떻게하면 줄일 수 있을지 차근차근 생각해보자.

version 1.0 - 아스키 코드로 나타내기
아스키 코드를 사용하면 알파뱃을 8비트를 사용해 표현할 수 있다. 그렇다면 가장 단순한 방법으로 계산하면 비용 = 총 30자 x 8비트 = 240비트가 들것이다.

version 1.1 : 사용된 알파뱃만 비트로 표현하기.
해당 텍스트에서 사용된 알파뱃은 5개이다. $2^3=8$ 로 3비트면 총 8가지 표현법이 생긴다. 즉, 알파뱃을 3개 비트로 표현할 수 있다. 비용 = 30자 x 3비트 = 90비트. 약 60퍼센트 비용이 줄어들었다.

A : 000
B : 001
C : 010
D : 011
E : 100

version 1.2
만약 텍스트에서 자주 등장하는 알파뱃 순으로 비트를 인코딩한다면 어떨까?

A : 0
B : 10
C : 01
D : 10
E : 11

이 경우 총 소요 비트 = 각 알파뱃의 등장 횟수 * 각 알파뱃의 인코딩 비트수가 될 것이다.

총 소요 비트 = 10회 x 1비트 + 8회 x 1비트 + 7회 x 2비트 + 4회 x 2비트 + 1회 x 2비트 = 10 + 8 + 14 + 8 + 2 = 42비트이다.

version 1.1에 비해 비용이 줄어들었지만 문제가 생겼다. 인코딩된 비트를 다시 알파뱃으로 바꿀 때 해석이 다양해지기 때문이다. 예를 들어, 01는 0과 1의 조합인 알파뱃 AB와 01인 알파뱃 C로 복수 해석이 가능하다 . 해석의 다양성 문제를 곰곰이 생각해보면 두 가지의 원인이 있는 것 같다.

서로 다른 인코딩 비트를 더해서 하나의 인코딩 비트를 만들어 낼 수 있다.
그로 인해 인코딩 된 비트의 스트림을 입력받았을 때 0...을 입력받았을 때, 알파뱃 A로 읽어야할지, 다음 비트를 기다려 01... C로 읽어야 할지 판단이 어려워지는 것이다.

허프만 코딩이란

허프만 코딩은 위의 문제를 어떻게 해결하고 있을까. 사전지식에서 언급한 것처럼 허프만 코딩은 prefix-free-code를 사용해서 인코딩 비용을 줄이면서도 한 가지 해석만 가능하도록 하였다.
특히 중요한 것은 허프만 코딩은 prefix-free-code를 따르고 prefix-free-code는 항상 이진 트리로 표현할 수 있다.

허프만 트리를 구축하는데 두가지 규칙이 있다.