[Data] Huffman`s Algorithm

이전 포스트에서 일종의 binary tree형식으로 bit을 나열해서 Variable Length Encoding을 구한다고 언급했었는데, Tree를 만드는데도 일종의 규칙같은게 있다. Huffman`s Algorithm이라는 것인데, 한번 잠깐 소개해보고자 한다. 우선 Logic은 다음과 같다. 

일단 앞의 예제를 그대로 가지고 오는 것을 생각해보자. 위에서 맨처음 스텝에 언급한 것처럼 가장 작은 확률을 가진 symbol 2개를 바탕으로 하나의 subtree를 만든다. 

그러면 이렇게 된다.( 우선 C와 D의 순서는 상관없다. 같은 확률을 가지고 있기 때문에 표현하기 좋게 순서대로 나열한 것일뿐 D가 먼저와도 상관없다.) 그러면 이 subtree내의 확률들을 합쳐서 그 다음 노드에 정의를 하고 그 값을 현재 남아 있는 값들과 비교해본다.

그러면 이때 가장 가까운 값이 A가 되는데 A가 가진 확률 자체가 C와 D의 합보다 크기 때문에 C와 D를 합친 subtree를 왼쪽에, 큰 값을 가진 A를 오른쪽에 배치한다.

역시 동일한 방식을 적용하고 상위노드로 올리면 값은 1/2이 되고, 그 걸 B가 가진 확률과 비교해야 한다. 우선 동일하긴 하지만 A가 가진 자식 노드들의 크기로 인해서 B를 왼쪽에, A를 오른쪽에 놓게 된다.

짠! Huffman`s algorithm을 통해서 binary tree를 만들어 보았다.

그런데 사실 이렇게 단일 symbol에 대한 Tree를 만들수도 있지만, 조금만 더 생각해보면 연속된 symbol에 대해서도 각각의 확률을 구하고 이를 바탕으로 Tree를 만들수도 있게 된다. 예를 들어서 이렇게 되는 것이다. 

이걸 바탕으로 예상 정보표현량을 구해보면 대략 1.646 bits 이라는 값이 나오게 되는데, 한 symbol만을 고려했을 때 나온 예상 정보 표현량인 1.667 bit에 비해서 값이 작아진 것을 확인할 수 있다. 이와 같은 개념을 확장해보면 연속된 패턴을 가지고 Huffman`s algorithm을 사용하면 적은 bit만 가지고 정보를 표현할 수 있게 된다. 이런 원리는 보통 파일 압축 방식에 많이 적용되는 편이고, 조금더 궁금한 사람이 있다면 흔히 LZW 방식이라고 하는 Lempel-Zip-Welch 방식에 대해서 찾아볼것을 권한다.