> 산술 부호화 | 분수 비트 | 최적 <
// 산술 부호화 - 엔트로피 한계에 가까운 분수 비트 인코딩
거의 최적
압축 효율을 위해 이론적인 엔트로피 한계에 매우 가깝게 다가갑니다.
분수 비트
확률에 따라 기호를 분수 비트로 인코딩합니다.
스트리밍
데이터가 도착하는 대로 점진적으로 인코딩 및 디코딩할 수 있습니다.
>> 기술 정보
산술 부호화의 동작 방식:
산술 부호화는 전체 메시지를 구간 [0,1) 안의 하나의 숫자로 표현합니다. 각 기호는 자신의 확률에 따라 이 구간을 좁혀 갑니다. 최종 구간은 이진 분수로 인코딩되어 엔트로피 한계에 매우 가까운 압축을 달성합니다.
인코딩 과정:
텍스트: "AAB" 확률: A=0.67, B=0.33 1. 시작: [0, 1) 2. 'A': [0, 0.67) 3. 'A': [0, 0.45) 4. 'B': [0.30, 0.45) 출력: [0.30, 0.45) 구간의 임의의 수 이진수: 0.010011...
산술 부호화를 사용할 이유:
- >우수한 압축 비율
- >엔트로피 한계에 근접
- >임의의 확률 분포를 처리
- >JPEG2000/H.264 등에서 사용
- >특허 만료 (2024)
>> 자주 묻는 질문
산술 부호화란 무엇인가요?
산술 부호화는 기호의 시퀀스를 하나의 분수 값으로 변환하는 엔트로피 부호화 방식입니다. 정수 비트만 사용하는 허프만 부호화와 달리, 산술 부호화는 기호 하나당 분수 비트를 사용할 수 있습니다.
허프만보다 왜 더 좋은가요?
산술 부호화는 압축률을 엔트로피 한계에 임의로 가깝게 만들 수 있는 반면, 허프만 부호화는 기호당 정수 비트로 제한됩니다. 확률 분포가 매우 치우친 경우 산술 부호화가 훨씬 더 효율적일 수 있습니다.
정밀도(precision) 파라미터는 무엇인가요?
정밀도는 내부 계산에 사용되는 비트 수를 제어합니다. 정밀도가 높을수록 더 긴 메시지를 인코딩할 수 있지만, 더 많은 메모리가 필요합니다. 짧은 텍스트에는 보통 16비트면 충분합니다.
산술 부호화는 어디에 사용되나요?
산술 부호화는 H.264/H.265 비디오, JPEG2000 이미지, ZIP의 DEFLATE64 모드와 같은 최신 압축 표준에서 사용됩니다. 과거에는 특허로 제한되었지만 주요 특허는 만료되었습니다.
// 계산 예시
| Step | Symbol | low | high |
|---|---|---|---|
| 0 | — | 0 | 1 |
| 1 | A | 0 | 0.5 |
| 2 | B | 0.25 | 0.375 |
| 3 | C | 0.34375 | 0.375 |
// 코드 예제
Model P(A)=0.5 P(B)=0.25 P(C)=0.25 -> A:[0,0.5) B:[0.5,0.75) C:[0.75,1)
Update width = high - low
high = low + width * cum_high(symbol)
low = low + width * cum_low(symbol)
Output any value in [0.34375, 0.375) e.g. 0.34375 = 0.01011b (5 bits = 1 + 2 + 2)
Entropy -log2 P(A) - log2 P(B) - log2 P(C) = 1 + 2 + 2 = 5 bits
>> 더 많은 질문
Q: 산술 부호화가 허프만보다 나은 경우가 많은 이유는?
A: 허프만은 각 기호에 정수 비트(최소 1)를 할당합니다. 산술 부호화는 메시지 전체를 [0, 1) 안의 하나의 분수로 부호화해 엔트로피에 가까워지며, 확률이 50%를 넘는 기호도 허프만에서는 1비트가 드는 문제를 개선합니다.
Q: ABC 구간 예시는 어떻게 동작하나요?
A: A=0.5, B=0.25, C=0.25일 때 기호마다 구간이 좁아집니다: [0,1) → [0,0.5) → [0.25, 0.375) → [0.34375, 0.375). 이 안의 수, 예를 들어 이진수 0.01011(=0.34375)이 "ABC"를 5비트, 즉 엔트로피 그대로 나타냅니다.
Q: 산술 부호화는 어디에 쓰이나요?
A: H.264/HEVC의 CABAC, JPEG 2000과 JBIG2의 MQ 코더, range coding(AV1)과 ANS(zstd, JPEG XL) 같은 변형에 쓰입니다. 초기 특허가 보급을 늦췄으나 지금은 대부분 만료되었습니다.