알고리즘HuffmanCompressionGreedyPriority QueueDEFLATE

허프만 코딩 (Huffman Coding)

빈도로 트리를 만들고 비트열을 인코딩·복원하는 무손실 부호화

시각화 로드 중...

알고리즘 복잡도

최선O(N + σ log σ + B)
평균O(N + σ log σ + B)
최악O(N + σ log σ + B)
공간O(σ) + 출력

개요

Algorithm Overview

허프만 코딩은 기호의 빈도를 이용해 접두어 없는 가변 길이 코드 를 만드는 무손실 부호화 방법이다. 자주 등장하는 기호를 짧은 경로에 배치해 전체 본문의 비트 수를 줄인다.

빈도에서 트리까지

빈도가 가장 작은 두 노드를 꺼내 부모로 합치고 다시 큐에 넣는다. 루트 하나가 남으면 왼쪽 간선을 0, 오른쪽 간선을 1로 읽어 각 리프의 코드를 만든다. 코드는 다른 코드의 접두어가 아니므로 구분자 없이 이어진 비트열도 리프에 도달할 때마다 해독할 수 있다.

같은 빈도의 노드는 선택 순서에 따라 서로 다른 트리와 코드가 나올 수 있다. 이 예제는 빈도, 서브트리의 가장 작은 문자, 생성 ID 순으로 정하고 먼저 꺼낸 노드를 왼쪽에 둔다. 빈도가 같더라도 코드 길이는 다를 수 있다.

ABRACADABRA 예제

A:5, B:2, C:1, D:1, R:2. 병합 순서는 C+D → B+CD → R+BCD → A+RBCD다. 결과는 A=0, B=110, C=1110, D=1111, R=10이며 인코딩 본문은 23비트다. 디코더는 리프에 도착할 때마다 문자를 출력하고 루트로 돌아간다.

기준논리적 본문 크기
UTF-8 원문 11바이트88비트
5종 기호 고정 길이 3비트33비트
허프만 코드 본문23비트

23비트는 파일 전체 크기 가 아니다. 바이트로 담으면 본문만 최소 3바이트이며 코드북, 길이 정보, 패딩 등은 별도다. 짧은 입력은 이런 부가 정보 때문에 원문보다 커질 수 있다. 0과 1을 화면에 표시한 문자열도 실제 비트 패킹과 다르다.

실제 사용: DEFLATE와 JPEG

DEFLATE는 LZ77과 허프만 코딩을 결합한다. LZ77은 반복 구간을 길이·거리로 표현하고 허프만 코딩은 리터럴/길이와 거리 기호를 부호화한다. 블록은 고정 코드, 동적 코드 또는 비압축 방식을 사용할 수 있다. gzip과 PNG에서 DEFLATE가 사용된다. 위 문자 단위 교육 예제의 비트열은 실제 gzip 출력이 아니다.

베이스라인 JPEG는 이미지 블록의 DCT·양자화 후 계수를 기호화하고 허프만 부호화한다. 허프만 단계는 무손실이며, 일반적인 JPEG의 손실은 양자화 등과 구분해야 한다. 모든 JPEG 모드가 같은 부호화 방식을 사용하는 것은 아니다.

비용과 한계

입력 길이 N, 기호 수 σ, 출력 비트 수 B에 대해 빈도 집계 O(N), 최소 힙 기반 트리 구성 O(σ log σ), 인코딩 출력과 디코딩은 O(B)다. 트리와 힙은 O(σ), 코드표와 출력 버퍼는 추가 공간이 든다. 이 시각화의 작은 예제는 학습을 위해 배열을 정렬해 우선순위를 계산하므로 최소 힙의 시간 복잡도와 구분한다. 주어진 빈도에 대해 이진 접두어 코드의 가중 길이를 최소화하지만 모든 압축 방식 중 항상 최소 파일 크기를 보장하지는 않는다. 압축은 암호화가 아니다.

학습 목표

  • 빈도와 우선순위 큐로 허프만 트리를 만들고 인코딩·복원 과정을 추적한다.
  • 본문 비트 수와 실제 파일 크기, DEFLATE와 JPEG에서의 역할을 구분한다.

자주 하는 오해

  • 허프만 코드 23비트를 코드북과 패딩을 포함한 실제 파일 크기로 판단하지 않는다.
  • 같은 빈도의 기호가 반드시 같은 길이의 코드를 갖는다고 가정하지 않는다.

핵심 정리

  • 두 최소 빈도를 반복 병합하고 접두어 없는 코드로 구분자 없이 복원한다.
  • 동률 규칙에 따라 비트 패턴은 달라질 수 있으며 실제 압축에는 추가 정보가 필요하다.

학습 확인

문제 1

허프만 트리 구성에서 다음에 병합할 노드는?

문제 2

접두어 없는 코드에서 비트를 읽다가 리프에 도착하면?

문제 3

허프만 본문이 23비트라면 파일 전체 크기는?

문제 4

빈도가 같은 두 기호는 항상 코드 길이가 같을까?

문제 5

허프만 코딩으로 복원할 수 있는 것은?

핵심 단계

  1. 1

    문자별 빈도를 집계한다.

  2. 2

    가장 작은 두 노드를 선택해 부모로 병합하고 큐에 다시 넣는다.

  3. 3

    루트에서 왼쪽 0, 오른쪽 1로 이동해 코드표를 만든다.

  4. 4

    원문을 코드로 치환하고 비트를 트리에서 읽어 복원한다.

핵심 개념 및 실무 적용 분야

✓DEFLATE: LZ77 토큰의 리터럴/길이와 거리 기호 부호화.
✓베이스라인 JPEG: 양자화된 계수의 기호를 허프만 코드로 표현.

참고 자료

개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.