[알고리즘] 탐욕법 - 허프만 코드 (Greedy Approach - Huffman Code)

1. 데이터 압축 문제 (The problem of data compression)

 

데이터 파일을 효율적으로 encoding 하기 위한 방법을 찾아내는 문제입니다.

데이터 파일은 통상적으로 이진 코드 (binary code)로 표현됩니다.

또한 각각의 이진 문자열은 코드 워드 (code word)라는 유일한 이진 코드로 표현됩니다.

 

이때 "ababcbbbc"라는 문자열이 있다고 가정하면, 문자의 집합은 {a, b, c}가 됩니다.

이때 이 문자열을 이진 코드로 표현하는 방법이 있습니다.

 

1.1 길이가 고정된 이진 코드 (fixed-length binary code)

 

길이가 고정된 이진 코드는 각각의 문자를 표현하는 비트의 개수가 일정합니다.

{a, b, c}를 표현하기 위해서는 단지 3개의 비트만 있으면 됩니다.

 

 

1.2 길이가 변하는 이진 코드 (variale-length binary code)

 

길이가 변하는 이진 코드는 문자를 표현하는 비트의 개수가 가변적입니다.

이 방법을 사용하면 비트의 개수가 고정된 것 보다 좀 더 효율적인 방식을 만들 수 있습니다.

 

 

 

이렇게 두 가지 방법이 있는데, 길이가 고정된 이진 코드를 사용하여 해당 문자열을 이진 코드로 부호화해보겠습니다.

a : 00, b : 01, c : 10이라고 한다면, 해당 문자열은

00 01 00 01 10 01 01 01 10이 되므로 해당 문자열을 표현하기 위해서는 18개의 비트가 필요하다는 것을 알 수 있습니다.

 

다른 방법으로 길이가 변하는 이진 코드를 이용해서 부호화해보겠습니다.

이때, 각 문자마다 나오는 빈도수가 다르므로 빈도수가 높은 b는 0, a : 10, c : 11의 code word를 넣겠습니다.

따라서 문자열은 10 0 10 0 11 0 0 0 11이므로 총 13개의 비트로 문자열을 표현할 수 있습니다.

 

따라서 최적 이진 코드(Optimal Binary Code)는 문자들을 이진 코드로 표현하는데 필요한 비트의 개수가 최소가 되는 이진 문자 코드(Binary Character Code)를 찾는 것입니다.

 

우선 전치 코드 (Prefix Code)를 먼저 보고, 허프만 코드를 보겠습니다.

---

2. 전치 코드 (Prefix Code)

 

 

길이가 변하는 이진 코드의 일종으로 전치 코드 (Prefix Code)가 있습니다.

이때 Prefix code는 한 문자의 code word가 다른 문자의 code word의 앞부분이 될 수 없습니다.

즉 a : 10이라면, b는 1이 될 수 없습니다.

따라서 길이가 고정된 코드 역시 전치 코드의 일종이라 볼 수 있습니다.

 

전치 코드는 잎이 코드 문자로 구성된 이진트리로 표현할 수 있습니다.

이때 Prefix Code의 장점은 파일을 Parsing 할 때 현재 parsing 하는 지점의 앞부분까지 볼 필요가 없습니다.

 

왜냐하면 이처럼 이진 파일을 처음부터 훑어갈 때, 0이 나오는지 1이 나오는지에 따라 그냥 트리의 왼쪽 오른쪽으로 이동만 하면 되기 때문입니다.

left, right 새끼 노드가 None일 때까지만 이동하면 됩니다.

예를 들어, 0으로 시작하면 필연적으로 a이고, 1로 가면 오른쪽 트리로 갔다가 0이 나면 b, 1이 나오면 c기 때문입니다.

---

3. 허프만 코드 (Huffman Code)

 

 

이때 a가 16번, b가 10번, c가 2번이 나온다고 가정해봅시다.

 

만약에 길이가 고정된 이진 코드라면, 16 * 2 + 10 * 2 + 2 * 2 = 56개의 비트가 필요합니다.

 

또한 만약에 Prefix Code라면 16 * 1 + 10 * 2 + 2 * 2 = 40개의 비트가 필요합니다.

 

이때 필요한 비트의 수는 다음의 식으로 구할 수 있습니다.

\(bits(T) = \sum_{i = 1}^{n} frequency(v_i) \times  depth(v_i)\)

 

이때 {v_1, v_2, ... ,v_n}는 파일에 있는 문자의 집합이고, frequency(v_i)는 v_i가 나오는 횟수이고, depth(v_i)는 T에서 v_i의 깊이입니다.

 

이때 우리는 최적의 이진 코드 트리를 만들어서 bits(T)를 최소하 하는 것이 목표입니다.

 

이때 허프만 알고리즘 (Huffman Algorithm)은 탐욕법을 이용해서 최적 코드에 해당하는 이진트리를 만들어서 최적 이진 문자 코드를 만들어냅니다.

 

이때 이 알고리즘이 만들어내는 코드를 허프만 코드 (Huffman Code)라고 합니다.

 

이때 우리는 min-heap을 이용하여 priority queue를 만들어야 합니다.

이때 priority queue에서는 빈도수가 낮은 문자가 우선순위가 가장 높은 원소이고, 우선순위가 가장 높은 원소가 먼저 빠져나갑니다.

 

문제의 순서는 다음과 같습니다

1. 우선순위가 높은 두 개의 원소를 뺀다.
2. 두 개의 원소를 자식으로 가지는 원소를 만든다. 해당 원소의 빈도수는 자식 빈도 수의 합과 같다.
3. 새롭게 만든 원소를 다시 우선순위 큐에 넣는다.
4. 원소의 개수가 n 개라면 n-1번 반복한다.

슈도 코드로 작성하면 다음과 같습니다.

n = number of characters in the file
Arrange n pointers to nodetype in a PQ

for i in range(n-1):
	remove(PQ, p)
    remove(PQ, q)		# 빈도수가 작은 두 개를 꺼냄
    r = new nodetype		# 새로운 노드를 만듬
    r.left = p
    r.right = q
    r.frequency = p.frequency + q.frequency		# 자식의 빈도수를 합함
    insert(PQ, r)		# 다시 집어 넣음
    
remove(PQ, r)
return r

간단하죠?

 

그림으로 표현하면 다음과 같습니다.

 

---

4. encoded binary code를 decode 하는 법

 

 

문자열을 encode 해서 binary code로 만들었다면, 이제 다시 해독하는 법을 알아야 합니다.

 

만약 encoded binary string이 00100111101101111이고, 최적 이진 코드 트리가 위의 트리와 같다고 하겠습니다.

그러면 이진 문자열을 그대로 따라가면서 트리에 따라 해독하면 됩니다.

그러므로 문자열은 a f d b c e가 됩니다.

 

 

감사합니다.

 

 

지적 환영합니다.