[Data] Variable Length Encoding

이전 포스트에서 정보의 표현량이 고정된 방식인 Fixed Length Encoding에 대해서 언급했다. 아마 그 이전 포스트에서도 언급한 바가 있겠지만, Fixed Length Encoding 기법은 변환하기 쉽고, 모든 경우의 수가 같을 때 사용되는 방법이라고 했었고, 이와 반대 급부로 비효율적으로 정보 표현이 낭비되는 케이스도 존재한다고 했었다. 그걸 어느정도 해결하는 방법이 이제 소개할 Variable Length Encoding이다.

 이름에서도 표현되는 것처럼 정보의 표현량이 고정되어 있지 않은 방식이며, 경우의 수가 각각 다를 때 이 표현 방식을 쓰게 되면 bit을 효율적으로 처리하면서 정보를 표현할 수 있다. 예를 들어서 다음과 같은 케이스가 있다고 가정해보자.

이와 같이 A, B, C, D가 나오는 확률이 각각 다르다(C, D는 같긴 하지만...). 이럴 때 어떤 한문자를 딱 뽑으면 어떤게 가장 많이 나올까? 당연히 B가 될 것이다. 하지만 A, C, D로 갈수록 뽑을수록 나올 확률이 적어질 것이다. 상식적으로 생각해보면 뭔가 확률이 적은것을 뽑기 원하면 그만큼 더 샘플을 더 많이 뽑아야 얻을수 있을 것이고, 그런 개념을 정보 표현량으로 적용해본다면 더 많은 bit으로 표현해야 그만큼 확률이 낮은 정보를 표현할 수 있게 될 것이다. 

 그런 개념을 적용한다면 상대적으로 확률이 큰 정보일 수록 표현하는 정보량은 적을 것이고, 반대는 정보 표현량이 많아야 한다. 그래서 그때 이걸 Binary Tree식으로 구별해서 표현한다고 이전 포스트에서 Variable Length Encoding을 잠깐 다룰때 언급했다. 일단 위의 정보량으로부터 Entropy를 구해보면 4가지 정보를 표현하는 데는 총 1.626 bit이 필요하다는 것을 계산할 수 있다. 

그러면 지금 구한 Variable Length Encoding을 구하게 되면 실질적으로 정보표현량의 평균은 얼마가 될까? 그건 그때 했던 것처럼 각각의 경우의 수에 확률을 곱해서 더해주면 되는데, 위와 같은 방식인 경우 평균 정보표현량은 1.667 bit이 된다.

만약 지금까지 배운 방식을 토대로 1000개의 symbol을 표현해본다고 가정해보자. 그러면 지금까지 1bit을 구하는데 필요한 평균정보평균량에 1000을 그냥 곱하면 되는 것이다. 그러면 다음과 같이

잘보면 Variable length Encoding 기법이 이전 포스트에서 다룬 Fixed Length Encoding 기법보다 적은 정보량으로 표현량을 가지고 정보를 표현할 수 있긴하지만, 그렇다고 최종적인 목표인 entropy에 비하면 아직 몇 bit 정도 손해보는 게 생긴다. 이걸 조금이라도 극복해내는게 지금 이런 것들을 다루는 목적이 되겠다.

출처: 6.004.1x Computation Structures - Part 1: Digital Circuits