[정보이론] 허프만 코드의 optimal 판단 / Huffman code optimal

들어가기 앞서

https://programming119.tistory.com/75

[알고리즘] 허프만 코드와 그리디 알고리즘 / Huffman code and greedy algorithm

허프만 코드에 대해 모르신다면, 참고해주세요!

 

허프만 코드의 Optimal 세 조건

코드화된 distribution이 있을 때, 다음과 같은 세 조건을 모두 만족시키면 Optimal 입니다.

 

 

1. 코드길이는 확률값과 반비례 한다. (코드 길이가 길수록, 확률 값은 작야아 한다는 뜻입니다.)

 

예시 )

11100 에 해당하는 확률 : 1/2

0 에 해당하는 확률 :  1/8  

=> NON-Optimal

 

 

2. 두개의 가장 긴 코드는 같은 길이이다.

- 만약 한 개의 가장 긴 코드의 길이가 있다면, 그것을 잘라내도 Optimal한 코드가 가능합니다.

 

예) 11111 , 1110 이 가장 긴 코드 2개라면,

1111, 1110 으로 줄여도 허프만 코드가 성립합니다.

 

 

3. 두개의 가장 긴 코드는 마지막 bit 만 다르다.

- 허프만 코드가 트리 형태로 구성된다는 점을 생각해본다면 직관적으로 이해할 수 있습니다.