허프만 코딩(Huffman Coding)

안녕하세요. 이경민입니다.

 

대용량 처리에 관해서 예전부터 관심이 많았는데, 압축 분야의 기본인 허프만 코딩에 대해 얕은 지식을 써볼까 합니다.

 

먼저 허프만 코딩을 이용한 압축의 기술적인 사항을 살펴보기 전에, 텍스트 압축이 어떻게 이루어지는지 개념적으로 살펴보도록 하죠.

 

텍스트 문서를 압축하기 위해서는 문서에 어떤 처리를 해주어야 할까요? 여러 가지 방법이 있겠지만, 허프만 코딩을 이용한 텍스트 압축에서는, 다음과 같은 기본 개념에 기초를 두고 있습니다.

 

“많이 나오는(출현 빈도수가 높은) 기호에는 짧은 코드 길이를 부여한다.”

 

우리가 일반적으로 사용하는 아스키 코드의 경우에서는 모든 기호의 코드 길이가 8비트로 동일합니다. 아스키 코드에서 최상위 비트는 확장 문자를 나타내기 위해 사용되고, 나머지 7비트를 이용해 총 128개의 기호를 표현합니다. 이런 방식은 이해하기 쉬우며, 문자를 처리하는 속도가 빠르지만, 우리가 배우려는 압축을 전혀 고려하지 않는 단점이 있습니다.

 

대용량 처리를 위해서, 텍스트 문서를 압축하기 위해서는, 문서에서 상대적으로 많이 나오는 기호들에 8비트 보다 더 짧은 코드길이를 부여함으로써 가능하게 됩니다. 하지만 특정 기호에 더 짧은 코드 길이를 부여하려면, 다른 기호들에는 필수적으로 8비트보다 더 긴 코드길이를 부여해야 합니다.

 

예를 들어, 특정 문서가 영문자 a, b, c, d, e, f, g, h로만 이루어져 있다고 합시다.

그리고 각 문자의 문서에서 나타나는 확률이 아래의 표와 같다고 합시다.

 

문자	확률 값
a	0.3
b	0.2
c	0.15
d	0.1
e	0.1
f	0.05
g	0.05
H	0.05

표 1) 문자들의 확률 값

 

이 문서를 위해 압축을 고려하지 않은 일반적인 코드를 생성한다고 하면, 한 글자를 나타내기 위해서는 몇 비트가 필요할까요?

총 8개의 글자이므로, 23 = 8, 에서 총 3비트가 필요할 것입니다.

각 글자에 아스키 코드와 같은 방식, 즉 압축을 고려하지 않는 방식으로 코드를 부여한다면 다음과 같이 될 것입니다.

 

문자	코드
a	000
b	001
c	010
d	011
e	100
f	101
g	110
h	111

표 2) 압축을 반영하지 않은 코드

 

이렇게 코드를 부여하는 방식이 바로 우리가 일반적으로 사용하는 ASCII 코드에서 사용하는 방식이죠.

 

그런데, 이 문서에서 각 문자가 나타날 확률이 다르기 때문에, 더 많이 나타나는 문자에 더 짧은 코드를 부여한다면 문서의 크기를 줄일 수 있을 것입니다. 각 문자들이 나타나는 확률을 반영해 각 문자에 코드를 부여한다면, 아마 다음과 같은 코드를 생성할 수 있을 것입니다.

 

문자	코드
a	11
b	00
c	101
d	010
e	1000
f	1001
g	0110
h	0111

표 3) 허프만 코드

 

문서의 대부분을 차지하는 a, b에 2비트의 코드를 부여함으로써, 문서의 크기를 상당량 줄일 수 있을 것입니다. 기존 방식에서는 코든 글자들에 똑같이 3비트가 부여되어 있으므로, 3비트씩 끊어서 읽어 문자들을 해독할 수 있지만, 위와 같이 각 글자마다 코드 길이가 다르게 되어 있을 때는 문서의 디코딩이 제대로 이루어 질 것인가에 대해 의문을 가질 수 있을 것입니다.

 

다음의 예를 살펴보도록 합시다.

예를 들어, bcgaaaefh 라는 문자열을 바로 위의 코드 체계로 인코딩 해보면, 다음과 같은 코드가 될 것입니다.

001011111111000100101110110

그럼 위의 인코딩된 코드를 디코딩해서 bcaaaefhg 문자열을 얻는 과정을 살펴봅시다.

 

가장 짧은 코드 길이가 2비트임으로, 처음 2비트 읽어오면 00입니다. 이는 위 코드표의 b와 일치하는 군요. b를 출력합니다. 다음 2비트를 읽으면 10입니다. 이 코드와 일치하는 문자가 없으므로, 한 비트를 더 읽어오면 101이 되고 이는 c와 일치하므로 c를 출력합니다. 이와 같은 방식으로 인코딩된 코드에서 한 비트씩 읽어온 후, 코드표에 일치하는 문자가 있는지 검사하여 일치한 문자를 출력함으로써, 디코딩이 제대로 이루어 지게 됩니다.

 

디코딩 과정을 살펴봤는데, “흠 이런 식의 코드 체계를 사용하면, 디코딩 과정에서 혹시 하나라도 잘못 디코딩 되는 문자는 없을까?” 하는 걱정을 가지고 분들이 있을지 모르겠습니다. 하지만, 그럴 일은 절대 발생하지 않는데, 위의 코드 표를 자세히 살펴보면, 다음과 같은 특징을 발견할 수 있습니다.

 

한 문자의 코드는 다른 코드의 처음 부분과 일치하지 않는다.

 

예를 들어, a의 코드는 11인데 이를 다른 코드들의 처음 2비트와 비교해 본다면 11로 시작되는 코드가 하나도 없음을 알 수 있을 것입니다. 마찬가지로 d의 코드는 010인데 010으로 시작하는 코드는 d외에 하나도 없는 것을 확인할 수 있습니다. 바로 이런 종류의 코드를 prefix code(더 정확히 prefix-free code)라고 합니다.

 

그렇다면, 어떻게 이런 prefix code를 생성할 수 있을 까요?

문자들의 개수가 위와 같이 8개 정도로 작을 때면, 간단히 손으로 써보면서 각 문자들의 코드를 정할 수 있겠지만, 기호의 개수가 많을 때는 이런 방법은 불가능 할 것입니다. 따라서, 각 기호에 적절한 코드를 부여하는 알고리즘이 필요한데, 그것이 바로 허프만 코딩 알고리즘입니다.

허프만 코딩 알고리즘은 허프만 트리라 불리는 특수한 트리를 생성하는 것으로, 아래의 허프만트리를 살펴보도록 합시다.

 

l  허프만 트리(Huffman Tree)

 

 

그림 1 허프만 트리

 

위 트리는 표 3에서 나타나는 허프만 코드를 생성하기 위해 사용되는 허프만 트리로, 트리를 생성하는 방법은 조금 후에 살펴보고 트리에 대해 살펴보도록 합시다. 트리의 리프 노드는 문자와 그 확률을 저장하고 있고, 중간 노드는 자식 노드의 확률을 합한 값을 저장하고 있습니다.

가지의 왼쪽 부분에는 숫자 0, 1이 있는 것을 볼 수 있을 것입니다. 이는 각 문자들의 코드를 이루고 있는 비트로써, 루트 노드에서 각 리프 노드의 이르는 가지들의 숫자들이 그 문자의 코드가 되고, 이는 표 1 에 나타나는 각 문자의 코드와 일치합니다.

 

허프만 트리 생성

 

ü  허프만 트리를 생성하기 위해서는 트리의 노드를 저장하는 두 개의 큐(큐1, 큐2)가 필요하다.

1. 인코딩 하려는 모든 문자과 그 확률 값을 갖는 리프 노드를 생성한다.
2. 모든 리프 노드를 큐1에 넣는다.
3. 큐1과 큐2에, 두 개 이상의 노드가 있을 때까지 다음을 반복한다.
   1. 큐1과 큐2에서, 어느 큐에서든 상관없이, 확률이 가장 낮은 두 개의 노드를 꺼낸다.
   2. 방금 꺼낸 두 개의 노드를 자식 노드로 갖는 중간 노드를 생성하고 생성한 중간 노드의 확률 값은 두 자식 노드의 확률 값을 더한 것으로 한다.
   3. 생성한 중간 노드를 두 번째 큐에 넣는다.
4. 마지막에 남은 하나의 노드가 루트 노드이다. 이제 허프만 트리가 완성되었다.

 

그럼, 표 1에 나타나는 문자들을 실제 위 알고리즘에 적용하는 과정을 살펴보도록 합시다.

 

ü  아래의 표들은 작업이 이루어진 후의 큐의 상태로, 괄호 안의 숫자는 노드 확률 값을 나타냅니다.

 

먼저, 각 문자와 그 확률 값을 갖는 노드를 생성하여 큐1에 넣습니다.

큐1	a(0.3), b(0.2), c(0.15), d(0.1), e(0.1), f(0.05), g(0.05), h(0.05)
큐2

 

큐1에서 가장 작은 확률 값을 갖는 노드 중 f와 g를 꺼내, f와 g를 자식 노드로 갖는 중간 노드 ①을 생성하고 그 확률 값은 자식 노드의 확률 값을 합한 0.1로 합니다. 생성한 중간 노드를 큐2에 넣습니다.

큐1	a(0.3), b(0.2), c(0.15), d(0.1), e(0.1), h(0.05)
큐2	①(0.1)

 

큐1과 큐2에서 가장 작은 확률 값을 갖는 노드 중, e와 h를 꺼내, 이 노드를 자식 노드로 갖는 중간 노드를 생성합니다.

큐1	a(0.3), b(0.2), c(0.15), d(0.1)
큐2	①(0.1), ②(0.15)

 

다음으로 작은 확률 값을 갖는 노드 2개를 선택하면, ①과 d가 선택되고, 다시 위 과정을 반복합니다.

큐1	a(0.3), b(0.2), c(0.15)
큐2	②(0.15), ③(0.2)

 

위 과정을 계속 반복하면, 결국 확률 값을 1.0을 갖는 노드가 남게 되고 그것이 허프만 트리의 루트 노드가 됩니다. 그리고 생성된 허프만 트리를 이용하여 각 문자에 허프만 코드를 부여하면 되는 것입니다.

 

이상으로 허프만 코딩에 대해서 간단히 알아보았습니다.