토픽 38 / 82

허프만 코딩 (Huffman Coding)

문자의 출현 빈도를 기반으로 가변 길이 코드를 생성하여 데이터를 효율적으로 압축하는 탐욕 알고리즘 기반 무손실 압축 기법

목적: 무손실 압축, 빈도 기반 최적 코드, 데이터 크기 축소

특징: 탐욕 알고리즘, 가변 길이 코드, 접두사 코드(Prefix Code), 이진 트리

접두사 코드: 어떤 코드도 다른 코드의 접두사가 아님, 모호성 없음

동작: ① 빈도 계산 → ② 최소 힙(우선순위 큐) 생성 → ③ 빈도 작은 두 노드 병합(새 노드 생성) → ④ 루트까지 반복 → ⑤ 트리 순회하며 코드 생성(왼쪽 0, 오른쪽 1)

시간 복잡도: O(n log n) - n = 고유 문자 수, 힙 연산

공간 복잡도: O(n) - 트리

장점: 최적 압축(빈도 기반), 무손실, 단순 구현, 접두사 코드

단점: 빈도 테이블 저장 필요, 소규모 데이터 오버헤드, 고정 빈도(적응형 아님)

적용사례: 압축(ZIP, GZIP), 이미지(JPEG), 네트워크 프로토콜, 파일 아카이빙

비교: 허프만(무손실/최적) vs LZW(사전 기반) vs RLE(연속 반복)

연관: 탐욕, 우선순위 큐, 압축, 접두사 코드, 이진 트리