허프만 부호화

1단계 : 주어진 정보 I를 구성하는 심볼의 확률 계산

2단계 : 1단계 심볼들의 확률로부터 Huffman 이진트리 (Binary Tree) 구성

1 : (심볼, 확률) 쌍으로 구성된 리스트 L를 만듦

2 : 리스트 L에 있는 (심볼, 확률)로 구성된 노드를 갖는 그래프 G 생성

3-1 : 리스트 L에 있는 확률이 가장 적은 두 개의 노드 C1, C2를 자식 노드로 갖는 부모 노드 P를 그래프 G에 추가

3-2 : 부모 노드 P의 확률 값은 두 자식 노드 C1, C2의 확률 값을 더함

3-3 : 리스트 L에 부모 노드 P를 추가하고 자식 노드 C1, C2 삭제

4 : 부모 노드 P의 확률이 1이 될 때까지 3단계 반복

5 : 자식 노드가 있는 모든 노드의 왼쪽 자식 가지에 0을 오른쪽 자식 가지에 1을 부여, 생성된 그래프 G가 Huffman 이진트리

 

3단계 : 2단계에서 구성된 Huffman Tree로 부터 Huffman Table 구성 

1 : Huffman Table은 각 심볼에 해당하는 이진코드 (Binary Code)가 할당됨

2 : 심볼의 이진코드 (Binary Code)는 Huffman Tree에서 루트 노드에서 출발해서 심볼에 도착할 때 거치는 순서대로 가지들의 이진 값들로 구성됨 

4단계 : 3단계에서 구성된 Huffman Table에 따라 정보 I의 각 심볼 부호화