허프만 코딩

허프만 코딩(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. 1. 1. 허프만 트리 구축 과정:
2. 우선순위 큐에 각 문자와 빈도를 삽입.
3. 빈도수가 가장 작은 두 노드(A:5, B:9)를 결합 → 새 노드(14).
4. 다음으로 빈도수가 작은 두 노드(C:12, 새 노드(14))를 결합 → 새 노드(26).
5. 위 과정을 반복하여 최종적으로 허프만 트리를 생성.

1. 1. 1. 허프만 코드:

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

코드 예제

허프만 코딩을 구현하는 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.