Huffman Coding

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Prefix Code

Symbol을 인코딩하는데 있어, 고정된 길이로 인코딩할 수 있지만, symbol 빈도수가 클수록 길이를 작게한다면 더 효율적일 것이다. Huffman coding은 symbol frequency가 주어졌을 때, symbol에 code를 할당하는 알고리즘이다.

 

Prefix code : 1, 0으로 이루어진 code에서, 하나의 code가 다른 하나의 prefix가 되지 않는 code이다.

 

ABL (Average Bits per Letter) 

 

Prefix code는 아래 그림과 같이 tree의 leaves에 할당함으로써 표현할 수 있다.

 

 

 

중간 노드에 할당이 될 수 없는데, 할당되면 아래 노드의 prefix가 되어버리기 때문이다.

 

모든 node가 2개의 children을 가지면 full이라 한다.

그리고 Prefix code가 full이면 optimal이다.

 

Pf ) u가 1개의 children을 가진다 하자.

1. u가 root일 경우, u를 지우고 그 children을 root로 하면 된다.

2. u가 root가 아니어도 마찬가지로 아래 children을 올려서 더 depth를 짧게 만들 수 있다.

 

 

 

Huffman Encoding

Observation 1 : lowest frequency를 가지는 item은 lowest level에 있다.

Observation 2 : n > 1일 때, lowest level은 적어도 2개이상의 leaves를 가진다.

Observation 3 : 같은 level에서 item의 종류는 관계없다 (서로 바꿔도 됨)

 

 

 

 

* Time complexity : $O(n^2)$, S를 Priority queue로 구현하면 $O(nlogn)$

 

 

Claim : $ABL(T') = ABL(T) - f_w$

Tree T'가 있고 subtree w를 추가한 tree를 T라 하자.

그러면 위의 공식이 성립한다.

 

 

Pf ) 

 

 

 

Claim : Huffman code는 minimum ABL을 달성한다.

 

Pf ) 귀납법으로 증명

n = 2는 tree를 바로 만들 수 있으므로 자명.

Hypothesis : size n-1인 T'는 optimal이라 가정

 

T가 optimal하지 않다고 하자. 그러면 ABS(Z) < ABL(T)인 tree Z가 존재한다.

그리고 Observation에 의해 lowest frequency인 y, z는 leaves로 존재한다.

Z'는 Z에서 y, z를 delete한 tree라고 하자. 그리고 y, z의 parent를 w라고 하자.

위의 성질로 인해, $ABL(Z') = ABL(Z) - f_w,  ABL(T') = ABL(T) - f_w$

이는, $ABL(Z') < ABL(T')$가 되므로, 위의 가정에 모순이다.