8. LZ77 / LZ78 / LZW — 사전 기반 압축

핵심 인사이트 (3줄 요약)

1. 본질: LZ77/LZ78/LZW는 이전에 나타난 문자열을 사전(Dictionary)에 참조하여 반복 패턴을 역참조(Back-reference)로 교체하는 무손실 범용 압축 알고리즘 계열로, 현대 데이터 압축의 표준 기반이다.
2. 가치: 텍스트부터 바이너리까지 데이터 종류에 무관하게 반복 패턴을 학습하여 압축하므로, ZIP·PNG·gzip·HTTP·GIF·TIFF 등 인터넷과 파일 시스템에서 쓰이는 거의 모든 무손실 압축의 근간이다.
3. 판단 포인트: LZ77은 슬라이딩 윈도우 크기가 압축률-속도 트레이드오프를 결정하며, LZW는 사전을 명시 전송하지 않아도 되는 장점으로 GIF·TIFF·PDF에서 활용된다.

Ⅰ. 개요 및 필요성

텍스트 "abcabcabc"는 "abc"가 3번 반복된다. 이 반복을 매번 저장하는 대신 "앞에서 3글자 전으로 돌아가 6글자 복사"라는 참조로 표현하면 크기가 극적으로 줄어든다. LZ (Lempel-Ziv) 계열 알고리즘은 이 아이디어를 체계화하여 1977년(LZ77)과 1978년(LZ78)에 발표되었으며, 이후 모든 범용 압축 알고리즘의 원형이 되었다.

LZ 계열 알고리즘 분류

📢 섹션 요약 비유: LZ77은 요리책을 압축할 때 "3페이지와 동일한 조리법, 4번째 단계부터"처럼 앞 내용을 참조하는 방식—반복 내용을 매번 쓰지 않는다.

Ⅱ. 아키텍처 및 핵심 원리

LZ77: 슬라이딩 윈도우 압축

슬라이딩 윈도우:
  ┌──────────────────────┬──────────────────┐
  │   검색 버퍼 (과거)    │  미리보기 버퍼   │
  │  ← 최대 32KB 이전 →  │  (현재 위치 →)  │
  └──────────────────────┴──────────────────┘

토큰: (offset, length, next_char)
  offset:    검색 버퍼에서 일치 시작 위치까지의 역방향 거리
  length:    일치하는 문자 수
  next_char: 일치 이후 다음 문자

예시: "abcabc"
  처리 "abc" → (0,0,'a'), (0,0,'b'), (0,0,'c')  ← 처음 3글자 리터럴
  처리 "abc" → (3,3,'?')  ← 3글자 전으로 돌아가 3글자 복사

ASCII 다이어그램:
  검색 버퍼          미리보기
  [a b c]            [a b c ...]
          ↑ offset=3, length=3
  토큰: (3, 3)  ← 6글자를 2숫자로 압축

LZ78: 명시적 사전 방식

사전을 동적으로 구축하며 인덱스로 참조

입력: "abababab"
사전 구축:
  "" + 'a' → 사전[1]="a",  출력: (0, 'a')
  "" + 'b' → 사전[2]="b",  출력: (0, 'b')
  "a" + 'b' → 사전[3]="ab", 출력: (1, 'b')  ← 사전[1]="a" 참조
  "a" + 'b' → 이미 사전[3]="ab"
  "ab" + 'a' → 사전[4]="aba", 출력: (3, 'a')
  ...

LZW: 사전 전송 불필요

LZ78에서 진화:
  - 사전이 초기 알파벳(0~255)으로 시작
  - 인코더와 디코더가 동일 규칙으로 사전을 동기화
  - 사전 자체를 압축 파일에 포함할 필요 없음

GIF 형식:
  256색 팔레트 → LZW 사전의 첫 256 엔트리로 초기화
  픽셀 시퀀스를 LZW로 압축 → 91년 Unisys 특허 만료로 현재 무료

DEFLATE = LZ77 + 허프만 코딩

단계 1: LZ77
  입력: "Hello World Hello World"
  LZ77 출력: Hello World (0,0,H)(0,0,e)...(12,11) ← 12글자 전 11글자 복사

단계 2: 허프만 코딩
  LZ77 토큰의 리터럴·길이·거리 값에 빈도 기반 허프만 코드 적용
  → 최종 압축 스트림

ZIP, gzip, PNG, zlib, HTTP/1.1 Content-Encoding: gzip 모두 이 방식

📢 섹션 요약 비유: DEFLATE는 이사할 때 이미 포장된 박스 참조표(LZ77)를 만들고, 그 참조 번호들을 또 모스 부호(허프만)로 줄이는 이중 절약 전략이다.

Ⅲ. 비교 및 연결

알고리즘 성능 비교

슬라이딩 윈도우 크기 트레이드오프

윈도우 크기 소 (예: 4KB)  →  참조 범위 좁음  →  압축률 낮음, 속도 빠름
윈도우 크기 대 (예: 32KB) →  참조 범위 넓음  →  압축률 높음, 메모리 더 사용

gzip 기본: 32KB 윈도우
7-Zip 울트라: 256MB 윈도우 → 매우 높은 압축률, 더 많은 RAM 필요

📢 섹션 요약 비유: 슬라이딩 윈도우는 기억력의 크기—큰 기억력(큰 윈도우)은 더 오래된 반복 패턴도 기억해서 압축률이 높지만, 더 많은 뇌(메모리)가 필요하다.

Ⅳ. 실무 적용 및 기술사 판단

주요 활용 사례

• ZIP / gzip: DEFLATE (LZ77+허프만), 파일 압축·웹 서버 콘텐츠 인코딩
• PNG: DEFLATE + 이미지 필터링, 무손실 이미지 표준
• GIF: LZW, 팔레트 기반 애니메이션
• HTTP/1.1: Content-Encoding: gzip / Content-Encoding: deflate
• HTTP/2: Zstandard 또는 Brotli (LZ77 기반 + 정적 사전)

기술사 판단 기준

범용 파일 압축 표준              →  DEFLATE (ZIP/gzip)
이미지 무손실 압축               →  PNG (DEFLATE + 필터)
웹 콘텐츠 최고 압축              →  Brotli (LZ77 + 정적 사전 + ANS)
고성능 실시간 압축 (서버간)      →  Zstandard
팔레트 이미지 + 애니메이션       →  GIF (LZW)
텍스트 최고 압축 (백업 등)       →  bzip2 / xz (LZMA)

📢 섹션 요약 비유: ZIP과 PNG의 DEFLATE는 같은 레시피(LZ77+허프만)로 만들었지만, PNG는 이미지 특성에 맞춘 전처리(필터링)를 더해 더 맛있는 요리(높은 압축률)를 만든다.

Ⅴ. 기대효과 및 결론

LZ77/LZ78/LZW는 데이터의 종류에 무관하게 반복 패턴을 학습하여 압축하는 범용 알고리즘으로, 1977년 이후 인터넷 표준 압축 기술의 핵심이 되었다. DEFLATE는 LZ77과 허프만 코딩의 결합으로 최고의 범용 압축 표준이 되었으며, 현대의 Zstandard와 Brotli도 같은 원리를 발전시킨 것이다.

결론: LZ 계열은 "무엇이든 압축하는" 범용 알고리즘이며, 슬라이딩 윈도우 크기와 후처리(허프만 등) 결합이 압축률과 속도를 결정하는 핵심 파라미터다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[반복 패턴 감지 (Repetition Detection)]
    │
    ▼
[LZ77 — 슬라이딩 윈도우 사전 압축]
    │
    ▼
[LZ78 / LZW — 동적 사전 압축 (GIF/TIFF)]
    │
    ▼
[DEFLATE (LZ77 + 허프만 코딩) — ZIP/PNG/gzip]
    │
    ▼
[Zstandard / Brotli — 현대 고속 압축 표준]

데이터 압축 기술이 LZ 계열 사전 참조 방식에서 허프만 결합을 거쳐 현대 표준 알고리즘으로 발전한 흐름이다.

👶 어린이를 위한 3줄 비유 설명

1. LZ77은 편지를 쓸 때 "앞에 적은 것과 똑같으니 3쪽 2번째 줄 참조"라고 하는 것—반복을 적지 않고 참조만 해.
2. LZW는 공통 단어장을 만들어두고 번호만 적는 방식—GIF 이미지가 작은 이유 중 하나야.
3. ZIP은 LZ77이 반복 패턴을 없애고 허프만 코딩이 남은 기호를 더 줄이는 두 단계 압축이야!