허프만 코딩 편집하기

'''허프만 코딩'''(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
|}

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

===완성된 허프만 코드===
{| class="wikitable"
|-
!문자
!허프만 코드
|-
|A||1100
|-
|B||1101
|-
|C||100
|-
|D||101
|-
|E ||111
|-
|F||0
|}

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

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

[[분류:알고리즘]]