엔트로피 부호화

소프트웨어 통계 마지막 수정: 2026-09-01 04:14:52

1. 개요[편집]

엔트로피 부호화 Entropy Coding
위치	압축 파이프라인의 마지막 단계
이론적 하한	기호당 $H(X)$ 비트 (섀넌 소스 부호화 정리)
3대 엔진	허프만(1952) · 산술부호화(1976) · ANS(2009~2014)
손실 여부	완전 무손실. 버리는 것은 앞단(양자화)의 일
실무 채택	DEFLATE·JPEG=허프만, HEVC=CABAC, zstd·JPEG XL=ANS
성능 축	압축률 ↔ 기호당 처리 속도, 이 둘의 줄다리기가 역사 전부

자주 나오는 놈에게 짧은 이름을 준다. 압축의 마지막 한 방은 이 한 문장이 전부다.

엔트로피 부호화(entropy coding)는 기호의 확률분포를 이용해 자주 등장하는 기호에 짧은 부호어를, 드문 기호에 긴 부호어를 배정함으로써 평균 부호 길이를 그 분포의 엔트로피 근처까지 끌어내리는 무손실 부호화 기법이다. 이미지 압축이든 동영상 압축이든 범용 파일 압축이든, 파이프라인의 맨 끝에는 거의 예외 없이 이놈이 앉아 있다.

여기서 반드시 붙잡아야 할 구분이 하나 있다. 엔트로피 부호화는 정보를 하나도 버리지 않는다. 버리는 일은 앞단의 양자화가 하고, 엔트로피 부호기는 앞단이 만들어 준 확률분포가 얼마나 치우쳐 있는지를 남김없이 현금화할 뿐이다. 그래서 “우리 코덱이 압축률이 좋다”는 말의 90%는 사실 앞단(예측·변환·문맥 모형)이 잘했다는 뜻이고, 엔트로피 부호기가 기여하는 몫은 “모형이 준 확률을 몇 % 손해 보고 비트로 바꿨는가”라는 마진 싸움이다. 이 마진이 20세기에는 5~10%였고, 21세기에는 1% 아래로 내려갔다.

2. 하한 — 섀넌 소스 부호화 정리[편집]

기호 집합 $\mathcal{X}$ 위의 확률분포 $p$ 에서 기호가 독립적으로 나온다고 하자. 각 기호 $x$ 에 길이 $\ell(x)$ 비트의 부호어를 붙이는 유일 복호 가능(uniquely decodable) 부호라면, 크라프트-맥밀런 부등식

\sum_{x \in \mathcal{X}} 2^{-\ell(x)} \;\le\; 1

을 만족해야 한다.¹ 이 제약 아래 평균 길이 $L = \sum_x p(x)\ell(x)$ 를 최소화하면, 젠센 부등식 한 줄로

L \;\ge\; H(X) \;=\; -\sum_{x} p(x)\log_2 p(x)

가 나온다. 이것이 섀넌 소스 부호화 정리의 부호별 형태다. 등호는 모든 $p(x)$ 가 2의 음의 거듭제곱, 즉 $\ell(x) = -\log_2 p(x)$ 가 정수일 때만 성립한다. 반대 방향도 성립해서, 기호를 $n$ 개씩 묶어 블록으로 부호화하면 기호당 평균 길이를 $H(X) + 1/n$ 이하로 만들 수 있다. 즉 엔트로피는 넘을 수 없는 바닥이자, 원하는 만큼 가까이 갈 수 있는 바닥이다.

주의할 것은 $H(X)$ 가 “데이터의 성질”이 아니라 **“내가 가정한 모형 $p$ 의 성질”**이라는 점이다. 실제 분포가 $q$ 인데 $p$ 라고 믿고 부호화하면 평균 길이는 $H(q) + D_{\mathrm{KL}}(q\,\|\,p)$ 가 되고, 초과분이 정확히 쿨백-라이블러 발산이다. 모형이 틀린 대가가 비트로 청구되는 셈. 그래서 압축 경쟁은 사실상 모형링 경쟁이다.

3. 허프만 — 정수 비트의 저주[편집]

허프만 부호는 1952년 데이비드 허프만이 MIT 대학원 수업 기말 과제로 만든 물건이다.² 알고리즘은 민망할 정도로 단순하다. 확률이 가장 작은 두 기호를 우선순위 큐에서 꺼내 합쳐 새 노드를 만들고, 하나가 남을 때까지 반복한다. $O(m \log m)$ 에 끝나고, 결과는 주어진 확률분포에 대해 최적인 접두 부호임이 증명된다. 그리디 알고리즘이 최적해를 주는 교과서적 사례이기도 하다.

문제는 “접두 부호 중 최적”이라는 단서에 있다. 접두 부호는 기호마다 정수 개의 비트를 쓸 수밖에 없다. 확률이 0.9인 기호의 이상적 길이는 $-\log_2 0.9 = 0.152$ 비트인데, 허프만은 1비트를 준다. 6배 넘게 낭비하는 것이다. 일반적 상한은

H(X) \;\le\; L_{\text{Huffman}} \;<\; H(X) + 1

이고, 갤러거(1978)의 더 날카로운 상한은 최대 확률 $p_{\max}$ 에 대해 $L - H < p_{\max} + 0.086$ 이다. 즉 분포가 평평하면 허프만은 거의 최적이고, 한 기호가 지배적이면 처참하다. 이진 결정을 잔뜩 쏟아내는 현대 비디오 코덱이 허프만을 못 쓰는 이유가 정확히 이것이다 — 확률 0.98짜리 “이 계수는 0이다” 신호에 1비트씩 물리면 게임이 안 된다.

우회로가 없지는 않다. 기호를 여러 개 묶어 확장 알파벳을 만들면(블록 허프만) 낭비가 $1/n$ 로 줄지만 표 크기가 지수로 커진다. 런길이 부호화로 0의 연속을 미리 접어 두는 것도(JPEG의 방식) 사실상 같은 트릭이다. 실무에서 허프만이 여전히 살아 있는 이유는 속도 하나다. 복호가 테이블 조회 한 번이고, 정규 허프만(canonical Huffman)을 쓰면 부호표를 길이 배열만으로 전송할 수 있다.

4. 산술 부호화 — 기호당 분수 비트[편집]

산술 부호화(arithmetic coding)는 발상을 통째로 바꾼다. 메시지 전체를 $[0,1)$ 구간 안의 실수 하나로 본다. 기호가 하나 들어올 때마다 현재 구간을 그 기호의 확률만큼의 부분구간으로 좁히고, 마지막에 남은 구간 안의 아무 수나 이진수로 적어 보낸다. 길이 $n$ 메시지의 최종 구간 폭은 $\prod_i p(x_i)$ 이므로, 필요한 비트 수는

\Bigl\lceil -\log_2 \textstyle\prod_i p(x_i) \Bigr\rceil + 1 \;=\; \sum_i \bigl(-\log_2 p(x_i)\bigr) + O(1)

이다. 오버헤드가 기호당 1비트가 아니라 메시지 전체에 2비트 남짓으로 바뀐다. 기호당으로 환산하면 사실상 0이고, 확률 0.98짜리 기호는 진짜로 0.029비트를 먹는다.

물론 무한 정밀도 실수는 못 쓴다. 실제 구현은 정수 레지스터(보통 32비트) 위에서 구간의 하한 low와 폭 range를 유지하고, 폭이 임계값 아래로 떨어지면 상위 바이트를 뱉으며 재정규화(renormalization)한다. 상위 비트가 확정되지 않고 0111…/1000… 경계에 끼는 자리올림 전파(carry propagation)를 어떻게 처리하느냐가 구현의 지저분한 절반이다.

정리하자면 이 계보는 이렇다.

파스코·리사넨(1976) — 산술 부호화의 독립적 제안. 리사넨·랭던(1979)이 IBM에서 실용적 정수 구현으로 다듬는다.
위튼·닐·클리어리(1987) — CACM 에 C 코드를 통째로 실은 논문. 이걸로 산술 부호화가 대중화됐다.
레인지 코더(Martin, 1979) — 수학적으로 산술 부호화와 같지만, 비트 대신 바이트 단위로 재정규화해 나눗셈 횟수를 줄인 변종. 특허 지형이 비교적 깨끗하다는 실무적 이유로 7-Zip·LZMA 계열이 이쪽을 택했다.
이진 산술 부호화 — 알파벳을 $\{0,1\}$ 로 고정하면 구간 분할이 곱셈 한 번, 심지어 표 조회로 대체된다. CABAC·JPEG2000의 MQ 코더가 이 길이다.

산술 부호화가 20년 가까이 발이 묶였던 이유는 순수하게 특허였다. IBM의 QM 코더 관련 특허 때문에 JPEG 표준의 산술 모드는 규격에만 존재하고 아무도 안 썼고, 그 사이 세상은 허프만으로 버텼다.³

5. ANS — 허프만 속도로 산술부호화 압축률[편집]

비대칭 수 체계(Asymmetric Numeral Systems, ANS)는 야로스와프 두다가 2009년부터 다듬어 2013~2014년 논문으로 정리한 방식이다.⁴ 아이디어는 “상태 하나에 정보를 눌러 담는다”로 요약된다. 자연수 상태 $x$ 를 유지하다가 기호 $s$ 를 부호화할 때 대략

x \;\longmapsto\; C(s, x) \;\approx\; \frac{x}{p(s)}

가 되도록 상태를 키운다. 상태의 정보량은 $\log_2 x$ 이므로 한 기호가 $-\log_2 p(s)$ 비트만큼 상태를 불린 셈이고, 이게 정확히 이상적 부호 길이다. 상태가 레지스터를 넘치기 직전에 하위 비트를 뱉어 재정규화한다. 산술 부호화가 구간의 양 끝(low, range)을 관리하는 데 비해 ANS는 상태 하나만 관리하므로 연산이 훨씬 가볍다.

두 갈래가 실무를 지배한다.

tANS / FSE(table ANS, Finite State Entropy) — 상태 전이를 통째로 표로 구워 둔다. 부호화·복호화가 기호당 테이블 조회 한 번, 즉 허프만과 같은 비용인데 분수 비트를 쓴다. Zstandard와 애플의 LZFSE가 이걸 쓴다.
rANS(range ANS) — 곱셈·나눗셈 기반이라 표가 필요 없고 확률을 동적으로 바꾸기 쉽다. 인터리빙으로 SIMD 병렬화가 가능해 처리량이 매우 높다. JPEG XL, 유전체 포맷 CRAM 등이 채택했다.

ANS에는 산술 부호화에 없는 특징이 하나 있다. 복호 순서가 부호화 순서의 역순이라는 것(LIFO). 인코더가 데이터를 거꾸로 훑거나 버퍼를 뒤집어야 해서 스트리밍 설계가 조금 성가시다. 그 대가로 얻는 속도가 워낙 커서, 2015년 이후 새로 설계된 무손실 코덱은 사실상 전부 ANS 계열이다.

6. 문맥 모형 — 압축률의 진짜 출처[편집]

지금까지는 확률 $p$ 가 하늘에서 떨어진다고 가정했다. 현실에서 그 $p$ 를 만드는 게 모형이고, 압축률의 대부분이 여기서 결정된다.

적응형 모형. 부호기와 복호기가 똑같은 규칙으로 통계를 갱신하면 부호표를 전송할 필요가 없다. 지금까지 본 기호의 빈도로 다음 확률을 추정하고, 갱신은 부호화 직후에 한다(복호기가 같은 시점에 같은 정보를 갖도록). 적응형 허프만(FGK·비터 알고리즘)도 있지만 트리 재구성 비용 탓에, 적응은 산술/ANS 쪽에서 훨씬 자연스럽다.
문맥 모형. 직전 $k$ 개 기호를 조건으로 분포를 따로 둔다. 조건부 엔트로피 $H(X_i \mid X_{i-1},\dots)$ 는 무조건부 엔트로피보다 작으므로 압축률이 개선되고, 이건 은닉 마르코프 모형류의 문맥 확장과 같은 발상이다. 문맥을 늘릴수록 좋지만 문맥 희석(context dilution) — 문맥마다 표본이 부족해 추정이 나빠지는 현상 — 이 곧 발목을 잡는다. PPM 계열은 긴 문맥부터 시도하고 실패하면 escape 기호로 짧은 문맥으로 후퇴하는 방식으로 이를 다룬다.
CABAC. H.264/AVC와 HEVC의 표준 엔트로피 부호기이며, 세 부품으로 이루어진다. 이진화(syntax element를 절단 단항·Exp-Golomb 등으로 비트열로 변환) → 문맥 모형화(각 빈(bin)마다 이웃 블록 정보로 문맥 인덱스를 고르고, 그 문맥의 확률 상태를 유지) → 이진 산술 부호화(곱셈 없는 표 기반 구간 분할 + 재정규화). 확률 갱신이 상태 기계로 되어 있어 부동소수점이 전혀 등장하지 않고, 그래서 비트 단위로 재현 가능하다. H.264에서 CAVLC 대비 대략 10~15% 비트 절감이 보고되었고, HEVC는 아예 CABAC만 남겼다.

7. 앞단과의 역할 분담[편집]

엔트로피 부호기 혼자서는 아무것도 못 한다. 앞단이 하는 일은 딱 하나 — 분포를 뾰족하게 만드는 것이다.

예측/변환. 이웃 화소값 자체는 0~255에 넓게 퍼져 엔트로피가 7비트 근처지만, 예측 잔차는 0 주변에 몰린 라플라스 분포가 되어 엔트로피가 절반 이하로 떨어진다. 이산 코사인 변환이나 웨이블릿 변환은 같은 일을 주파수 영역에서 한다 — 에너지를 소수의 계수에 몰아넣고 나머지를 0 근처로 보낸다. 여기까지는 전부 무손실이며 비트를 줄이지도 않는다. 줄어드는 것은 엔트로피뿐이다.
양자화. 정보를 실제로 버리는 유일한 단계. 계수를 눈금에 맞춰 반올림하면 대부분이 정확히 0이 되고, 분포가 극단적으로 뾰족해진다. 얼마나 버릴지의 최적 배분은 율-왜곡 이론이 다룬다.
엔트로피 부호화. 뾰족해진 분포를 비트로 환전한다. 여기서 손실은 0이다.

이 3단 구조를 이해하면 “왜 이미 압축된 JPEG을 zip으로 다시 묶어도 안 줄어드는가”가 자명해진다. 엔트로피 부호기가 이미 분포를 다 짜냈으므로 출력은 거의 균등난수처럼 보이고, 남은 여지가 없다. 난수 생성기 출력이 압축되지 않는 것과 정확히 같은 이유다.

8. 구현이 아픈 곳[편집]

교과서의 세 줄과 돌아가는 코드 사이에는 늘 지저분한 골짜기가 있다.

부호표를 어떻게 보낼 것인가. 비적응형 허프만은 부호표 자체를 헤더에 실어야 하는데, 알파벳이 256개면 이것만으로 수백 바이트다. 짧은 파일에서는 배보다 배꼽이 크다. 해법이 정규 허프만(canonical Huffman)으로, “같은 길이의 부호어는 사전순으로 연속 배정”이라는 규칙을 강제하면 부호어 길이 배열만 보내도 표가 유일하게 복원된다. 길이 배열은 또 그 자체로 압축할 수 있어서(DEFLATE는 길이 배열을 다시 허프만으로 압축한다), 실제 오버헤드가 수십 바이트로 줄어든다.

확률을 정수로 눌러 담기. 산술·레인지·ANS 전부 확률을 $2^{-b}$ 단위의 정수 빈도로 근사한다( $b = 12$ 정도가 흔하다). 이때 합이 정확히 $2^b$ 가 되도록 정규화해야 하고, 반올림 때문에 빈도가 0이 되는 기호가 생기면 그 기호가 등장하는 순간 부호기가 폭발한다. 그래서 “모든 기호에 최소 1을 보장하고 남은 몫을 큰 기호에서 깎는” 처리가 필수다. 확률 양자화로 잃는 압축률은 보통 0.1% 미만이라 아무도 신경 쓰지 않지만, 0 빈도 사고는 매년 어딘가에서 반복된다.

자리올림과 재정규화. 산술 부호기의 구간이 0.0111…과 0.1000… 사이에 걸치면 상위 비트가 확정되지 않는다. 이걸 대기 비트(pending bits) 카운터로 미뤄 두거나, 아예 구간을 강제로 좁혀(underflow 방지) 문제를 없애 버린다. 레인지 코더가 바이트 단위 출력을 택한 것도 이 처리를 단순화하려는 목적이 크다.

결정론이 목숨이다. 적응형 모형은 부호기와 복호기가 완전히 같은 순서로 같은 갱신을 해야 한다. 부동소수점을 확률 갱신에 쓰면 컴파일러 최적화나 FMA 유무에 따라 마지막 비트가 달라지고, 그 순간 복호가 통째로 깨진다. 그래서 CABAC을 비롯한 표준 코덱의 확률 갱신은 예외 없이 정수 상태 기계로 규정되어 있다. 부동소수점 연산의 재현성 문제가 압축 표준을 어떻게 설계하게 만들었는지 보여주는 사례다.

병렬화. 엔트로피 부호화는 본질적으로 직렬이다 — 다음 기호의 부호가 지금까지의 상태에 의존한다. 처방은 두 가지로, 데이터를 독립 청크로 잘라 스레드에 뿌리거나(경계에서 압축률을 조금 손해 본다), 상태를 여러 개 두고 인터리빙한다. rANS가 각광받는 큰 이유가 후자다 — 상태 8개를 SIMD 레인에 하나씩 얹으면 한 명령으로 8기호를 처리할 수 있다. 허프만도 비슷하게 여러 비트스트림을 인터리빙하는 기법이 zstd·Brotli에 들어가 있다.

9. 시뮬레이션 데이터는 왜 잘 안 줄어드나[편집]

해석 결과를 gzip으로 묶어 봤는데 30%밖에 안 줄어든 경험이 있다면, 그건 도구 탓이 아니다. 배정밀도 부동소수점의 가수부 하위 비트는 사실상 난수이기 때문이다. 물리적으로 의미 있는 유효숫자는 서너 자리인데 저장은 15~16자리로 하니, 나머지가 전부 압축 불가능한 잡음으로 들어앉는다. 엔트로피 부호기 입장에서는 균등분포를 만난 셈이라 할 일이 없다.

그래서 과학 데이터 압축은 다른 길을 간다.

무손실. 이웃 격자점과의 예측(로렌초 예측기 등)을 부동소수점 표현 위에서 수행하고, 잔차의 지수부·부호부만 엔트로피 부호화한다. 가수부는 포기한다. FPZIP 계열이 이 방식이고, 현실적인 압축률은 1.5~2배 정도다.
오차 한계 손실. 사용자가 절대·상대 오차 한계를 주면 그 안에서 최대한 버린다. ZFP·SZ·MGARD가 여기 속하며, 오차 한계를 $10^{-6}$ 정도로 잡으면 10~30배가 나온다. 여기서도 마지막 단계는 엔트로피 부호화다 — 양자화된 계수를 산술 부호기나 ANS로 넘긴다.
정밀도를 애초에 낮추기. 저장용으로 단정밀도나 반정밀도로 캐스팅하는 것이 사실 가장 효과적인 “압축”인 경우가 많다. 혼합 정밀도 논의가 저장 쪽으로 확장된 형태.

HDF5·netCDF의 필터 체인(shuffle → deflate/zstd)이 하는 일도 결국 같은 발상이다. shuffle 필터는 배열의 모든 값에서 첫 바이트끼리, 둘째 바이트끼리 모아 재배치하는데, 이렇게 하면 비슷한 크기의 값들의 지수부 바이트가 한곳에 모여 반복 패턴이 생기고 뒤따르는 엔트로피 부호기가 일할 거리를 얻는다. 앞단이 분포를 뾰족하게 만들어야 뒷단이 산다는 원칙의 가장 저렴한 구현이다.

10. 어디에 무엇이 쓰이나[편집]

시스템	앞단	엔트로피 부호기
DEFLATE (PNG, gzip, zip)	LZ77 사전 매칭	정규 허프만(고정/동적 표)
JPEG (baseline)	DCT + 양자화 + 지그재그 런길이	허프만 (산술 모드는 사문화)
JPEG2000	웨이블릿 + EBCOT 비트평면	문맥 기반 이진 산술(MQ 코더)
H.264 / HEVC	인트라·인터 예측 + 변환 + 양자화	CABAC (H.264는 CAVLC 선택 가능)
AV1	예측 + 변환 + 양자화	다심볼 레인지 코더
bzip2	BWT + MTF + RLE	허프만(다중 표 전환)
LZMA / 7-Zip	LZ77 대형 사전	문맥 기반 레인지 코더
Zstandard	LZ77	리터럴은 허프만, 시퀀스는 FSE(tANS)
Brotli	LZ77 + 정적 사전	문맥 모형 + 허프만
JPEG XL	변조 DCT / 무손실 모드	rANS
FLAC, JPEG-LS	선형 예측 / MED 예측	골룸-라이스 부호

골룸-라이스 부호가 표에 끼어 있는 게 눈에 띌 텐데, 이건 기하분포에 대한 최적 접두 부호를 파라미터 하나로 즉석에서 만들어 내는 특수 케이스다. 예측 잔차는 대체로 기하/라플라스 분포이므로, 표도 산술 연산도 없이 시프트와 비교만으로 거의 최적에 도달한다. 하드웨어와 임베디드가 사랑하는 이유.

11. 관련 문서[편집]

크라프트 부등식은 원래 접두 부호에 대해 증명됐고(Kraft, 1949), 맥밀런(1956)이 “유일 복호 가능하기만 하면 접두 부호가 아니어도 같은 부등식이 성립한다”를 보였다. 함의가 꽤 잔인하다 — 접두 부호를 버리고 뭔가 영리한 짓을 해도 길이 측면에서는 얻을 게 하나도 없다는 뜻이다. 접두 부호가 표준이 된 데는 이 정리 지분이 크다. ↩
담당 교수 로버트 파노가 “최적 부호를 증명하거나 기말고사를 보거나 고르라”고 했고, 허프만은 몇 달을 헤매다 포기 직전에 아이디어를 떠올렸다고 회고한다. 참고로 파노 본인과 섀넌이 이미 만들어 둔 섀넌-파노 부호가 있었는데, 그건 위에서 아래로 쪼개는 방식이라 최적이 아니었다. 학생이 지도교수 방법을 갈아엎은 사례. ↩
그 20년 동안 “산술 부호화는 느리다”는 통념이 굳었는데, 사실 느린 건 곱셈·나눗셈이 비쌌던 시대의 이야기였다. 특허가 만료되고 나서 재평가해 보니 실제 병목은 대개 문맥 모형 쪽이었다. 기술사에서 특허가 통념까지 왜곡한 몇 안 되는 사례. ↩
Duda, J. (2013/2014). “Asymmetric numeral systems”. arXiv. 논문 제목의 부제가 대놓고 “허프만의 속도와 산술부호화의 압축률을 결합한 엔트로피 부호화”인데, 보통 이런 제목은 과장이지만 이번엔 진짜였다. 두다는 특허를 내지 않고 공개해 버렸고, 나중에 구글이 관련 특허를 출원하자 직접 이의를 제기해 무산시킨 일화로도 유명하다. ↩