허프만 코드

1. 개요[편집]

---

허프만 코드(Huffman's Code)는 허프만 알고리즘에 의해 생성된 최적 이진코드를 말한다. 허프만 알고리즘(Huffman's Algorithm)은 허프만 코드에 해당하는 이진트리를 구축하는 그리디 알고리즘이다.

2. 최적 이진코드[편집]

---

최적 이진코드(Optimal Binary Code)는 주어진 파일에 있는 문자들을 이진코드로 표현할 때 필요한 비트의 수가 최소가 되는 이진트리를 구축하는 최적화 문제의 일종이다.

주어진 문자열을 위한 최적 이진트리를 구축하기 위해서는 전치 코드(Prefix Code)로 구현해야 한다. 전치 코드란 길이가 변하는 가변 길이 이진코드의 특수한 형태로서, 한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수는 없다. 예를 들어, 'a'라는 문자의 코드워드가 '01'이라면, 'b'라는 문자의 코드워드는 011이 될수는 없다. 01이 011의 앞부분과 겹치기 때문이다.

전치코드로 이진트리를 만들면 가변 길이 이진코드를 디코딩(파싱)할 때 뒷부분을 미리 봐야 할 필요가 없다는 장점이 있다. 전치코드는 리프노드가 코드문자이고, 내부노드는 이진수의 방향을 표현하는 이진트리로 표현 가능하다.

3. 허프만 알고리즘[편집]

---

허프만 알고리즘은 허프만 코드를 구축하기 위한 그리디 알고리즘이다. 주어진 데이터 파일 내의 문자의 개수가 n이라고 할 때, 이 데이터 파일을 이진코드를 인코딩(압축)하기 위한 최적의 이진트리 T를 구축한다.

허프만 알고리즘은 각 문자가 나타나는 빈도 수에 따라 우선순위 큐를 사용하여 다음과 같이 생성할 수 있다.

class HuffNode:
    def __init__ (self, symbol, freq):
        self.symbol = symbol
        self.freq = freq
        self.left = None
        self.right = None

def huffman (n, PQ):
    for _ in range(n - 1):
        p = PQ.get()[1]
        q = PQ.get()[1]
        r = HuffNode(' ', p.freq + q.freq)
        r.left = p
        r.right = q
        PQ.put((r.freq, r))
    return PQ.get()[1]