✍️ 필사 모드: 압축 알고리즘 Deep Dive — LZ77, Huffman, Arithmetic, ANS, Zstandard, Brotli 완전 정복 (2025)

TL;DR

• 무손실 압축은 거의 항상 두 단계의 조합: (1) Dictionary 기반 중복 제거 (LZ77 계열 — 반복 바이트를 back-reference로 치환), (2) Entropy coding (Huffman/Arithmetic/ANS — 흔한 심볼에 짧은 코드).
• LZ77 (1977): 슬라이딩 윈도우에서 반복을 찾아 (offset, length, next_char) 출력. 모든 modern compressor의 뿌리.
• Huffman coding: 빈도 기반 prefix-free 코드. DEFLATE/gzip의 entropy 단계.
• Arithmetic coding: Huffman보다 좋은 비율이지만 느림. 30년간 특허 + 성능 문제로 한정적 사용.
• ANS (Asymmetric Numeral Systems), Jarek Duda 2009: Arithmetic 품질 + Huffman 속도. Zstd, LZFSE, AV1이 사용. 최근 10년의 hidden 혁명.
• DEFLATE (1993, RFC 1951): LZ77 + Huffman. gzip, PNG, ZIP의 기본.
• LZ4 (2011): 압축 비율 희생, 극한 속도 (GB/s). Snappy와 경쟁, 현대 시스템(RocksDB, LZ4-HC)에 내장.
• Zstandard (2016, Yann Collet): LZ77 + FSE(ANS). gzip보다 3배 빠르고 비율 좋음. Dictionary training으로 작은 메시지도 효율적 압축.
• Brotli (2015, Google): Zstd와 유사 경쟁자. 웹 트래픽 최적화, 정적 dictionary 내장.
• 실무 선택: 속도 → LZ4, 범용 → Zstd, 웹 정적 콘텐츠 → Brotli, 레거시 → gzip, 작은 메시지 많음 → Zstd dictionary.

1. 압축의 기본

1.1 왜 압축하는가

디스크: 스토리지 비용 절감. 네트워크: 대역폭 절감, 레이턴시 감소. 메모리: RAM 효율 증가. 백업/아카이브: 장기 보관.

2025년 데이터가 폭증하면서 압축의 중요성은 오히려 증가. CPU는 남지만 I/O와 네트워크가 병목.

1.2 Lossless vs Lossy

Lossless (이 글의 주제):

• 원본 완전 복원.
• 텍스트, 코드, DB, 실행 파일.
• gzip, zstd, LZ4, Brotli.

Lossy:

• 일부 정보 손실 (품질 vs 비율 trade-off).
• 이미지(JPEG), 오디오(MP3), 비디오(H.264).
• 이 글의 범위 밖.

1.3 Shannon의 한계

정보 이론 (Claude Shannon, 1948):

어떤 데이터든 압축의 이론적 하한이 존재한다. 엔트로피:

p_i는 심볼 i의 확률. 단위는 bit/symbol.

예: 영어 텍스트의 엔트로피는 약 1.5 bit/char. 8-bit ASCII로 저장된 텍스트는 이론상 5배 이상 압축 가능.

실제 압축기는 이 한계에 가까워지려 한다. 하지만 정확히 도달 불가능.

1.4 두 단계 전략

현대 무손실 compressor의 대부분이 두 단계를 결합:

1. Dictionary / LZ: "ABCDEF...ABCDEF"처럼 반복된 시퀀스를 back-reference로 치환. 구조적 중복 제거.
2. Entropy coding: 남은 바이트들의 통계적 편향 활용. "a"가 자주 나오면 짧은 코드, "z"는 긴 코드.

두 단계는 독립적으로 발전. 어느 LZ, 어느 entropy를 조합하느냐에 따라 다른 compressor.

2. LZ77 — 모든 것의 뿌리

2.1 아이디어

Lempel와 Ziv의 1977년 논문. "반복된 시퀀스를 이전 위치 참조로 치환".

입력: ABABABAB

과정:
A          → "A" (리터럴)
B          → "B" (리터럴)
AB         → "이전 위치 -2, 길이 2 복사"
AB         → "이전 위치 -2, 길이 2 복사"

출력:

(0, 0, A)
(0, 0, B)
(2, 2, _)
(2, 2, _)

각 토큰: (offset, length, next_char). Offset = 얼마나 뒤로, length = 몇 바이트 복사.

2.2 슬라이딩 윈도우

실제로는 최근 N 바이트의 윈도우만 검색.

[search buffer (N bytes)] [lookahead buffer (M bytes)] [미처리 데이터]

매 step:

1. Lookahead의 첫 바이트들이 search buffer의 어디에 나타났는지 찾기.
2. 가장 긴 match를 찾음.
3. (offset, length, next_char) 출력.
4. Window를 length + 1만큼 전진.

2.3 LZSS (1982)

LZ77의 개선: match가 너무 짧으면 back-reference가 오히려 손해. (3 byte reference가 3 byte 리터럴과 같음.)

LZSS: flag bit으로 "다음이 리터럴인지 reference인지" 표시. 3 byte 이상만 reference.

대부분 modern compressor는 LZSS variant.

2.4 LZ78와 LZW

LZ78: slide window 대신 명시적 dictionary 구축. Dictionary가 시퀀스 index를 저장.

LZW (Welch, 1984): LZ78의 변형. GIF, Unix compress, 구 PDF.

지금은 거의 쓰이지 않음. LZ77 family가 지배.

2.5 Back-reference의 효율

예: 1 MB 반복 텍스트

• Raw: 1 MB.
• LZ77 (window 32 KB): 처음 ~32 KB 이후는 모두 "뒤로 32 KB, 길이 ..." reference. 수 바이트로 표현.
• 최종: ~32 KB + metadata.

32배 압축. 원리는 단순: "반복을 가리킨다".

2.6 Hash-based Matching

실제 구현에서는 매 위치에서 "가장 긴 match" 찾기가 병목. 해결: hash chain.

각 3-byte prefix에 해시를 계산하고, 같은 해시의 이전 위치들을 링크드 리스트로 연결. Match 후보를 빠르게 찾음.

속도 vs 압축률 trade-off:

• Hash chain 길게: 더 많은 후보 검사 → 더 긴 match → 더 나은 압축 → 느림.
• 짧게: 빠름, 압축률 낮음.

이것이 gzip의 "-1 (fast)" vs "-9 (best)" 차이.

3. Huffman Coding

3.1 아이디어

David Huffman의 1952년 알고리즘 (MIT 대학원생 과제). "자주 나오는 심볼에 짧은 코드, 드문 심볼에 긴 코드".

예: 텍스트에서 문자 빈도

a: 40%
b: 20%
c: 15%
d: 15%
e: 10%

고정 길이 3-bit 코드면 symbol 당 3 bit. 평균 3 bit/symbol.

Huffman 코드:

a → 0     (1 bit)
b → 10    (2 bits)
c → 110   (3 bits)
d → 1110  (4 bits)
e → 1111  (4 bits)

평균: 0.4×1 + 0.2×2 + 0.15×3 + 0.15×4 + 0.10×4 = 2.25 bit/symbol. 25% 절약.

3.2 Prefix-free Property

Huffman 코드는 prefix-free — 어떤 코드도 다른 코드의 접두사가 아니다. 즉 0, 10, 110 같이. 이 덕분에 구분자 없이 연속 decode 가능.

01001101110

→ 0 10 0 110 1110 → a b a c d

3.3 Huffman Tree

이진 트리를 만들어 각 심볼에 경로 할당:

        *
       / \
      *   a
     / \
    *   b
   / \
  *   c
 / \
d   e

• Leaf가 심볼.
• 경로가 코드 (왼쪽=0, 오른쪽=1).
• 자주 나오는 심볼이 짧은 경로.

3.4 Tree 구축

1. 모든 심볼을 우선순위 큐에 빈도순으로.
2. 가장 작은 두 노드를 꺼내 부모 노드로 합침 (빈도 = 합).
3. 부모를 큐에 삽입.
4. 큐에 하나만 남을 때까지 반복.

O(n log n) 시간. 탐욕 알고리즘이지만 최적 prefix-free 코드임이 증명됨.

3.5 Canonical Huffman

표준 Huffman tree는 여러 가능한 형태. Canonical form은 길이만 저장하고 규칙적으로 할당 → 압축 메타데이터 작음.

DEFLATE와 대부분 현대 compressor는 canonical Huffman 사용.

3.6 한계

Huffman의 한계:

• 최소 1 bit/symbol. 심볼 확률이 50%를 초과해도 더 줄일 수 없음.
• 확률이 50%인 경우 (예: fair coin) — 이상적이지만 비효율 아님.
• 확률이 90%인 경우 (예: biased data) — 이론상 0.15 bit/symbol가 필요한데 Huffman은 1 bit → 85% 손실.

이 한계를 Arithmetic coding과 ANS가 극복한다.

4. Arithmetic Coding

4.1 아이디어

"전체 메시지를 하나의 실수로 표현". 어떤 확률 분포에도 이론적 한계에 근접.

4.2 예제

알파벳 a (50%), b (25%), c (25%). 인코딩할 메시지: "abc".

초기 범위: [0, 1).

1. 'a' 입력: 범위 = [0, 0.5).
2. 'b' 입력: 0.5 × 0.5 = 0.25 길이, offset 0.25. 범위 = [0.25, 0.375).
3. 'c' 입력: 0.125 × 0.25 = 0.031, offset 0.09375. 범위 = [0.34375, 0.375).

이 범위 안의 아무 실수나 출력. 예: 0.35 → 01011010 (이진 표현).

Decoder는 같은 확률 분포로 역산. 0.35 × 2 = 0.7 → 범위 [0, 0.5) 미포함 → ... (실제로는 실수를 추적).

4.3 효율

각 심볼이 정확히 -log2(p) bit를 차지. Shannon 엔트로피 한계에 근접.

Huffman: 정수 bit만 (1, 2, 3...). Arithmetic: 실수 bit (0.5, 1.5, 2.3...).

4.4 왜 한정적 사용

단점:

1. 속도: 부동소수점 연산 또는 정밀 정수 산술. Huffman보다 2-5배 느림.
2. 특허 문제: IBM의 여러 특허로 수십 년간 사용 제한. 2000년대 이후 만료.
3. 복잡도: 구현 어려움, bug 취약.

30년 동안 "더 나은 기법이 있지만 실용적이지 않다"는 위치. H.264, JPEG 2000에서만 활용.

4.5 Range Coding

Arithmetic coding의 변형. 정수 산술 사용, 특허 문제 없음. 일부 compressor (7zip의 LZMA)가 사용.

5. ANS — 게임 체인저

5.1 배경

2009년 폴란드 수학자 Jarek Duda가 새 엔트로피 코딩을 제안. ANS (Asymmetric Numeral Systems). 이메일 리스트와 논문에 조용히 공개.

처음엔 관심 적었다. 하지만 곧 **"Arithmetic의 품질 + Huffman의 속도"**라는 평가를 받으며 급속히 채택.

5.2 아이디어

"큰 정수 하나"에 전체 메시지를 인코딩하되, 표준 레지스터 연산으로.

Arithmetic coding처럼 작동하지만 부동소수점 없음, 나눗셈 거의 없음. 대신 Finite State Machine으로 표현.

5.3 Finite State Entropy (FSE)

ANS의 실용 변형. Yann Collet (Zstd 저자)이 구현.

• 각 심볼에 다음 상태 할당.
• 인코딩: 심볼 입력 → 상태 전이 → 일부 bit 출력.
• 디코딩: 반대 방향.

상태 머신이 pre-computed table → 런타임에 lookup + shift → 매우 빠름.

5.4 tANS vs rANS

tANS (table-based ANS): 상태 전이 table. 빠르지만 큰 table → 메모리 오버헤드.

rANS (range-ANS): 범위 기반. table 없음, 약간 느림, 더 유연.

Zstd의 FSE는 tANS. Facebook의 일부 내부 도구는 rANS.

5.5 성능

FSE vs Huffman vs Arithmetic:

"아무 단점 없는 업그레이드". 왜 진작 없었는지 의문.

5.6 채택

ANS 기반 compressor:

• Zstandard (2016): FSE 사용. 가장 널리 쓰임.
• LZFSE (Apple, 2015): LZ + FSE. iOS/macOS 기본.
• AV1 비디오 codec: 엔트로피 단계에 ANS.
• oodle: 상용 게임 압축.
• Brotli: 일부 부분.

2015년 이후 나온 compressor의 사실상 표준 entropy coder.

6. DEFLATE — gzip의 엔진

6.1 개요

Phil Katz의 1993년 작품. PKZIP에 사용, 이후 RFC 1951 (1996)로 표준화.

LZ77 + Huffman의 결합. 가장 널리 쓰이는 압축 포맷:

• gzip (.gz).
• ZIP.
• PNG (이미지).
• HTTP Content-Encoding: gzip.

30년 넘게 표준.

6.2 구조

압축된 데이터 = block 시퀀스. 각 block:

• Header: block 타입 (stored, fixed Huffman, dynamic Huffman).
• Huffman tree (dynamic만).
• Compressed data: LZ77 토큰들, Huffman으로 인코딩.

6.3 LZ77 단계

• Window: 32 KB.
• Match length: 3-258 바이트.
• Offset: 1-32768.

각 match는 (length, distance) 쌍. 리터럴은 0-255 문자 코드.

6.4 Huffman 단계

두 Huffman 트리:

• Literal/length tree: 리터럴 문자(0-255) + length 코드(257-285).
• Distance tree: offset 코드(0-29).

길이와 거리는 log-scale로 "bucket"에 매핑. 작은 값은 정확히, 큰 값은 extra bits로.

6.5 레벨

gzip -1 ~ gzip -9:

• -1: lazy match, 빠른 hash chain.
• -9: 더 긴 hash chain, best match 탐색.

Time/space trade-off. 실제 차이는 ~20% 압축률 / 5-10x 속도.

6.6 성능

• 압축: ~50 MB/s (단일 코어).
• 해제: ~300 MB/s.
• 비율: 텍스트 기준 3-5x.

30년 전 알고리즘이지만 여전히 쓸 만. 단, 현대 대안들(zstd, brotli)이 더 나음.

7. LZ4 — 극한 속도

7.1 철학

Yann Collet의 2011년 작품. "압축률을 희생해서 속도를 극대화".

7.2 디자인

• No entropy coding: LZ77만, Huffman/ANS 없음.
• Simple format: byte-aligned, no bit manipulation.
• Hash table: 단순한 해시 함수, 한 번의 lookup만.
• Small match minimum: 4 바이트.

7.3 속도

• 압축: 500-800 MB/s (단일 코어).
• 해제: 2-5 GB/s (단일 코어).
• 비율: 텍스트 기준 2-2.5x (gzip의 절반).

"압축률은 낮지만 매우 빠르다". 네트워크/디스크 bottleneck보다 CPU가 빠른 환경에 적합.

7.4 사용처

• RocksDB, Cassandra: 디스크 저장 압축.
• Zstandard 내부: 낮은 level에서 LZ4-like 모드.
• MongoDB: Snapshot, journal.
• Kernel: Linux의 일부 압축 경로.
• Kafka: 일부 설정.

"실시간 압축이 필요하지만 CPU 예산이 제한된" 모든 곳.

7.5 LZ4 HC

"High Compression" 변형. 더 느리지만 더 나은 압축률. 여전히 zstd보다는 빠르고 덜 압축.

7.6 Snappy

Google의 유사 compressor (2011). LZ4와 비슷한 특성:

• Very fast, 낮은 비율.
• LevelDB, BigTable, HBase에 사용.

LZ4가 약간 더 빠르고 약간 더 압축. 대부분 LZ4 승.

8. Zstandard — 범용의 왕

8.1 배경

Facebook의 Yann Collet (LZ4 저자 동일). 2016년 발표.

목표: "gzip보다 3배 빠르면서 더 잘 압축".

8.2 구성

• LZ77-style match: 2+ 바이트, 큰 window(기본 8 MB).
• Entropy coding: FSE (ANS 기반) for literals, Huffman for literal distribution in some cases.
• Frame format: 청크 단위, 스트리밍 친화적.

8.3 Dictionary 기능

Killer feature: pre-trained dictionary.

# 100개 샘플 JSON으로 dictionary 학습
zstd --train samples/*.json -o dict.bin

# Dictionary 사용해 압축
zstd -D dict.bin input.json -o output.zst

# Dictionary 사용해 해제
zstd -D dict.bin -d output.zst -o input.json

효과: 작은 메시지(수백 바이트)에 dictionary가 10-100x 압축률 향상.

일반 compressor는 작은 메시지에 약한데 zstd dictionary로 극복. Kafka, 작은 HTTP API, 채팅 메시지에 이상적.

8.4 Long-range Mode

zstd --long: 멀리 떨어진 match까지 검색 (GB 단위 window). 백업, 디스크 이미지에 효과적.

8.5 Compression Levels

zstd -1 (fast) ~ zstd -22 (max):

• -1: ~500 MB/s, ratio 2x. LZ4와 경쟁.
• -3 (기본): ~200 MB/s, ratio 3x.
• -9: ~50 MB/s, ratio 3.5x.
• -19: ~10 MB/s, ratio 4.2x.
• -22: ~1 MB/s, ratio 4.5x.

넓은 범위. 상황에 따라 선택 가능.

8.6 Decompression 속도

2-3 GB/s (단일 코어). Compression level과 무관. 항상 빠름 — 이게 가장 큰 장점.

8.7 채택

• Linux 커널 압축 (zstd 옵션).
• Btrfs, ZFS 파일시스템.
• Arch Linux 패키지 (전체 repo zstd로).
• Kafka, RocksDB 등 현대 시스템.
• Facebook 전체 인프라.

사실상 새 표준.

8.8 코드 복잡도

Zstd source: ~25,000 줄 C. gzip은 ~5,000 줄. Trade-off: 복잡도 vs 성능.

단 단일 바이너리, 외부 의존성 없음 → 포팅 쉬움.

9. Brotli — Google의 선택

9.1 배경

Google Jyrki Alakuijala 등, 2015년 발표. HTTP/2 컨텐츠 압축용.

특징:

• 정적 dictionary 내장: 120 KB의 영어/HTML/CSS/JS 토큰.
• Context modeling: literal 주변 context를 고려해 더 나은 Huffman 트리.
• 긴 back-reference: 2 MB window.

9.2 압축률

Brotli는 zstd와 유사한 압축률에 약간 느림.

텍스트, 특히 HTML/CSS/JS에 최적화. 웹 콘텐츠에는 zstd보다 조금 더 좋음 (내장 dictionary 덕분).

9.3 Decompression

~400 MB/s. Zstd보다 약간 느림. 하지만 충분.

9.4 사용처

주로 웹:

• HTTP Content-Encoding: br. Chrome, Firefox 모두 지원.
• WOFF2 (Web Open Font Format 2).
• Android APK.
• Cloudflare 엣지 압축.

일반 시스템에서는 zstd가 주로 사용.

9.5 Brotli vs Zstd (웹)

10 MB HTML + CSS + JS
gzip (-9):   2.5 MB
brotli (11): 1.8 MB  (28% better than gzip)
zstd (19):   1.9 MB

Brotli가 웹에서 약간 더 좋음. 정적 dictionary 효과.

10. LZMA / 7z

10.1 배경

Igor Pavlov의 LZMA (Lempel-Ziv-Markov chain-Algorithm). 7-zip 압축기의 기본. 1998년부터.

10.2 특징

• Huge window: 최대 4 GB. 매우 멀리 있는 match도 찾음.
• Arithmetic coding (range coder): Huffman보다 더 나은 비율.
• Markov model: literal 주변 context로 조건부 확률 개선.
• 매우 복잡: 구현 이해 어려움.

10.3 성능

• 압축: 매우 느림 (수 MB/s).
• 해제: 수십 MB/s.
• 비율: 매우 좋음. Zstd보다 5-15% 더 압축.

10.4 사용처

• 7-zip: GUI 압축 도구.
• xz (Unix): .tar.xz.
• Arch Linux (이전엔 xz, 지금은 zstd로 전환 중).
• Debian packages (.deb): 일부.

"극한 압축률이 필요하고 시간이 있을 때". 백업, 배포 파일에.

10.5 왜 zstd가 대체

Zstd: 약간 나쁜 비율, 훨씬 빠름. 대부분 경우 합리적 선택.

Arch가 xz → zstd로 전환하면서 "설치 시간이 50% 감소, 패키지 크기는 20% 증가"라고 보고. 사용자 입장에서 net positive.

11. 비교 표

11.1 압축률

고정된 입력(텍스트, 10 MB Linux kernel source):

11.2 용도별 권장

실시간 스트리밍 / 고속 I/O:

• LZ4: 압축률은 낮지만 병목 없음.
• 예: 로그 스트림, 인메모리 캐시.

범용 파일 압축:

• Zstd -3: 합리적 압축, 빠름.
• gzip의 현대적 대체.

백업 / 아카이브:

• Zstd -19 또는 xz: 한 번 압축, 여러 번 해제.
• 압축 시간 허용 가능.

웹 콘텐츠:

• Brotli: 정적 dictionary로 HTML/CSS/JS 최적화.
• 폴백 gzip.

작은 메시지 많음:

• Zstd with dictionary: 학습된 dictionary로 10-100배 개선.
• 예: Kafka 메시지, 작은 HTTP API, 채팅.

DB / 스토리지 엔진:

• LZ4: 빠른 read.
• Zstd: 공간 효율 우선.

12. SIMD 가속

12.1 압축의 SIMD 기회

압축은 이론적으로 sequential 작업이지만 많은 부분에서 SIMD 적용 가능:

1. Hash 계산: 여러 포지션의 hash를 한 번에.
2. Match 검색: 긴 byte comparison.
3. Huffman decoding: 여러 심볼 병렬 lookup.
4. Entropy decode: ANS state update.

12.2 현대 구현

Zstd: SSE2/AVX2 지원. SIMD로 literal copying 가속.

LZ4: 매우 단순한 구조라 SIMD 활용 적음. 하지만 decompression 시 긴 복사는 memcpy (SIMD 내장).

libdeflate: zlib의 대안 구현. SIMD 가속으로 zlib보다 2-3배 빠른 gzip.

12.3 대역폭의 한계

많은 경우 메모리 대역폭이 실제 병목. SIMD로 CPU 연산을 줄여도 L3/DRAM 대역폭 포화.

압축 속도가 수 GB/s에 도달하면 하드웨어 한계.

12.4 하드웨어 압축

Intel QAT (Quick Assist): CPU 내부에 DEFLATE 하드웨어 가속기. 100 GB/s 수준.

NVIDIA GPU: cuDNN의 일부, 일부 DB 엔진.

SmartNIC: 네트워크 카드가 압축/해제.

대규모 서비스(Facebook, Google)에서 활용.

13. Dictionary Training

13.1 왜 필요한가

일반 compressor는 입력 안의 중복만 찾음. 100 byte JSON 메시지에는 내부 중복이 거의 없음 → 압축 안 됨.

{"name":"Alice","age":30}

이 메시지를 압축하면 오히려 커질 수 있음 (메타데이터 오버헤드).

13.2 Dictionary의 역할

수백 개의 유사한 JSON을 보면 공통 패턴이 많다:

• "name": 자주 나옴.
• "age": 자주 나옴.
• 키 이름 전반적으로 반복.

Dictionary = "이 공통 토큰들을 미리 담아둔 참조 자료".

압축 시 reference를 dictionary로 가리키면 매우 짧은 코드.

13.3 학습 과정

zstd --train samples/*.json --maxdict=110K -o dict

1. 샘플 파일들 읽기.
2. 가장 흔한 substring을 찾기 (통계).
3. 상위 substring들을 dictionary에 포함.
4. Dictionary 파일 출력.

13.4 사용

zstd -D dict input.json -o output.zst

Dictionary 파일을 encoder와 decoder 모두가 가지고 있어야 함. 공유 필요.

13.5 성능

실측:

• 일반 JSON 100 byte: zstd로 90 byte (10% 감소).
• Dictionary 사용 (10 KB dictionary, 1000개 JSON 학습): 30 byte (70% 감소).

7배 차이. 작은 메시지 대량 전송에 필수.

13.6 사용 사례

• Kafka: 메시지별로 작은 payload. Dictionary로 50-80% 감소.
• HTTP API: 응답 payload 구조가 정해짐. Dictionary 학습 가능.
• Protobuf messages: 특정 스키마에 특화된 dictionary.
• NoSQL KV: 비슷한 키-값 쌍.

Facebook은 이 기법으로 petabyte 규모 저장 비용 절감.

14. 실전 예제

14.1 HTTP 서버

Accept-Encoding: gzip, br, zstd

Response:
Content-Encoding: zstd

Nginx:

http {
    zstd on;
    zstd_comp_level 3;
    zstd_types text/html text/css application/javascript application/json;
}

(zstd module 설치 필요. 기본 Nginx는 gzip.)

정적 파일은 build 시점에 미리 압축 (.br, .gz 파일) → runtime CPU 절약.

14.2 Kafka

compression.type=zstd

Producer가 배치를 압축. 기본 3 레벨 적용 시 텍스트 메시지가 3-5x 감소.

Kafka는 압축된 배치를 그대로 저장 + 전달. Broker는 압축 해제 안 함 → CPU 효율.

14.3 Kubernetes 컨테이너 이미지

OCI image layers는 보통 gzip. zstd로 전환 중:

docker build --compression=zstd .

Pull 시간 30-50% 감소. 큰 이미지(ML model)에 유용.

14.4 Backup

tar -cf - /data | zstd -19 --long > backup.tar.zst

--long으로 큰 window 사용 → 파일 간 중복도 제거.

Rsync + zstd는 전통적 gzip 조합보다 10-30% 빠르고 작음.

14.5 DB

RocksDB:

options.compression = kZstdCompression;
options.bottommost_compression = kZstdCompression;
options.compression_opts.level = 3;

L0-L4는 LZ4 (빠른), L5-L6는 zstd (높은 압축). Tiered compression.

ClickHouse:

CREATE TABLE events (
    ...
) ENGINE = MergeTree
SETTINGS
    index_granularity = 8192;

ALTER TABLE events MODIFY COLUMN data CODEC(ZSTD(3));

컬럼별 다른 코덱 가능.

15. 현대 동향

15.1 Asymmetric Speed

Decode >> Encode 속도 불균형을 활용:

• 한 번 압축, 수천 번 해제 (웹, CDN, 이미지).
• Encoder에 시간 투자해 decoder 빠름.
• Brotli -11, zstd -19.

15.2 Hardware Acceleration

• Intel QAT (서버 CPU).
• NVIDIA decompression engines (Ampere+).
• AWS Nitro card 일부.

대규모 서비스에서 주요 투자 영역.

15.3 ML-based

Google DeepMind의 실험: LLM 기반 압축. 모델이 "다음 토큰을 예측"하면 차이만 저장.

결과: 이미지/텍스트에서 5-10배 압축. 하지만 느리고 GPU 필요 — 실용적이지 않음.

하지만 특수 용도(genome, 과학 데이터)에서 관심.

15.4 Lossy Text?

"일부 오차 허용" 텍스트 압축 실험 중. 자연어의 정보 이론 한계는 여전히 1-1.5 bit/char 수준이지만 LLM이 이를 더 낮출 가능성.

학술 연구 단계.

15.5 새 entropy coder?

ANS 이후 10년. 차세대는?

Pelican, rANS 변형 등이 실험 중. 하지만 ANS가 충분히 좋아서 주류 교체는 당분간 없을 듯.

16. 자주 묻는 질문

Q: 이미 압축된 파일을 또 압축하면?

A: 효과 거의 없음. JPEG, MP3, ZIP, 이미 gzip 된 파일 등. 대부분 1% 미만 절감, 심지어 커질 수 있음 (메타데이터).

Q: Solid 압축 vs 파일별 압축?

A: Solid (전체를 하나의 stream): 파일 간 중복 활용, 더 좋은 압축률. 단점: 하나만 꺼내려면 전체 해제. 파일별: 독립적, 빠른 random access. 단점: 공유 중복 손실.

ZIP는 파일별, tar.gz / tar.zst / 7z는 solid.

Q: 최대 효율 조합?

A: LZMA / zstd --long 둘 다 수 GB window로 큰 파일 간 중복 활용.

Q: 암호화와 함께?

A: 압축 → 암호화 순서. 반대는 암호화된 데이터가 랜덤해서 압축 안 됨. 주의: CRIME/BREACH 같은 length-based 공격. HTTPS에서 sensitive data + compression 혼합 시 위험.

Q: Streaming 지원?

A: Zstd, brotli, gzip 모두 streaming API. 입력을 한 번에 가지고 있지 않아도 압축 가능.

17. 요약 — 한 장 정리

┌─────────────────────────────────────────────────────┐
│          Compression Cheat Sheet                     │
├─────────────────────────────────────────────────────┤
│ 기본 원리:                                              │
│   두 단계: LZ (중복 제거) + Entropy (통계)            │
│                                                       │
│ LZ 패밀리:                                             │
│   LZ77 (slide window, back-reference)                │
│   LZSS (length minimum)                              │
│   LZ78/LZW (explicit dictionary, deprecated)         │
│                                                       │
│ Entropy Coding:                                       │
│   Huffman (1952): 정수 bit, 빠름                     │
│   Arithmetic (1970s): 실수 bit, 느림, 특허            │
│   ANS/FSE (2009): Arithmetic 품질 + Huffman 속도     │
│                                                       │
│ 주요 알고리즘:                                          │
│   DEFLATE (1993): LZ77 + Huffman                     │
│   LZ4 (2011): LZ77만, 초고속                         │
│   Zstandard (2016): LZ77 + FSE                      │
│   Brotli (2015): 정적 dictionary + context          │
│   LZMA (1998): LZ77 + Markov + Range                │
│                                                       │
│ 속도 vs 비율:                                          │
│   LZ4/Snappy: 빠름, 낮은 비율                         │
│   gzip -1: 빠름, 중간                                │
│   zstd -3: 균형 (기본 권장)                           │
│   gzip -9: 느림, 좋은 비율                            │
│   zstd -19: 느림, 더 좋은 비율                        │
│   brotli -11: 느림, 웹 최적                           │
│   xz -9: 매우 느림, 최고 비율                         │
│                                                       │
│ 용도별:                                                │
│   실시간: LZ4                                         │
│   범용: zstd -3                                       │
│   백업: zstd -19 또는 xz                              │
│   웹: brotli                                          │
│   작은 메시지: zstd + dictionary                      │
│                                                       │
│ Dictionary Training:                                  │
│   Zstd --train                                        │
│   작은 메시지 10-100x 개선                            │
│   Kafka, HTTP API, NoSQL에 유용                      │
│                                                       │
│ 가속:                                                  │
│   SIMD (libdeflate, zstd)                            │
│   하드웨어 (Intel QAT)                                │
│   GPU                                                 │
│                                                       │
│ 주의:                                                  │
│   이미 압축된 것 재압축 불가                            │
│   암호화 전에 압축                                     │
│   CRIME/BREACH 주의 (HTTPS)                          │
└─────────────────────────────────────────────────────┘

18. 퀴즈

19. 학습 리소스

논문:

• Lempel & Ziv, "A Universal Algorithm for Sequential Data Compression" (1977).
• Huffman, "A Method for the Construction of Minimum-Redundancy Codes" (1952).
• Duda, "Asymmetric Numeral Systems" (2009).
• Yann Collet, Zstd 관련 블로그 글들.

책:

• "Introduction to Data Compression" — Khalid Sayood.
• "Managing Gigabytes" — Witten, Moffat, Bell.

블로그:

• https://fastcompression.blogspot.com — Yann Collet (LZ4, Zstd 저자).
• https://www.righto.com/2019/07/shanghaied-by-zsr.html — 압축 알고리즘 블로그.

도구:

• zstd, gzip, xz, brotli CLI.
• lzbench: 다양한 compressor 벤치마크.
• squash benchmark (https://quixdb.github.io/squash-benchmark).

소스:

• Facebook/zstd GitHub.
• LZ4 GitHub.
• Brotli GitHub.

이 글이 도움이 됐다면 다음 포스트도 확인해 보세요:

• "SIMD / AVX / NEON Deep Dive" — 압축 가속에 쓰이는 기법.
• "RocksDB & LSM-Tree" — LZ4/zstd를 사용하는 DB 엔진.
• "CDN & Edge Caching" — 웹 압축의 배포.
• "Binary Serialization (Protobuf/Thrift/Avro)" — 사전 압축된 데이터 포맷.