Greedy Algorithm-(2) Huffman Code

Huffman Code

• 데이터 압축을 위한 효율적인 encoding 방법
• text file을 표현하는데 variable-length binary code를 사용한다.

* variable-length binary code

-> 가변 길이 바이너리 코드: 다른 길이의 비트를 사용하여 각 문자를 표현

* Fixed-length binary code

-> 고정 길이 바이너리 코드: 같은 길이의 비트를 사용하여 각 문자를 표현

예) 아스키 코드

 

* Prefix Code

어느 코드도 다른 코드의 앞부분에 있지 않게 구성한 코드

Huffman Code란 결국?

-> prefix code이면서 가변길이 바이너리 코드인 코드를 최적이 되도록 

 

(문자 v가 나올 빈도 * 문자 v의 비트 길이)의 최소를 찾는 게 Huffman Code의 핵심

 

 

 

알고리즘 구현

각각의 문자가 n개의 싱글노드트리로 이루어졌다고 간주

1. 가장 적은 빈도를 가진 두 개의 트리를 병합

2. 하나의 싱글 트리가 될 때까지 1번 반복

 

for (i = 1; i < n; i++) {
    remove(PQ, p); // PQ는 Min priority queue
    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;

Public class nodetype
{
    char symbol;
    int frequency;
    nodetype left;
    nodetype right;
}

--> 시간 복잡도: 세타 n lg n

(priority queue 삽입, 제거에 l g n시간 걸림) * for문 n-1번

 

Min priority queue니깐 계속 알아서 정렬돔

depth: 문자 길이

노드에 적힌 숫자: frequecy

 

 

 

최적해인지 증명하기

1. 0번째 단계에서 싱글노드의 집합은 최적

2. i번째 단계에서 트리의 집합이 최적이라고 가정

3. i+1번째 단계에서 루트노드 u와 v가 합쳐짐

-> (1) 최적해 T에서 u의 부모와 v의 부모가 같은 경우: 증명 끝

(2)  최적해 T에서 u의 부모와 v의 부모가 다른 경우 

u와 w가 선택됨

노드 w와 노드 v를 바꾼 새로운 트리 T'을 만들자

cost(T')= cost(T)-f(v)*d(v)+f(w)*d(v)-f(w)*d(w)+f(v)*d(w)을 인수분해한 것

            = cost(T)+(d(w)-d(v))*(f(v)-f(w)) 

           <=cost(T)

T'가 최적해.

-> 바꾸면 전체 cost는 작거나 같다. 즉, 같다.

v와 w의 depth가 같았을 것