압축 알고리즘 Huffman Coding

압축 알고리즘 Huffman Coding

1. 알고리즘 설명

허프만 코딩(Huffman Coding)은 무손실 데이터 압축 기법 중 하나로, 가변 길이 인코딩을 활용하여 자주 등장하는 문자에는 짧은 코드를, 드물게 등장하는 문자에는 긴 코드를 할당하는 방식으로 데이터를 압축하는 알고리즘입니다. 이 알고리즘은 1952년 David A. Huffman에 의해 고안되었으며, 최적 접두사 코드(Optimal Prefix Code)를 생성하는 데 사용됩니다.

1.1 동작 원리

1. 입력 데이터에서 각 문자의 빈도를 계산합니다.
2. 빈도수를 기반으로 최소 힙(Min Heap) 구조의 우선순위 큐를 생성합니다.
3. 최소 힙에서 두 개의 최소 빈도를 가진 노드를 선택하여 새로운 부모 노드를 생성합니다. 이 부모 노드의 빈도수는 두 자식 노드의 빈도수를 합한 값이 됩니다.
4. 이 과정을 반복하여 하나의 트리(허프만 트리, Huffman Tree)가 만들어질 때까지 진행합니다.
5. 트리의 루트에서 각 문자까지의 경로를 따라 0과 1의 비트 패턴을 생성하여 허프만 코드를 부여합니다.
6. 생성된 허프만 코드를 이용하여 데이터를 압축합니다.

2. 사용 사례 및 장점/단점

2.1 사용 사례

• 파일 압축 프로그램 (ZIP, GZIP 등)
• 이미지 포맷 (JPEG, PNG의 일부 압축 기법)
• MP3, AAC 등의 오디오 압축 포맷
• 데이터 전송 프로토콜에서의 최적화

2.2 장점

• 최적 접두사 코드(prefix-free code)를 생성하여 효율적인 압축이 가능합니다.
• 통계적 방법을 사용하여 자주 사용되는 문자를 짧은 비트로 표현할 수 있습니다.
• 데이터 손실이 없는 무손실 압축 알고리즘입니다.

2.3 단점

• 문자의 빈도수를 기반으로 하므로, 빈도수가 변하는 경우 새로운 허프만 트리를 생성해야 합니다.
• 압축 해제 시 허프만 트리가 필요하므로 추가적인 저장 공간이 필요합니다.
• 부호화 및 복호화 과정에서 추가적인 계산 비용이 발생할 수 있습니다.

3. Java 구현 예제

import java.util.*;

class HuffmanNode {
    int frequency;
    char character;
    HuffmanNode left, right;

    public HuffmanNode(char character, int frequency) {
        this.character = character;
        this.frequency = frequency;
    }
}

class HuffmanComparator implements Comparator<HuffmanNode> {
    public int compare(HuffmanNode x, HuffmanNode y) {
        return x.frequency - y.frequency;
    }
}

public class HuffmanCoding {
    public static void buildHuffmanTree(Map<Character, Integer> freqMap) {
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>(new HuffmanComparator());

        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            queue.add(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

        while (queue.size() > 1) {
            HuffmanNode left = queue.poll();
            HuffmanNode right = queue.poll();
            HuffmanNode parent = new HuffmanNode('-', left.frequency + right.frequency);
            parent.left = left;
            parent.right = right;
            queue.add(parent);
        }
    }

    public static void main(String[] args) {
        Map<Character, Integer> freqMap = new HashMap<>();
        String text = "hello huffman";
        for (char c : text.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        buildHuffmanTree(freqMap);
    }
}

4. C 구현 예제

#include <stdio.h>
#include <stdlib.h>

typedef struct HuffmanNode {
    char character;
    int frequency;
    struct HuffmanNode *left, *right;
} HuffmanNode;

HuffmanNode* createNode(char character, int frequency) {
    HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    node->character = character;
    node->frequency = frequency;
    node->left = node->right = NULL;
    return node;
}

void printCodes(HuffmanNode* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (!root->left && !root->right) {
        printf("%c: ", root->character);
        for (int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

int main() {
    char text[] = "huffman coding example";
    int frequency[256] = {0};
    for (int i = 0; text[i] != '\0'; i++) {
        frequency[(int)text[i]]++;
    }

    // 여기에서 최소 힙을 사용하여 허프만 트리를 구성하는 과정이 필요합니다.
    // 구현을 단순화하기 위해 여기서는 생략합니다.

    return 0;
}

5. 파일 크기 비교 실험

허프만 코딩을 적용하여 실제로 압축이 얼마나 이루어지는지 실험할 수 있습니다. 예제 파일을 준비하고, 원본 파일과 압축된 파일의 크기를 비교하는 실험을 수행합니다.

5.1 실험 방법

1. ASCII 텍스트 파일을 준비합니다.
2. 허프만 코딩을 적용하여 압축합니다.
3. 압축된 파일과 원본 파일의 크기를 비교합니다.

5.2 실험 결과 예시

sample.txt	100 KB	60 KB	40%
example.txt	50 KB	30 KB	40%

이 실험을 통해 허프만 코딩이 데이터 압축에 효과적이라는 점을 확인할 수 있습니다. 하지만 압축률은 데이터의 특성에 따라 달라질 수 있습니다.

6. 결론

허프만 코딩은 빈도 기반의 무손실 압축 알고리즘으로, 텍스트 및 미디어 파일의 압축에 널리 사용됩니다. Java 및 C 언어로 구현할 수 있으며, 파일 크기 비교 실험을 통해 실제 압축 효과를 확인할 수 있습니다. 그러나 허프만 트리 저장 비용과 압축률이 데이터에 따라 달라질 수 있는 점을 고려해야 합니다.