Adaptive Huffman coding

Adaptive Huffman Coding ( Dynamic Huffman Coindg )

http://ben-tanen.com/adaptive-huffman/  <-- 설명이 정말 좋다!!

-------------------------------------------------------------------------------

[기존의 허프만 코딩]

Traditional Huffman Tree는 Frequency table를 보고 낮은 빈도수 가진 문자 2개씩 가져오면서 bottom to top으로 올라오면서 허프만 트리를 구성한다.

따라서 각 문자에 대한 빈도수를 얻기 위해 한번 읽고, 다시 한번 더 읽으면서 table을 참조하여 허프만 트리를 완성한다.

하지만 이같은 경우에는 두번 읽어야한다는 단점과, 한번에 모든 데이터가 주어지지 않고 실시간으로 input 값이 들어오는 상황에서는 사용할 수 없다는 단점이 있다.

-------------------------------------------------------------------------------

[동적 허프만 코딩] - FGK Tree

이에 동적으로 허프만 트리를 구성하는 Adaptive Huffman Coding에 대해 알아보자.

(Dynamic Huffman Coding 이라고도 부름.)

이하, 동적 허프만 코딩으로 통일.

동적 허프만 트리는 실시간으로 만들어지며, input 값을 읽고 트리를 만드는 과정이 동시에 이루어진다. (두번 읽지 않는다!)

각 문자에 대한 빈도수를 다 알지 못하므로 root에서 시작해서 아래로 잎을 만들며 Tree를 구성한다.

(기본 허프만 코딩은 빈도수 테이블을 기반으로 아래에서 위로 트리를 구성했다.)

주의 :

"Root를 제외한 모든 노드들은 형제를 가진다"라는 Sibling Property를 만족시키기 위해 새롭게 추가되는 노드의 sibling node로  null node를 사용한다.

sibling property의 또 다른 조건인 left to rignt / bottom to top 방향으로 값이 커진다는 조건도 만족시켜야 한다.

1. 새롭게 추가되는 문자라면 null node를 사용하며 트리에 추가한다.

( 맨 아래 잎의 좌쪽 노드에 추가하면 된다. )

2. 이미 있는 요소라면 단순히 Frequency를 1 증가시킨다.

3. Frequency를 증가시켰을 때 left to rignt / bottom to top 조건에 위배된다면 두 노드를 swap한다.