Arithmetic Coding

Arithmetic Coding

데이터 압축 기법 중 하나인 Arithmetic Coding(산술 부호화)은 확률 모델을 기반으로 가변 길이 부호를 생성하는 방법입니다. 이 글에서는 Arithmetic Coding의 수학적 원리, Huffman Coding과의 비교, 그리고 Java와 C 언어를 이용한 구현 예제 및 응용 방법에 대해 설명합니다.

1. Arithmetic Coding의 개요

Arithmetic Coding은 고정된 비트 길이를 사용하는 전통적인 부호화 기법과 달리, 입력 데이터를 하나의 실수 구간으로 변환하여 부호화합니다. 이러한 방식은 데이터의 빈도수에 따라 보다 효율적인 압축을 가능하게 합니다.

Arithmetic Coding은 다음과 같은 단계로 이루어집니다:

1. 입력 심볼의 확률 분포를 기반으로 구간을 설정합니다.
2. 각 심볼을 해당 구간 내에서 분할하며, 점점 더 작은 구간으로 축소해 나갑니다.
3. 최종적으로 특정한 실수 값으로 데이터가 압축됩니다.
4. 복원 과정에서는 부호화된 실수 값을 통해 원본 데이터를 순차적으로 복원합니다.

2. Arithmetic Coding의 수학적 원리

Arithmetic Coding의 핵심 원리는 입력 심볼을 특정한 확률 범위 내에서 부호화하는 것입니다. 이를 수학적으로 설명하면 다음과 같습니다.

2.1 확률 구간 설정

입력 심볼들의 출현 확률이 주어졌다고 가정합니다. 예를 들어, A, B, C 세 개의 심볼이 각각 50%, 30%, 20%의 확률로 나타난다면, 다음과 같은 구간을 설정할 수 있습니다.

심볼	확률	구간
A	0.5	[0.0, 0.5)
B	0.3	[0.5, 0.8)
C	0.2	[0.8, 1.0)

2.2 부호화 과정

예제 입력이 ABCA라면, 다음과 같은 과정으로 구간을 축소합니다.

1. A → [0.0, 0.5)
2. B → [0.0 + 0.5 × 0.5, 0.0 + 0.5 × 0.8) = [0.25, 0.4)
3. C → [0.25 + 0.15 × 0.8, 0.25 + 0.15 × 1.0) = [0.37, 0.4)
4. A → [0.37 + 0.03 × 0.0, 0.37 + 0.03 × 0.5) = [0.37, 0.385)

부호화된 값으로는 [0.37, 0.385] 사이의 아무 값(예: 0.375)을 선택할 수 있습니다.

2.3 복원 과정

복원할 때는 부호화된 실수 값을 확인하여, 해당 값이 속하는 구간을 찾는 방식으로 원래 입력 데이터를 복원할 수 있습니다.

3. Huffman Coding과의 비교

항목	Arithmetic Coding	Huffman Coding
부호 길이	가변 길이 (실수 값)	가변 길이 (정수 비트)
압축 효율성	더 높은 압축률 가능	상대적으로 낮음
실시간 처리 여부	어려움	쉬움
코드 테이블 필요 여부	불필요	필요

Huffman Coding은 고정된 코드 테이블을 사용하여 데이터를 압축하지만, Arithmetic Coding은 심볼을 실수 구간으로 변환하여 더 높은 압축률을 제공할 수 있습니다. 그러나 Huffman Coding은 연산량이 적고 빠르게 처리할 수 있어 실시간 시스템에 적합합니다.

4. 구현 예제

4.1 Java 구현

import java.util.HashMap;
import java.util.Map;

class ArithmeticEncoder {
    private static class Range {
        double low, high;
        Range(double low, double high) {
            this.low = low;
            this.high = high;
        }
    }

    public static double encode(String input, Map<Character, Double> probabilities) {
        double low = 0.0, high = 1.0;
        for (char c : input.toCharArray()) {
            double range = high - low;
            high = low + range * probabilities.get(c);
            low = low + range * probabilities.get(c);
        }
        return (low + high) / 2;
    }

    public static void main(String[] args) {
        Map<Character, Double> probabilities = new HashMap<>();
        probabilities.put('A', 0.5);
        probabilities.put('B', 0.3);
        probabilities.put('C', 0.2);

        String input = "ABCA";
        double encodedValue = encode(input, probabilities);
        System.out.println("Encoded Value: " + encodedValue);
    }
}

4.2 C 구현

#include <stdio.h>

double encode(const char *input, double *probabilities) {
    double low = 0.0, high = 1.0, range;
    while (*input) {
        range = high - low;
        high = low + range * probabilities[*input - 'A'];
        low = low + range * probabilities[*input - 'A'];
        input++;
    }
    return (low + high) / 2;
}

int main() {
    double probabilities[] = {0.5, 0.3, 0.2};
    char input[] = "ABCA";
    double encoded = encode(input, probabilities);
    printf("Encoded Value: %f\n", encoded);
    return 0;
}

5. 응용 분야

Arithmetic Coding은 다음과 같은 분야에서 활용됩니다:

• 파일 압축: JPEG, Bzip2 등에서 사용
• 데이터 전송: 효율적인 데이터 패킷 압축
• 보안 및 암호화: 정보 이론 기반 보안 기술

6. 결론

Arithmetic Coding은 확률 모델을 기반으로 가변 길이 부호를 생성하여 높은 압축률을 제공합니다. Huffman Coding과 비교했을 때, 더 높은 압축 성능을 가지지만, 연산량이 크기 때문에 실시간 시스템에는 적합하지 않을 수도 있습니다. 다양한 응용 분야에서 사용되며, 데이터 압축 기술의 핵심적인 역할을 수행합니다.