한양과기고 에듀테크 수업도구 대시보드

산술 부호화 — 글자 한 개를 1비트보다 잘게

허프만 코딩은 한 글자에 정수 비트(1비트, 2비트…)만 배정할 수 있다. 그래서 어떤 글자의 "이상적인" 길이가 1.4비트라도 2비트를 써야 한다. 산술 부호화는 메시지 전체를 하나의 소수 로 바꾼다. [0, 1) 구간을 글자가 나올 때마다 확률만큼 잘게 쪼개고, 마지막에 남은 좁은 구간 안의 숫자 하나를 2진 소수로 적으면 끝이다. 덕분에 글자당 소수점 이하 비트 까지 쥐어짤 수 있어 이론 한계(엔트로피)에 거의 붙는다.

1. 글자별 확률 & 구간 나누기

각 글자는 [누적확률_시작, 누적확률_끝) 라는 자기만의 칸을 [0,1) 안에 갖는다.

2. 글자마다 구간을 그 글자의 칸으로 좁히기

low = 0 다음: – high = 1

‘부호화 시작’ 뒤 다음 글자를 눌러 구간이 좁아지는 과정을 보세요.

3. 남은 구간 → 2진 소수 → 비트열

–

ASCII 고정 8비트

–

산술 부호화 (bits)

–

엔트로피 한계 (bits)

ASCII 8비트 고정–

허프만 (정수 비트)–

산술 부호화–

엔트로피 한계 (이론상 최소)–

–

4. 어떻게 되돌릴까? (복호화)

받는 쪽은 그 숫자 하나와 확률표, 글자 수만 있으면 된다.

5. 알고리즘 (의사코드)

# 인코딩: 구간 [low, high) 를 계속 좁힌다 low, high = 0.0, 1.0 for ch in message: span = high - low high = low + span * cumHigh[ch] # 글자 칸의 끝 low = low + span * cumLow[ch] # 글자 칸의 시작 # [low, high) 안에 들어가는 가장 짧은 2진 소수를 출력 emit_shortest_binary_fraction_in(low, high) # 디코딩: 같은 나눗셈을 거꾸로 value = 0.b1b2b3... # 받은 비트열을 2진 소수로 for _ in range(message_length): # value 가 어느 글자 칸에 있는지 찾는다 ch = symbol_whose_range_contains(value) output(ch) span = cumHigh[ch] - cumLow[ch] value = (value - cumLow[ch]) / span # 그 칸을 다시 [0,1) 로 펼침

6. 왜 허프만보다 좋을까?

글자당 소수점 비트

구간 폭은 각 글자 확률의 곱이 된다. 최종 비트 수 ≈ -log2(폭) = Σ -log2(p). 확률이 0.9인 글자는 약 0.15비트만 먹는다. 허프만은 최소 1비트를 강제당해 이 상황에서 크게 손해다.

엔트로피에 거의 붙는다

섀넌의 엔트로피 H = Σ -p·log2(p)가 글자당 이론상 최소 비트다. 산술 부호화의 오버헤드는 메시지 전체에 2비트 미만 — 글자 수가 많을수록 손해가 0에 수렴한다.

적응형과 궁합이 좋다

다음 글자를 쓰기 직전에 확률표를 갱신해도 된다(adaptive). 트리를 다시 만들 필요가 없어, 문맥마다 확률을 바꾸는 PPM·CABAC(H.264/H.265) 같은 강력한 압축의 뼈대가 된다.

현실의 문제들

double 로는 금방 정밀도가 바닥난다 → 실제로는 정수 range coder로 구현하고, 구간이 좁아지면 확정된 앞 비트를 흘려보내는 renormalization을 쓴다. 끝을 알리려면 메시지 길이나 EOF 기호가 필요하다. 특허 때문에 한동안 회피되다 2000년대에 풀렸다.

기반 아이디어는 1970년대 Rissanen · Pasco. 오늘날 bzip2, JPEG 2000, H.264/H.265, 최신 Zstandard의 rANS 등에 쓰인다.