Huffman Code

사용자 삽입 이미지Huffman Code는?
디지털 전송에서 평균 부호의 길이를 가장 짧게 할 수 있는 가변 길이 부호(variable length code)의 하나.
신호의 발생 빈도를 고려해서 Code를 배정하는 방법으로, 빈도수가 높으면 Code의 길이를 짧게,
빈도수가 낮으면 Code 길이를 길게 배정한다. 이렇게 배정을 하면 데이터의 손실없이 전체 크기를 줄이는
효과를 가져오게 된다. Fax나 JPEG, MPEG등 각종 정보 압축 규격으로 많이 사용되고 있다.

총 1000개의 글자가 있다고 가정하고, 글자를 3bit로 표현할 경우 총 3000bit를 필요로 한다.
하지만, Huffman code를 사용하게 되면 2180bit를 차지하므로 약 2/3로 압축된 것을 알 수 있다.

    글자    빈도    고정      가변
     a:     450개,   000,      0
     b:     250개,   001,      101
     c:     120개,   010,      100
     d:     100개,   011,      111
     e:      80개,   100,      1101

Huffman Code 만드는 법

사용자 삽입 이미지(a) 코드를 발생 빈도 기준으로 오름차순 정렬한다.

(b) 가장 발생 빈도가 낮은 코드를 묶어서 하나의 가지를 만들고, 가지의 위쪽에 빈도의 합을 적는다.
     빈도가 낮은 코드의 마지막 bit를 ‘0’과 ‘1’로 배정한다.

(c) 묶은 가지를 기준으로 오름차순 정렬을 수행해서, 빈도가 낮은 코드가 2개 이상이면 새로운 가지를 만든다.
     처음 만들어진 가지의 빈도 합이 14이고, 그 합보다 낮은 코드가 b(13)와 c(12)이 있으므로 이 둘을 하나의
     가지로 만든다.

(d~e) (a)부터 (c)의 과정을 반복해서 수행한다.

(f) Huffman tree로 모든 Code가 묶어지면, 가지를 따라 내려오면서 코드를 배정하면 된다.
    가지의 시작점이 상위 bit에 해당한다.

* 참고: http://en.wikipedia.org/wiki/Huffman_coding, http://yatoyato.tistory.com/1015
          http://www.cs.fsu.edu/~cop4531/slideshow/chapter17/17-3.html

You may also like...

댓글 남기기