[DS] 허프만 코드 : 힙의 응용

허프만 코드?

허프만 코드는 힙을 응용하여, 자료를 압축하는 가장 대표적인 방법 중 하나이다.

원리는?

핵심 키워드 : 최대 힙, 사용빈도, 가변길이

글자의 압축을 예로 들어 설명하겠다.
문자가 고정된 길이의 코드로 표현될 땐 비트의 수가 일정하다.

가변길이 코드를 사용한다면, 빈도가 잦은(자주 사용된) 문자에 대해서는 코드의 길이를 짧게 할당하여 사용되는 비트 수를 줄일 수 있다.

이를 위해 문자의 빈도를 키값으로 하는 노드들로 이진트리를 만들고 최대 힙으로 구성하는데, 이 트리는 아래의 규칙으로 만들어진다.

1. 가장 작은 빈도수의 두 노드를 골라 이진트리를 구성하는데, 이때 두 노드의 부모노드는 두 자식 노드의 합의 값으로 만들어진다.

   이 때, 두번째 부터는 직전에 만들어진 이진트리의 부모 노드까지 후보에 넣어서
   또 남은 노드들 중 제일 작은 두개의 노드로 이진트리를 구성한다.

2. 남은 트리에 대해 이를 반복하여 남는 노드가 없을때까지 수행하여 최종 이진트리를 만든다.

3. 모든 부모노드를 기준으로 left Edge에 대해 코드1을 부여, Right Edge에 대해 코드0을 부여

4. 이렇게 만들어진 빈도수의 최대 힙에 대해, leaf 노드에 위치한 각각의 알파벳까지 이어지는 edge들의 코드를 일렬로 나열하여 해당 알파벳의 가변길이 코드로 할당한다.

5. 해당 최대 힙은 빈도수가 높은 문자일수록 짧은탐색과정을 거치도록 구성되었기에 높은 빈도수의 문자는 짧은 가변길이 코드를 받아, 결과적으로 비트수가 적게 할당된 압축상태가 된다.

허프만 코드의 규칙

1. 코딩된 비트열을 왼쪽에서 오른쪽으로 조사하여 하나의 일치하는 코드를 찾는다.
2. 해독을 위해 모든 가변길이코드가 다른 코드의 첫 부분이 아니어야 한다.
3. 허프만 코드 생성을 위해 이진트리를 사용한다.

허프만 코드 트리 생성 과정을 보여주는 프로그램

def make_tree(freq):
	heap = MinHeap() #생성이 아닌, 생성과정 보여주는 프로그램이므로 MinHeap()사용
    for n in freq :
		heap.insert(n)
        
        for i in range(1, len(freq)) :
        e1 = heap.delete()
        e2 = heap.delete()
        heap.insert(e1 + e2)
        print(" (%d + %d) % (e1, e2))

### TEST
label = ['E','T','N','I','S']
freq = [15,12,8,6,4]
make_tree(freq)

Ref : 2022 1st, Data Structure, Ajou univerty