허프만 코딩 편집하기

'''허프만 코딩'''(Huffman Coding)은 '''데이터 압축'''에서 사용되는 무손실 압축 알고리즘 중 하나로, '''변장 길이 부호(Variable-Length Code)'''를 이용하여 빈도수가 높은 문자에는 짧은 코드, 빈도수가 낮은 문자에는 긴 코드를 할당하는 방식이다. '''그리디 알고리즘(Greedy Algorithm)'''을 기반으로 최적의 접두사 코드(Prefix Code)를 생성한다.
==개요==
허프만 코딩은 주어진 문자 집합에서 각 문자의 '''출현 빈도(Frequency)'''를 기반으로 최적의 이진 트리를 생성하는 방식으로 동작한다.
*자주 등장하는 문자 → 짧은 이진 코드 할당.
*드물게 등장하는 문자 → 긴 이진 코드 할당.
*결과적으로 압축된 데이터의 크기가 최소화됨.
==동작 과정==
허프만 코딩 알고리즘은 다음과 같은 방식으로 동작한다.
#각 문자의 빈도를 기반으로 우선순위 큐(Priority Queue)에 노드를 삽입.
#빈도수가 가장 낮은 두 노드를 선택하여 하나의 노드로 합침.
#합쳐진 노드의 빈도수는 두 노드의 빈도수를 합한 값으로 설정.
#위 과정을 반복하여 최종적으로 하나의 허프만 트리(Huffman Tree)를 생성.
#트리의 각 경로를 따라 0과 1을 할당하여 최적의 부호를 생성.
==예제==
다음과 같은 문자와 빈도가 주어졌을 때, 허프만 코딩을 적용한다.
{| class="wikitable"
|-
!문자!!빈도수
|-
|A||5
|-
|B||9
|-
|C||12
|-
|D||13
|-
|E||16
|-
|F||45
|}
###허프만 트리 구축 과정:
#우선순위 큐에 각 문자와 빈도를 삽입.
#빈도수가 가장 작은 두 노드(A:5, B:9)를 결합 → 새 노드(14).
#다음으로 빈도수가 작은 두 노드(C:12, 새 노드(14))를 결합 → 새 노드(26).
#위 과정을 반복하여 최종적으로 허프만 트리를 생성.

###허프만 코드:
{| class="wikitable"
|-
!문자!!허프만 코드
|-
|A||1100
|-
|B||1101
|-
|C||100
|-
|D||101
|-
|E||111
|-
|F||0
|}
==코드 예제==
허프만 코딩을 구현하는 Python 코드:<syntaxhighlight lang="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)
</syntaxhighlight>
 출력 결과 예시:
 {'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.