무손실 압축과 손실 압축의 원리 — 허프만 코딩과 RLE로 보는 압축 알고리즘
허프만 코딩·RLE 등 엔트로피 부호화 알고리즘의 동작 원리와 무손실·손실 압축의 차이를 실무 적용 절차 중심으로 정리한다.
2026-08-13 · 최초 발행 2025-11-26
정의 및 개념
데이터 압축은 원본 정보에 담긴 통계적 중복을 제거해 더 적은 비트로 표현하는 과정이다. 목표는 입력 데이터의 엔트로피(정보량) 하한에 최대한 가까운 부호화다.
압축은 크게 두 갈래로 나뉜다.
- 무손실(Lossless): 복원 시 원본과 완전히 일치한다. 텍스트, 소스코드, 로그, 데이터베이스 덤프처럼 한 비트라도 틀리면 안 되는 데이터에 필수다.
- 손실(Lossy): 지각적으로 중요하지 않은 성분을 제거한다. 이미지·오디오·비디오 등 멀티미디어에 적합하다.
두 갈래 모두 출발점은 같다. 데이터의 확률 분포를 추정해 빈도 높은 기호에는 짧은 코드를, 빈도 낮은 기호에는 긴 코드를 할당함으로써 평균 부호 길이를 최소화하는 소스 모델링과 엔트로피 부호화다.
엔트로피 부호화: 허프만 코딩
허프만 코딩은 기호 빈도를 추정한 뒤 최소 힙으로 이진 트리를 구성하고, 각 잎 노드까지의 경로를 0/1 코드로 매핑하는 방식이다. 이때 어떤 코드도 다른 코드의 접두사가 되지 않는 접두사(prefix)-무충돌 특성이 보장돼 디코더가 별도 구분자 없이 스트림을 정확히 분리할 수 있다.
구현이 쉽고 속도가 우수하지만, 기호 확률이 2의 거듭제곱과 멀어질수록 산술 부호화 대비 압축률이 떨어질 수 있다.
절차는 입력(기호 시퀀스, 빈도 테이블) → 처리(트리 생성 → 코드북 생성 → 비트스트림 생성) → 출력(헤더의 코드북 + 페이로드)으로 이어진다. 헤더(코드북)가 손상되면 스트림 전체를 복호할 수 없으므로, 코드북 중복 저장이나 CRC 보호가 필요하다.
반복 길이 부호화: RLE
RLE(Run-Length Encoding)는 동일 기호가 연속되는 구간을 (값, 길이) 쌍으로 치환한다. 예를 들어 AAAAB는 (A,4)(B,1)로 바뀐다.
긴 반복 구간에는 O(n) 속도로 매우 효과적이지만, 반대로 잡음성(noisy) 데이터에서는 토큰 오버헤드 때문에 원본보다 커지는 역효과가 날 수 있다. 길이 값이 손상되면 이후 스트림 전체의 동기화가 붕괴하므로, 블록 단위 체크섬이나 리셋 포인트를 두는 것이 안전하다.
손실 압축의 핵심: 변환과 양자화
손실 압축은 DCT나 웨이블릿 같은 변환으로 에너지를 저주파/고주파 성분으로 분리해 지각 중요도를 반영하는 데서 시작한다. 이어지는 양자화 단계가 QP(양자화 파라미터)나 λ로 비트 예산 안에서 품질을 조절하며, 이때 비가역 손실이 발생한다. 양자화 이후에도 잔여 중복이 남아 있어 후단에서 허프만 등 엔트로피 부호화를 한 번 더 거친다.
포맷·컨테이너와 무결성
실제 포맷들은 이 요소들을 조합해서 만들어진다. PNG는 DEFLATE(LZ77+허프만), JPEG는 DCT+양자화+허프만, FLAC는 LPC+엔트로피 부호화, H.264/AV1은 더 복합적인 파이프라인을 쓴다.
전송·저장 과정에서는 헤더 보호, CRC/Adler-32 같은 체크섬, 세그먼트화, 동기화 마커 삽입이 필요하고, 특히 스트리밍이나 무선 환경에서는 재전송 전략을 함께 설계해야 한다.
무손실 대 손실, 핵심 지표 비교
| 구분 | 성능(속도) | 압축률 | 일관성(원복 정확도) | 안정성(오류 영향) | 운영 편의 |
|---|---|---|---|---|---|
| 무손실(허프만/RLE/DEFLATE) | 보통~빠름, CPU 효율 우수 | 1.5~4배(데이터 의존), RLE는 반복 데이터에서 매우 큼 | 완전 복원 | 헤더/코드북 손상 시 블록 단위 영향, 동기화 비교적 용이 | 백업/로그에 적합, 규제 준수 용이 |
| 손실(JPEG/MP3/H.264 등) | 보통, 복잡도 높음(변환/양자화) | 5~20배+, 시각·청각 마스킹 활용 | 근사 복원, 지각 품질 중심 | 비트 오류 시 아티팩트 전파 가능, 오류 은닉 필요 | 스트리밍/미디어에 적합, 품질-비트율 튜닝 필요 |
도메인별 적용
- 텍스트/로그/데이터베이스 백업: 무손실 우선. DEFLATE/Zstd에 사전(dictionary) 최적화를 더한다. 공백·패딩·0-필드가 많은 CSV/JSON은 RLE로 블록을 사전 처리하면 효과가 있다.
- 이미지/스캔: 이진 스캔·팩스는 RLE 또는 Modified Huffman(Group 3/4)을 쓴다. 사진은 JPEG(DCT+양자화+허프만), 스크린샷·아이콘은 PNG(DEFLATE)가 적합하다.
- 오디오/비디오/스트리밍: 오디오는 FLAC(무손실), AAC/MP3(손실+허프만). 비디오는 H.264/HEVC/AV1처럼 변환+양자화+엔트로피 부호화를 결합한 코덱을 쓴다.
실무 적용 절차와 체감 효과
먼저 원복 정확도, 목표 압축률, 지연 한도, CPU/메모리 예산부터 정의한다. 그다음 데이터 특성에 맞춰 알고리즘을 고른다. 반복 패턴이 지배적이면 RLE 또는 RLE 프리패스+허프만/DEFLATE, 일반 텍스트·로그는 Zstd/DEFLATE(허프만+LZ)를 기본값으로 사전 학습을 곁들이고, 멀티미디어는 JPEG/PNG/FLAC/AAC 등 표준 포맷을 채택한다.
체감 효과는 데이터 유형에 따라 크게 갈린다. 일일 로그 2TB를 Zstd 평균 3:1로 압축하면 2TB / 3 ≈ 0.67TB/일로 줄어 월 60TB 수준을 절감할 수 있다. 100GB 파일을 1Gbps 링크로 전송할 때 무손실 2:1을 적용하면 원본 전송 시간 약 800초(100GB × 8 / 1Gbps)가 압축 후 약 400초(50GB × 8 / 1Gbps)로, 약 400초가 줄어든다. 멀티미디어에서는 1080p 비디오 8Mbps를 H.264로 튜닝하면 SSIM 0.95 이상을 유지하면서 4Mbps까지 낮출 수 있어 동일 CDN 비용을 절반 수준으로 줄이는 효과가 난다.
파라미터 튜닝 단계에서는 블록 크기를 64KB~1MB 범위에서 CPU-압축률 균형을 보며 조정하고, 손실 압축은 QP·품질 인덱스를 A/B 테스트하며 PSNR/SSIM 기준으로 검증한다. 운영·배포 단계에서는 컨테이너·헤더 보호, CRC 삽입, 인덱스와 동기화 마커 구성이 필요하고, 스트리밍이라면 슬라이스·타일링, 키프레임 주기 조정, 전방 오류 은닉을 함께 도입한다.
운영 모범사례와 트레이드오프
디스크나 네트워크가 병목이면 더 강한 압축이 유리하고, CPU가 병목이면 경량 코덱이나 병렬화가 낫다. 병렬화는 청크 분할, 스레드·코어 고정, NUMA 최적화로 처리하되 청크 경계에서 압축률이 떨어질 수 있다는 점을 감안해야 한다.
RLE는 반복이 희소한 데이터에서 오히려 팽창할 수 있으므로 임계(run threshold)와 하이브리드 토큰 설계로 방지한다. 허프만은 코드북 이중화, 소블록 단위의 헤더+페이로드 CRC, 손상 블록 스킵 전략으로 헤더를 보호한다. 재현성과 감사가 중요한 환경이라면 무손실 포맷을 강제하고 압축기 버전을 고정하며 코드북·사전 아티팩트를 저장해 둔다.