허프만 코딩 시각화
빈도 기반 최적 접두사 코드를 생성하는 탐욕 알고리즘으로 데이터 압축 원리를 학습하세요
탐욕법★★☆
속도
1 / 1단계
각 단계를 클릭하면 해당 시점으로 이동합니다.
인코딩 버튼을 눌러 시작하세요.
허프만 코딩이란?
문자 빈도에 따라 최적 접두사 코드를 생성하는 탐욕 알고리즘입니다. 빈번한 문자에 짧은 코드, 드문 문자에 긴 코드를 할당하여 전체 비트 수를 최소화합니다.
사용 방법
- 1텍스트를 입력하면 문자 빈도를 자동 분석합니다
- 2인코딩하면 허프만 트리 구축 과정을 단계별로 관찰할 수 있습니다
- 3코드 테이블에서 각 문자의 비트 코드를 확인하세요
- 4압축률을 확인하고 다양한 텍스트로 실험해보세요
동작 원리
- 1각 문자의 빈도를 계산하여 우선순위 큐(최소 힙)에 삽입합니다
- 2빈도가 가장 작은 두 노드를 꺼내 합치고 새 부모 노드를 만듭니다
- 3하나의 트리가 될 때까지 반복합니다
- 4트리에서 왼쪽=0, 오른쪽=1로 각 문자의 코드를 결정합니다
실무 활용
- •ZIP, GZIP 압축의 기본 알고리즘
- •JPEG, PNG 이미지 압축의 최종 엔트로피 코딩 단계
- •MP3/AAC 오디오 압축
- •HTTP/2 헤더 압축(HPACK)에서 허프만 테이블 사용
비슷한 알고리즘
- •산술 코딩(Arithmetic Coding) — 허프만보다 압축률이 좋으나 구현이 복잡
- •LZW — 사전 기반 압축, GIF 포맷에 사용
- •Deflate — LZ77 + 허프만의 조합, ZIP/GZIP의 핵심
학습 팁
- •빈도가 편향된 텍스트(예: 'aaaaabbc')로 시작하면 트리 구조가 명확합니다
- •접두사 코드의 의미를 이해하세요 — 어떤 코드도 다른 코드의 접두사가 아닙니다
- •고정 길이 코드(ASCII)와 압축률을 직접 비교해보세요
자주 묻는 질문
Q. 항상 최적 압축인가?
A. 접두사 코드 중에서는 최적이지만, 산술 코딩이 이론적 한계에 더 가깝습니다.
Q. 디코딩은 어떻게?
A. 비트열을 읽으며 허프만 트리를 순회합니다. 리프에 도달하면 해당 문자를 출력합니다.