Arithmetic Coding
개념
데이터 압축을 할 때 Huffman Coding(허프만 코딩)을 자주 쓰게 된다. 하지만 허프만 코딩은 자주 나오는 문자라도 ‘최소 1비트’를 차지해야 한다는 한계가 있다. 만약 데이터의 확률이 극단적으로 치우쳐 있다면 Huffman Coding을 쓰기에 비효율적이다. 이 한계를 극복하기 위해 데이터 전체를 단 하나의 소수(Decimal)로 변환하여 압축을 하는 알고리즘이 바로 Arithmetic Coding(산술 코딩)이다.
원리
산술 코딩의 원리는 간단하다. 0.0과 1.0 사이의 공간을 각 문자의 등장 확률만큼 나눈다. 그리고 문자가 들어올 때마다 해당 문자의 공간으로 Zoom-in하며 범위를 좁혀나간다. 마지막에 남은 좁은 범위 안의 숫자 하나만 저장하면, 그 숫자 하나로 전체 메시지를 복원할 수 있다.
압축 수식
새로운 글자가 들어올 때마다 현재의 시작점과 끝점을 갱신하는 공식이다.
먼저, 현재 우리가 가지고 있는 전체 구간의 길이를 구한다.
\[R_{old} = H_{old} - L_{old}\]그다음, 새롭게 들어온 글자의 고유 확률 구간(시작점 $L_{sym}$, 끝점 $H_{sym}$)을 곱하여 새로운 전체 구간을 설정한다.
\[L_{new} = L_{old} + (R_{old} \times L_{sym})\] \[H_{new} = L_{old} + (R_{old} \times H_{sym})\]- $L_{old}, H_{old}$: 현재 구간의 하한값(Low)과 상한값(High)
- $R_{old}$: 현재 구간의 전체 길이 (Range)
- $L_{sym}, H_{sym}$: 새로 들어온 기호에 원래 할당되어 있던 0.0 ~ 1.0 사이의 고유 하한값과 상한값
압축 해제 수식
디코딩은 압축이 모두 끝나고 저장된 최종 실수값 하나를 가지고 원래 글자들을 뽑아내는 과정이다. 이 최종값을 $V$라고 하자.
현재 구간 안에서 $V$가 실제로 차지하는 상대적 위치(비율)를 역산하는 공식은 다음과 같다.
\[Target = \frac{V - L_{old}}{R_{old}}\]- 처음 시작할 때는 $L_{old} = 0$, $R_{old} = 1$이므로 $Target$은 $V$가 된다.
- 계산된 $Target$ 값이 원래 정해둔 어떤 기호의 $L_{sym}, H_{sym})$ 구간 안에 들어가는지 확인하여 그 기호를 복원한다.
- 기호를 하나 복원하고 나면, 인코딩 때와 완전히 똑같은 수식($L_{new}$, $H_{new}$)을 이용해 구간을 업데이트를 한 뒤, 다음 글자를 찾기 위해 위 과정을 반복한다.
실제 계산 예제: “ACB” 압축과 복원
수식만으로는 헷갈릴 수 있으니, 문자열 “ACB”를 직접 압축하고 다시 풀어보자. 먼저 각 문자의 등장 확률이 다음과 같이 주어졌다고 가정한다. (시작 상태는 $L_{old} = 0.0$, $R_{old} = 1.0$)
| 문자 | 확률 (%) | 시작점 ($L_{sym}$) | 끝점 ($H_{sym}$) |
|---|---|---|---|
| A | 60% | 0.0 | 0.6 |
| B | 30% | 0.6 | 0.9 |
| C | 10% | 0.9 | 1.0 |
1. 인코딩(Encoding) 과정
- 첫 번째 문자 ‘A’
- A의 고유 구간: $0.0 \sim 0.6$
- $L_{new} = 0.0 + (1.0 \times 0.0) = 0.0$
- $R_{new} = 1.0 \times 0.6 = 0.6$
- 현재 상태: $0.0 \sim 0.6$ (길이 0.6)
- 두 번째 문자 ‘C’
- C의 고유 구간: $0.9 \sim 1.0$
- $L_{new} = 0.0 + (0.6 \times 0.9) = 0.54$
- $R_{new} = 0.6 \times 0.1 = 0.06$
- 현재 상태: $0.54 \sim 0.60$ (길이 0.06)
- 세 번째 문자 ‘B’
- B의 고유 구간: $0.6 \sim 0.9$
- $L_{new} = 0.54 + (0.06 \times 0.6) = 0.576$
- $R_{new} = 0.06 \times 0.3 = 0.018$
- 최종 구간: $0.576 \sim 0.594$
압축 완료 “ACB”라는 문자열은 최종적으로 $0.576 \sim 0.594$라는 좁은 구간으로 수렴했다. 컴퓨터는 이 구간 안에 있는 임의의 숫자, 예를 들어 $0.58$ 하나만 저장하면 된다. 전체 문자열이 소수점 하나로 압축된 것이다.
2. 디코딩(Decoding) 과정
이제 컴퓨터는 저장된 실수 $V = 0.58$ 하나만 가지고 있다. 디코딩 공식을 통해 다시 “ACB”를 찾아내 보자. 시작 상태는 처음과 동일하게 $L_{old} = 0.0$, $R_{old} = 1.0$이다.
- 첫 번째 문자 복원
- Target 계산: $\frac{0.58 - 0.0}{1.0} = 0.58$
- 확률표 확인: $0.58$은 A의 구간($0.0 \sim 0.6$)에 속한다. → 첫 번째 문자: ‘A’
- 구간 업데이트: A의 구간으로 좁힌다. ($L_{old} = 0.0, R_{old} = 0.6$)
- 두 번째 문자 복원
- Target 계산: $\frac{0.58 - 0.0}{0.6} \approx 0.966$
- 확률표 확인: $0.966$은 C의 구간($0.9 \sim 1.0$)에 속한다. → 두 번째 문자: ‘C’
- 구간 업데이트: C의 구간으로 좁힌다. ($L_{old} = 0.54, R_{old} = 0.06$)
- 세 번째 문자 복원
- Target 계산: $\frac{0.58 - 0.54}{0.06} = \frac{0.04}{0.06} \approx 0.666$
- 확률표 확인: $0.666$은 B의 구간($0.6 \sim 0.9$)에 속한다. → 세 번째 문자: ‘B’
단 하나의 숫자($0.58$)에서 원래의 문자열 “ACB”가 복원되었다
Leave a comment