엔트로피 부호화(Entropy coding)는 정보 이론과 데이터 압축에서 무손실 압축을 위해 사용되는 부호화 기법의 총칭이다. 데이터에 나타나는 기호(심볼)들의 출현 확률 분포를 이용하여, 출현 빈도가 높은 기호에는 짧은 부호어를, 낮은 기호에는 긴 부호어를 할당함으로써 평균 부호 길이를 최소화한다. 이는 클로드 섀넌이 제시한 엔트로피 개념에 기반하며, 이론적으로 주어진 확률 분포에 대한 무손실 압축의 한계(엔트로피)에 근접하는 것을 목표로 한다.
주요 특징 및 원리는 다음과 같다.
- 통계적 압축: 데이터의 통계적 특성(기호별 확률)을 활용하여 중복성을 제거한다.
- 가변 길이 부호(Variable-Length Code): 고정 길이 부호(예: ASCII)와 달리 기호마다 부호어의 길이가 다르다.
- 접두 부호(Prefix Code) 만족: 대부분의 엔트로피 부호화 방식은 어떤 부호어도 다른 부호어의 접두사가 되지 않도록 설계되어, 부호어 간의 구분자 없이 연속된 비트 스트림을 유일하게 복호화할 수 있다.
대표적인 알고리즘은 다음과 같다.
- 허프만 부호화(Huffman Coding): 기호의 확률에 따라 이진 트리를 구성하여 최적의 접두 부호를 생성한다. 구현이 간단하고 빠르지만, 기호별 확률이 2의 거듭제곱 꼴이 아닐 때 엔트로피와의 격차가 발생할 수 있다.
- 산술 부호화(Arithmetic Coding): 메시지 전체를 하나의 부호어(실수 구간)로 매핑한다. 허프만 부호화보다 엔트로피 한계에 더 근접할 수 있으며, 적응형 확률 모델링에 유리하다. 과거에는 특허 문제로 활용에 제약이 있었으나, 주요 특허가 만료되어 현재는 널리 사용된다.
- 비대칭 숫자 시스템(Asymmetric Numeral Systems, ANS): 산술 부호화의 압축 효율과 허프만 부호화에 가까운 처리 속도를 동시에 달성하기 위해 개발된 비교적 최신 기법이다. 현재 Zstandard(zstd), LZFSE 등 현대 압축 라이브러리에서 주로 채택되고 있다.
엔트로피 부호화는 단독으로 사용되기도 하지만, LZ77, LZ78, BWT(버로우즈-휠러 변환) 등 사전 기반 압축이나 변환 기법과 결합하여(예: Deflate, LZMA, bzip2, Zstandard) 실제 파일 압축 포맷, 이미지/비디오 코덱(JPEG, MPEG, HEVC, AV1), 통신 프로토콜 등 광범위한 분야에서 핵심 구성 요소로 활용된다.
