[AI정보이론] Data Compression - Huffman Code

 

 

Huffman Code - Binary Case

Huffman 코딩은 주어진 확률 분포에 따라 최적의 접두사 코드를 생성하는 방법이다

 

 

확률 변수가  X = {1, 2, 3, 4, 5} 이고,
각 값의 확률은  p(x) = {0.25, 0.25, 0.2, 0.15, 0.15} 라고 가정하면 위와 같은 결과가 나온다

 

진행과정
1. 초기 확률은 오름차순으로 정렬한다

2. 가장 작은 두 확률 합치기
3. 다시 정렬

4. 가장 작은 두 확률 합치기
5. 다시 정렬

6. 가장 작은 두 확률 합치기
7. 다시 정렬

8. 마지막으로 남은 두 확률 합치기

 

위 과정을 모두 거친 후 코드의 길이를 계산하면 2.3 bits가 나온다

< 0.5 + 0.5 + 0.4 + 0.45 + 0.45 = 2.3 >

 

 

 

Huffman Code - Ternary Case

Binary에서 Ternary로 확장하면 세 개의 가장 작은 확률을 가진 심볼들을 하나의 초심볼(supersymbol)로 결합한다

 

확률 변수가 X = {1, 2, 3, 4, 5}이고,
각 값의 확률은 p(x) = {0.25, 0.25, 0.2, 0.15, 0.15} 라고 가정하면 위와 같은 결과가 나온다

 

진행과정
1. 초기 확률은 오름차순으로 정렬한다

2. 가장 작은 3가지 확률 합치기
3. 다시 정렬

4. 마지막으로 남은 3가지 확률 합치기

위 과정을 모두 거친 후 코드의 길이를 계산하면 1.5 ternary digits 가 나온다

< 0.25 + 0.25 + 0.4 + 0.3 + 0.3 = 1.5 >

 

 

 

 

Huffman Code - DummySymbol

Huffman 코딩에서 심볼의 수가 충분하지 않은 경우,
적절한 개수로 맞추기 위해 더미 심볼(dummy symbol)을 추가하는 방법이 있다

 

 

확률 변수가 X = {1, 2, 3, 4, 5, 6}이고,
각 값의 확률은 p(x) = {0.25, 0.25, 0.2, 0.1, 0.1,  0.1} 라고 가정하면 위와 같은 결과가 나온다

 

진행과정
1. 심볼의 수가 6개로 더미 심볼을 추가해서 총 7개로 한다

2. 가장 작은 3가지 확률 합치기
3. 다시 정렬

4. 가장 작은 3가지 확률 합치기
5. 다시 정렬

6. 마지막으로 남은 3가지 확률 합치기

 

위 과정을 모두 거친 후 코드의 길이를 계산하면 1.7 ternary digits 가 나온다

< 0.25 + 0.25 + 0.4 + 0.2 + 0.3 + 0.3 + 0.0 = 1.7 >