Huffman encoding

Huffman encoding

 

Value 값이 1,2,3,4,5,6 이 있고 그 출현 빈도가 아래와 같다면

 

Frequency  Value
   5         1
   7         2
  10         3
  15         4
  20         5
  45         6

 

huffman tree를 이용하여 encoding을 할 수 있다.
각 value의 출현 빈도로 정렬하여야 하며 가장 Frequency가 작은것 부터 시작한다.
가장 Frequency가 작은 두 값의 Frequency의 합으로 부모 노드를 만든다.

* 소괄호안의 값은 Value 이다.

 

      12(*)
     /    ＼
   5(1)    7(2)

 

이제 두 value 를 list에서 제거하고 정렬한다. 그 값은 아래와 같다.

 

  10(3)
  12(*)
  15(4)
  20(5)
  45(6)

 

다시 반복하고 반복하여 하나의 value가  남을때 까지 위와 같이 반복한다.

 

       22(*)
      /    ＼
   10(3)    12(*)
              /    ＼
            5(1)    7(2)

 

두 값을 제거한 list는 아래와 같이 된다.

 

  15(4)
  20(5)
  22(*)
  45(6)

 

다음

 

       35(*)
      /    ＼
   15(4)    20(5)

 

list는

 

  22(*)
  35(*)
  45(6)

 

다시 두 value 는

 

                    57(*)
                   /    ＼
         /￣￣￣         ￣￣￣＼
       22(*)                       35(*)
      /    ＼                      /    ＼
   10(3)    12(*)             15(4)    20(5)
             /    ＼
          5(1)    7(2)

 

list는

 

  45(6)
  57(*)

 

다음

                                 (left 0)     102(*)     (right 1)
                                              /    ＼
                    /￣￣￣￣￣￣￣￣￣          ￣＼
                  57(*)- is 0                          45(6)- is 1
                 /    ＼
      /￣￣￣          ￣￣￣＼
   22(*)- is 00                35(*)- is 01
   /    ＼                      /    ＼
10(3)    12(*)             15(4)    20(5)
           /    ＼
         5(1)    7(2)

 

102 노드 하나만 남고 모두 끝났다.
이제 왼쪽은 0을 오른쪽은 1을 셋팅 해보자

 

 57(*) = 0
 45(6) = 1
 35(*) = 01
 22(*) = 00
 20(5) = 011
 15(4) = 010
 12(*) = 001
 10(3) = 000
  7(2) = 0011
  5(1) = 0010

 

 이로써 출현빈도(Frequency)가 가장 많은 값을 가장 적은 코드로 할당 하였다.