[알고리즘 정리] 허프만 코드(Huffman Code Problem)

Huffman Code Problem

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

Basic Idea

이 방법의 기본적인 아이디어는 문자열를 이진수로 표현할 때, 해당 문장열에서 가장 자주 등장했던 문자를 다른 문자보다 더 짧게 표현하는 것이다. 그런데 이렇게 이진 코드의 길이를 가변으로 만들면, 이진 코드를 다시 문자열로 변환할 때, 어디에서 끊어서 문자를 해독해야하는지 알 수가 없게 된다. 예를 들어 A 라는 문자가 1001 로 표현되었고, B 라는 문자가 100 으로 표현되었다면, 1001001 이라는 코드가 있을 때, 첫 문자를 B로도 해석할 수 있고, A로도 해석할 수 있게된다. 지금은 우리에게 주어진 코드의 길이가 짧아 큰 손해가 없는 것 처럼 보이지만, 엄청나게 긴 문자열을 표현한 이진코드를 해석하게 된다면, 계산에 걸리는 시간은 어마어마할 것이다. 따라서, 이런 문제를 해결하기 위해 Prefix Code 라는 개념을 도입하게 된다.

Prefix Free Code

Prefix Free Code 는 어떤 이진 코드의 집합이 서로 접두어가 되지 않은 코드를 말한다. 예를 들면 우리에게 {0, 1, 01, 010} 이라는 이진코드 집합이 있을 때, 0은 01과 010의 접두어가 될 수 있고, 01은 010의 접두어가 될 수 있기 때문에, Prefix Free Code 가 될 수 없다. 하지만 만약 우리가 가진 이진코드 집합이 {00, 010, 100, 101} 이라면, 모든 코드가 서로 다른 코드에 대해 접두어가 될 수 없기 때문에 Prefix Free Code의 조건을 만족한다. 이 개념을 사용해서 Huffman Code는 위에서 언급했던 중복 해석 문제를 해결할 수 있게 되었다.

Huffman Code Algorithm

Algorithm Flow

허프만 코드는 완전이진트리와 그리디 알고리즘을 통해 코드를 만들고 해석한다. 어떤 문자열의 속한 문자의 전체 빈도수가 100이라고 할 때, 각 문자들이 가진 빈도수가 다음과 같다고 하자.

a	b	c	d	e	f
45	13	12	16	9	5

먼저 이 테이블을 빈도수가 낮은 순으로 정렬을 해주어야 한다. 정렬을 수행하면,

f	e	c	b	d	a
5	9	12	13	16	45

다음과 같은 테이블로 정렬이 된다. 허프만 코드는 빈도수가 낮은 두 개를 하나의 이진트리로 만들어 배열에 다시 넣게 된다. 따라서 빈도수가 제일 낮은 f 와 e 가 합쳐서 새롭게 14로 배열에 들어가게 된다. 따라서 이제 배열은,

f & e	c	b	d	a
14	12	13	16	45

가 된다. 다시 빈도수 순으로 정렬해보자.

c	b	f & e	d	a
12	13	14	16	45

여기서 빈도수가 가장 낮은 두개를 뽑아서 다시 합쳐준다면,

c & b	f & e	d	a
25	14	16	45

이렇게 되고, 다시 배열을 정렬하면,

f & e	d	c & b	a
14	16	25	45

이렇게 된다. 한 번 더 해보자

f & e & d	c & b	a
30	25	45

( f & e -> d ) & (c & b)	a
55	45

이렇게 된다. -> 표시는 서로 부모, 자식 노드 관계임을 표기하고 & 표시는 서로 형제 관계에 있다는 것을 표기했다.

 

최종적으로는 루트 노드 아래에 왼쪽에는 a, 오른쪽에는 ( f & e -> d ) & (c & b) 가 붙어있는 이진트리가 완성된다.

 

위 알고리즘을 조금 더 편하게 수행하는 자료구조가 없을까? 당연히 있다.. Min-Priority-Queue(최소우선순위 큐) 를 사용하면 extract 함수를 통해 최소 값을 바로바로 뽑아낼 수 있고 새로 들어가는 합쳐진 노드들도 큐에 들어가자마자 정렬이 되어 관리하기가 용이해 진다.

Pseudo Code

그렇다면, Huffman Code Algorithm을 Min-Priority-Queue를 사용하는 방법으로 구현하는 pseudo code를 분석해보자.

Huffman-Code (c)
    n = size(C)
    Q = C

    for i = 1 to n-1 // 전체 노드들을 모두 다 돌아볼 것
        do allocalte a new node z // 두 개의 최소등장 횟수 문자를 합칠 노드를 생성
            left[z] = Extract-Min(Q)  // 왼쪽에 현재 큐에서 최소 빈도수를 뽑아 넣는다
            right[z] = Extract-Min(Q) // 오른쪽에 현재 큐에서 최소 빈도수를 뽑아 넣는다
            f[z] = f[left[z]] + f[right[z]] // 새로 만든 노드의 빈도수는 두 자녀노드의 빈도수를 합친 것
            insert(Q, z) // 큐에 새 노드를 넣자.

    return Extract-Min(Q) // 마지막에 하나남은 노드가 루트노드일 것이다.

Encoding and Decoding

• 문자을 huffman 코드로 만들 때는 위 알고리즘을 통해 트리로 만들고, leaf 노드에 다다를 떄까지 왼쪽 자식노드로 이동할 때는 0, 오른쪽 자식노드로 이동할 때는 1을 코드에 계속 더해준다.
• 코드를 문자로 변환할 때는 똑같은 방법으로 leaf 노드에 다다를 때까지 코드가 0일 때는 왼쪽, 1일 때는 오른쪽으로 계속 트리를 따라 이동하고 leaf에 도착하면 그 노드에 저장되어 있는 문자를 읽어들이면 된다.

Alogorithm Analysis

우선순위 큐를 사용하기 때문에 시간복잡도는 O(n log n) 이 될 것이다.