[자료구조] 허프만 코드 (Huffman Code)

 

허프만 코드 (Huffman Code)

앞서 포스팅한 이진 트리를 응용해서 문자열을 압축할 수 있습니다.

허프만 코드는 문자열을 사용한 빈도수에 따라 우선순위를 매겨 이것을 최소 힙 트리로 만들어 마치 압축한 것처럼 바꾸는 것입니다.

예를 들어, 다음과 같은 문장이 있다고 해봅시다.

data structure and algorithm

 

이 문장에서 문자들의 빈도수는 다음과 같습니다.

문자	빈도수	문자	빈도수
a	4	m	1
c	1	n	1
d	2	o	1
e	1	r	3
g	1	s	1
h	1	t	4
i	1	u	2
l	1

이 표에 나온 정보들을 바탕으로 허프만 코드를 만들어 보겠습니다.

위에서 최소 힙 트리를 만든다고 했는데, 빈도수가 최소 힙 트리의 인자값이 되면 됩니다.

우선, 빈도수가 가장 적은 원소를 묶습니다. 이 때, 한 번 묶을 때 그 상황에서 가장 작은 수가 나올 수 있도록 묶어주면 됩니다. 예를 들어, 지금 상황에서 빈도수가 c, e가 제일 작으므로 (사실 빈도수가 각각 1인 경우의 수는 많지만 편의를 위해 알파벳순으로 진행하겠습니다) 묶습니다.

이런 식으로 하나의 최소 힙 트리가 나올 때까지 진행하면 됩니다.

 

Phase 1. 참고 사항 1) 2, 2', 2'', 2'''은 모두 같은 2이다. 트리를 그려주는 에디터가 노드에 중복된 값을 넣을 수 없게 되어 있다. 참고 사항 2) 각각의 Phase는 이해하기 쉽게 임의로 나누어 놓은 것이다. 절대적인 것은 아니므로 참고

이 상황에서 새로운 알파벳 2개를 묶는 것보다 이미 만들어져 있는 트리에 새로운 알파벳을 묶는게 더 빈도수가 작은 경우가 있습니다. 그럴 때는 하나의 새로운 알파벳과 가장 작은 최소 힙 트리를 묶어주면 됩니다.

 

Phase 1-1.

이런 식으로 노드가 얼마나 방대해지는가에 상관 없이 무조건 그 상황에서 빈도수가 가장 작은 경우의 수에 따라 트리를 어떻게 묶을지 정해주면 됩니다.

 

Phase 2.

 

Phase 3.

 

Phase 4.

 

Phase 5.

하나의 최소 힙 트리로 완성되었으면, 각 간선에 숫자를 매깁니다. 루트에서 특정 알파벳까지 거쳐간 모든 숫자가 그 알파벳의 허프만 코드가 됩니다.

 

정리하면 다음과 같습니다.

알파벳	허프만 코드	알파벳	허프만 코드
t	011	o	1001
u	111	m	1010
d	110	n	1011
r	0001	c	00000
a	0011	e	00001
i	0100	g	00100
l	0101	h	00101
s	1000

실제로 허프만 코드를 이용한 문자열은 다음과 같습니다.

 

data structure and algorithm → 11000110110011 1000011000111100000011111000100001 00111011110 0011010100100100100010100011001011010

 

코드는 아래와 같습니다.

void huffman_tree(int freq[], char ch_list[], int n) {
    TreeNode *node, *x;
    Heap *heap;
    element e, e1, e2;
    int codes[100];
    int top = 0;
    heap = create();
    init(heap);

    for (int i = 0; i < n; i++) {
        node = make_tree(NULL, NULL);
        e.ch = node->ch = ch_list[i];
        e.key = node->weight = freq[i];
        e.ptree = node;
        insert_min_heap(heap, e);
    }

    for(int i = 1; i < n; i++) {
        // 최소값을 가지는 두 개의 노드를 삭제
        e1 = delete_min_heap(heap);
        e2 = delete_min_heap(heap);

        // 두 개의 노드를 합친다.
        x = make_tree(e1.ptree, e2.ptree);
        e.key = x->weight = e1.key + e2.key;
        e.ptree = x;
        printf("%d + %d -> %d \n", e1.key, e2.key, e.key);
        insert_min_heap(heap, e);
    }

    e = delete_min_heap(heap);
    print_codes(e.ptree, codes, top);
    destroy_tree(e.ptree);
    free(heap);
}