허프만 코드와 허프만 알고리즘

  • 이진 코드 (binary code)

    • ASCII / UNICODE와 같은 fixed-length 이진 코드
    • variable-length 이진 코드

  • 최적 이진 코드 문제 (optimal binary code)

    • 주어진 파일에 있는 문자들을 이진코드로 표현할 때 필요한 최소한의 이진 코드는?

  • 전치 코드 (prefix code)

    • 한 문자의 코드 워드가 다른 문자의 코드 워드의 앞부분이 될 수 없다
      → 01이 ‘a’의 코드워드라면 011은 ‘b’의 코드워드가 될 수 없다
    • 모든 전치코드는 리프노드가 코드 문자인 이진 트리로 표현 가능하다
    • 파일을 디코딩 할 때 뒷부분을 미리 볼 필요가 없음

  • 허프만 알고리즘 : 허프만 코드에 해당하는 이진 트리를 구축하는 Greedy approach

    1
    2
    3
    4
    5
    6
    7
    // n: 주어진 데이터 파일 내 문자의 개수
    // PQ: **빈도수가 낮은 노드를 먼저 리턴하는** 우선순위 큐(min-heap)
     1. PQ는 빈도수로 오름차순 정렬되어 있다
     2. PQ에서 두 개의 인자를 pop하여 처음 pop한 인자(p)를 left 노드로, 
        다음 인자(q)를 right 노드로 하는 새 노드를 구축한다
     3. 새 노드의 빈도수는 자식 노드(p, q)의 빈도수의 합이 된다
     4. 이 노드를 PQ에 다시 삽입한다 (오름차순에 맞게 위치함)

  • 최적 이진 코드를 위한 이진 트리의 구축

    • 데이터 파일을 인코딩하는 데 필요한 비트 수 계산
    • 주어진 이진트리는 T
    • {v1, v2, …, vn} : 데이터 파일 내 문자들의 집합
    • frequency(vi): 문자 vi가 파일 내에서 나타나는 빈도수
    • depth(vi): 이진 트리 T에서 문자 vi 노드의 깊이
    • bits(T) = 모든 frequency(vi) * depth(vi) 의 합 (0 < i < n)

파이썬으로 허프만 코드와 허프만 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class HuffNode:

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

    def preorder(self):
        print(self.freq, end=" ")
        if(self.left is not None):
            self.left.preorder()
        if(self.right is not None):
            self.right.preorder()
    
    def inorder(self):
        if(self.left is not None):
            self.left.inorder()
        print(self.freq, end=" ")
        if(self.right is not None):
            self.right.inorder()

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]

# 파이썬에는 Priority Queue가 있어 이 자료구조를 사용할 것