8.3 무손실 압축과 손실 압축의 분류 체계

1. 분류의 기본 기준

데이터 압축 기법은 복원의 정확성에 따라 무손실 압축(lossless compression)과 손실 압축(lossy compression)으로 분류된다. 이 분류는 정보 이론의 두 핵심 정리—무잡음 부호화 정리와 율-왜곡 정리—에 각각 대응한다.

2. 무손실 압축

2.1 정의와 조건

무손실 압축에서 부호화 함수 $E$ 와 복호화 함수 $D$ 는 모든 입력 $\mathbf{x}$ 에 대해 $D(E(\mathbf{x})) = \mathbf{x}$ 를 만족한다. 원본 데이터의 완벽한 복원이 보장되며, 단 하나의 비트도 손실되지 않는다.

2.2 이론적 한계

무손실 압축의 기호 당 최소 평균 비트 수는 정보원의 엔트로피 $H(X)$ 이다. 어떠한 무손실 압축 기법도 이 한계 이하로 압축할 수 없으며, 블록 부호화에 의해 이 한계에 임의로 가깝게 접근할 수 있다.

2.3 주요 기법

무손실 압축 기법은 다음으로 분류된다:

엔트로피 부호화(entropy coding): 기호의 확률 분포에 기반하여 부호어를 할당하는 방법이다. 허프만 부호화, 산술 부호화, ANS(Asymmetric Numeral Systems) 부호화가 대표적이다.

사전 기반 부호화(dictionary-based coding): 반복되는 패턴을 사전에 등록하고 참조하는 방법이다. 렘펠-지브(Lempel-Ziv) 계열 알고리즘(LZ77, LZ78, LZW)이 대표적이며, ZIP, GZIP, PNG 등의 실용적 압축 형식에서 사용된다.

예측 기반 부호화(predictive coding): 이전 데이터로부터 다음 데이터를 예측하고, 예측 오차(residual)만을 부호화하는 방법이다. PPM(Prediction by Partial Matching), 문맥 혼합(context mixing) 등이 이 범주에 속한다.

2.4 응용 영역

무손실 압축은 원본의 완벽한 복원이 필수인 영역에서 사용된다: 텍스트 문서, 소프트웨어 배포, 의료 영상, 과학 데이터, 금융 데이터 등이다.

3. 손실 압축

3.1 정의와 왜곡 측도

손실 압축에서 복원된 데이터 $\hat{\mathbf{x}} = D(E(\mathbf{x}))$ 는 원본 $\mathbf{x}$ 와 다를 수 있다. 왜곡(distortion)의 정도는 왜곡 측도(distortion measure) $d(\mathbf{x}, \hat{\mathbf{x}})$ 로 정량화된다. 대표적 왜곡 측도는 다음과 같다:

평균 제곱 오차(MSE): $d(\mathbf{x}, \hat{\mathbf{x}}) = (1/n)\sum_{i=1}^{n}(x_i - \hat{x}_i)^2$
해밍 왜곡(Hamming distortion): $d(\mathbf{x}, \hat{\mathbf{x}}) = (1/n)\sum_{i=1}^{n}\mathbf{1}(x_i \neq \hat{x}_i)$

3.2 이론적 한계

손실 압축의 한계는 율-왜곡 함수 $R(D)$ 에 의해 규정된다. 평균 왜곡이 $D$ 이하인 모든 부호화 기법 중 달성 가능한 최소 전송률이 $R(D)$ 이다. $R(D)$ 는 $D$ 에 대해 단조 감소하는 볼록 함수이다.

3.3 주요 기법

손실 압축은 일반적으로 변환(transform), 양자화(quantization), 엔트로피 부호화의 3단계로 구성된다:

변환 부호화(transform coding): 데이터를 에너지가 소수의 계수에 집중되는 변환 영역으로 변환한다. 이산 코사인 변환(DCT), 웨이블릿 변환(wavelet transform)이 대표적이다.

양자화(quantization): 연속 값 또는 세밀한 이산 값을 더 조잡한 이산 값으로 매핑한다. 스칼라 양자화(scalar quantization)와 벡터 양자화(vector quantization)로 구분된다. 양자화 단계에서 비가역적 정보 손실이 발생한다.

엔트로피 부호화: 양자화된 값에 무손실 엔트로피 부호화를 적용하여 최종 비트스트림을 생성한다.

3.4 응용 영역

손실 압축은 인간의 지각적 한계를 활용하여 더 높은 압축률을 달성한다: 정지 이미지(JPEG, WebP), 동영상(H.264, H.265, AV1), 음성 및 음악(MP3, AAC, Opus) 등이다.

4. 무손실과 손실의 경계

4.1 결합 기법

현실의 많은 압축 시스템은 무손실과 손실 기법을 결합한다. JPEG 압축에서 DCT와 양자화는 손실 단계이고, 양자화된 계수의 허프만 부호화는 무손실 단계이다. PNG는 예측 필터(무손실 전처리)와 DEFLATE(무손실 엔트로피 부호화)를 결합한 순수 무손실 형식이다.

4.2 정보론적 관점에서의 통합

무손실 압축과 손실 압축은 율-왜곡 이론의 틀에서 통합적으로 이해된다. 무손실 압축은 $D = 0$ 인 특수한 경우이며, $R(0) = H(X)$ 이다. 손실 압축은 $D > 0$ 을 허용하여 $R(D) < H(X)$ 의 더 높은 압축률을 달성한다. 이 통합적 관점에서, 무손실과 손실의 차이는 허용 왜곡 수준의 차이일 뿐, 이론적 프레임워크는 동일하다.

5. 결론

무손실 압축과 손실 압축의 분류는 데이터 압축의 가장 기본적인 구분이다. 무손실 압축은 엔트로피에 의해, 손실 압축은 율-왜곡 함수에 의해 각각의 이론적 한계가 규정된다. 응용의 요구 사항—원본 복원의 필요성, 허용 가능한 왜곡 수준, 목표 압축률—에 따라 적절한 범주의 기법이 선택되며, 현대의 압축 시스템은 흔히 두 범주의 기법을 결합하여 사용한다.