허프만 코딩

허프만 코딩(Huffman Coding)은 데이터 압축에서 사용되는 무손실 압축 알고리즘 중 하나로, 변장 길이 부호(Variable-Length Code)를 이용하여 빈도수가 높은 문자에는 짧은 코드, 빈도수가 낮은 문자에는 긴 코드를 할당하는 방식이다. 그리디 알고리즘(Greedy Algorithm)을 기반으로 최적의 접두사 코드(Prefix Code)를 생성한다.

개요

허프만 코딩은 주어진 문자 집합에서 각 문자의 출현 빈도(Frequency)를 기반으로 최적의 이진 트리를 생성하는 방식으로 동작한다.

• 자주 등장하는 문자
  • 짧은 이진 코드 할당.
• 드물게 등장하는 문자
  • 긴 이진 코드 할당.
• 결과적으로 압축된 데이터의 크기가 최소화됨.

동작 과정

허프만 코딩 알고리즘은 다음과 같은 방식으로 동작한다.

1. 각 문자의 빈도를 기반으로 우선순위 큐(Priority Queue)에 노드를 삽입.
2. 빈도수가 가장 낮은 두 노드를 선택하여 하나의 노드로 합침.
3. 합쳐진 노드의 빈도수는 두 노드의 빈도수를 합한 값으로 설정.
4. 위 과정을 반복하여 최종적으로 하나의 허프만 트리(Huffman Tree)를 생성.
5. 트리의 각 경로를 따라 0과 1을 할당하여 최적의 부호를 생성.

예제

다음과 같은 문자와 빈도가 주어졌을 때, 허프만 코딩을 적용한다.

문자	빈도수
A	5
B	9
C	12
D	13
E	16
F	45

허프만 트리 구축 과정

1. 우선순위 큐에 각 문자와 빈도를 삽입.
   • Q=[(A,5), (B,9), (C,12), (D,13), (E,16), (F,45)]
2. 빈도수가 가장 작은 두 노드(A:5, B:9)를 결합 → 새 노드(14).
   • (A+B,14) (C,12) (D,13) (E,16) (F,45)
3. 다음으로 빈도수가 작은 두 노드(C:12, 새 노드(14))를 결합 → 새 노드(26).
   • (A+B,14) (C+D,25) (E,16) (F,45)
4. 위 과정을 반복하여 최종적으로 허프만 트리를 생성.
   • (A+B+E,30) (C+D,25) (F,45)
   • (C+D+A+B+E,55) (F,45)
   • (F+C+D+A+B+E,100)
5. 아래와 같이 트리가 그려진다. 여기서 루트에서 출발하여, 왼쪽으로 갈 때 마다 0, 오른쪽은 1로 계속 이어나가다 보면 아래와 같이 코드가 만들어진다.

         (100)
          (F)
        /     \
      (45)    (55)
            /      \
         (25)      (30)
        /    \     /    \
     (12)  (13)  (14)  (16)
     (C)   (D)   (A+B)  (E)
                 /    \
              (5)    (9)
              (A)    (B)

완성된 허프만 코드

문자	허프만 코드
A	1100
B	1101
C	100
D	101
E	111
F	0

• 예를 들어 A는 루트에서 오른쪽, 오른쪽, 왼쪽, 왼쪽으로 가서 도달하였으므로 1100이 된다.
• A+B=14 등의 중간 과정은 사용하지 않는다.

코드 예제

허프만 코딩을 구현하는 Python 코드:

import heapq

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def huffman_coding(frequencies):
    heap = [Node(char, freq) for char, freq in frequencies.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)

    return heap[0]

def build_huffman_code(root, code="", huffman_dict={}):
    if root is not None:
        if root.char is not None:
            huffman_dict[root.char] = code
        build_huffman_code(root.left, code + "0", huffman_dict)
        build_huffman_code(root.right, code + "1", huffman_dict)
    return huffman_dict

# 예제 실행
frequencies = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}
root = huffman_coding(frequencies)
huffman_dict = build_huffman_code(root)

print(huffman_dict)

출력 결과 예시:
{'F': '0', 'C': '100', 'D': '101', 'A': '1100', 'B': '1101', 'E': '111'}

시간 복잡도

허프만 코딩의 시간 복잡도는 다음과 같다.

• 우선순위 큐 삽입 및 삭제
  • O(n log n)
• 트리 생성 및 탐색
  • O(n log n)
• 전체 알고리즘 시간 복잡도
  • O(n log n)

응용

허프만 코딩은 다양한 데이터 압축 기법에서 사용된다.

• 파일 압축
  • ZIP, GZIP 등의 데이터 압축 알고리즘에서 사용.
• 이미지 및 영상 압축
  • JPEG, MPEG에서 사용되는 엔트로피 부호화 기법.
• 네트워크 데이터 전송
  • 데이터 전송 시 전송량을 줄이기 위한 최적의 부호화 방식.

한계

허프만 코딩은 최적의 압축을 제공하지만 몇 가지 단점이 있다.

• 가변 길이 부호로 인해 디코딩이 복잡함.
• 빈도수가 실시간으로 변하는 경우 적용하기 어려움.
• 최적의 압축률을 보장하지 않으며, 경우에 따라 산출된 코드 길이가 예상보다 길어질 수 있음.

같이 보기

• 그리디 알고리즘
• 동적 계획법
• 무손실 데이터 압축
• 최소 신장 트리

참고 문헌

• Huffman, David A. "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE, 1952.
• Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.