압축 알고리즘의 분류 엔트로피 기반과 사전 기반

압축 알고리즘의 분류: 엔트로피 기반과 사전 기반

1. 서론

데이터 압축은 디지털 데이터를 보다 효율적으로 저장하고 전송할 수 있도록 변환하는 기술입니다. 압축 알고리즘은 크게 엔트로피 기반(Entropy-based) 압축 알고리즘과 사전 기반(Dictionary-based) 압축 알고리즘으로 나뉩니다.

본 포스팅에서는 이 두 가지 방식의 원리를 설명하고, 각각의 대표적인 알고리즘을 Java와 C 코드 예제와 함께 소개하겠습니다.

---

2. 엔트로피 기반 압축 알고리즘

2.1 개념

엔트로피 기반 압축 알고리즘은 데이터 내의 통계적 특성을 활용하여 보다 짧은 코드로 데이터를 표현하는 방식입니다. 주어진 데이터에서 특정 기호의 등장 빈도가 높을수록 짧은 코드로 변환하고, 낮을수록 긴 코드로 변환하여 전체적인 데이터 크기를 줄입니다.

대표적인 엔트로피 기반 압축 기법으로는 허프만 코딩(Huffman Coding)과 산술 코딩(Arithmetic Coding)이 있습니다.

2.2 허프만 코딩 (Huffman Coding)

허프만 코딩은 가변 길이 인코딩 방식을 사용하여 빈도가 높은 기호에는 짧은 코드를, 빈도가 낮은 기호에는 긴 코드를 할당합니다. 허프만 트리를 구성하여 최적의 프리픽스 코드(prefix-free code)를 생성합니다.

2.2.1 Java 예제 (허프만 코딩)

import java.util.*;

class HuffmanNode implements Comparable<HuffmanNode> {
    char ch;
    int freq;
    HuffmanNode left, right;

    HuffmanNode(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }

    public int compareTo(HuffmanNode node) {
        return this.freq - node.freq;
    }
}

public class HuffmanCoding {

    public static void buildHuffmanTree(Map<Character, Integer> freqMap) {
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();

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

        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();

            HuffmanNode newNode = new HuffmanNode('\0', left.freq + right.freq);
            newNode.left = left;
            newNode.right = right;

            pq.add(newNode);
        }
    }

    public static void main(String[] args) {
        Map<Character, Integer> freqMap = new HashMap<>();
        freqMap.put('a', 5);
        freqMap.put('b', 9);
        freqMap.put('c', 12);
        freqMap.put('d', 13);
        freqMap.put('e', 16);
        freqMap.put('f', 45);

        buildHuffmanTree(freqMap);
    }
}

2.2.2 C 예제 (허프만 코딩)

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

struct HuffmanNode {
    char ch;
    int freq;
    struct HuffmanNode *left, *right;
};

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

int main() {
    struct HuffmanNode* node = createNode('a', 5);
    printf("Character: %c, Frequency: %d\n", node->ch, node->freq);
    free(node);
    return 0;
}

---

3. 사전 기반 압축 알고리즘

3.1 개념

사전 기반 압축 알고리즘은 데이터에서 반복되는 패턴을 찾아 이를 사전에 저장하고, 패턴을 참조하는 방식으로 데이터를 압축합니다. 대표적인 방식으로는 LZ77, LZ78, LZW가 있습니다.

3.2 LZW (Lempel-Ziv-Welch) 알고리즘

LZW 알고리즘은 데이터에서 반복되는 문자열을 탐색하여, 이를 사전에 추가하고 해당 패턴을 사전의 색인 값(index)으로 치환하는 방식으로 작동합니다.

3.2.1 Java 예제 (LZW 압축)

import java.util.*;

public class LZWCompression {
    public static List<Integer> compress(String input) {
        Map<String, Integer> dictionary = new HashMap<>();
        int dictSize = 256;
        for (int i = 0; i < dictSize; i++) {
            dictionary.put("" + (char) i, i);
        }

        String current = "";
        List<Integer> result = new ArrayList<>();
        for (char c : input.toCharArray()) {
            String combined = current + c;
            if (dictionary.containsKey(combined)) {
                current = combined;
            } else {
                result.add(dictionary.get(current));
                dictionary.put(combined, dictSize++);
                current = "" + c;
            }
        }
        if (!current.isEmpty()) {
            result.add(dictionary.get(current));
        }
        return result;
    }

    public static void main(String[] args) {
        String input = "ABABABABA";
        System.out.println(compress(input));
    }
}

---

4. 결론

이번 포스팅에서는 압축 알고리즘을 크게 엔트로피 기반과 사전 기반으로 나누어 설명하였습니다. 엔트로피 기반 방식은 데이터의 빈도수를 활용하여 최적의 코드 길이를 부여하는 방식이며, 대표적으로 허프만 코딩과 산술 코딩이 있습니다. 사전 기반 방식은 데이터 내 반복되는 패턴을 사전에 저장하고 참조하는 방식이며, 대표적으로 LZ77, LZ78, LZW 알고리즘이 있습니다.

각각의 방식은 데이터 특성에 따라 성능이 달라지므로, 특정한 상황에서 어떤 압축 알고리즘을 선택할지 신중하게 고려해야 합니다.