[펌] 허프만코드

invalid-file

10.2.2 Huffman 부호화

Huffman 부호화의 기본 개념은 각 단위 정보를 표현하는 비트 수를 단위 정보 들의 출현 빈도를 기반으로 할당하는 것임

빈도가 높은 정보는 적은 비트 수를 사용하여 표현하고, 빈도가 낮은 정보는 비트 수를 많이 사용하여 표현해서 전체 데이터의 표현에 필요한 비트의 양을 줄임

대표적인 가변 길이 코드이며, 영상 압축에 많이 사용됨

첨부파일!!

허프만(Huffman) 압축기법

허프만 압축기법은 1954년 허프만에 의해 제안된 압축 방식으로 오늘날에도 널리 이용되고 있다. 이 기법은 정보원 데이터내의 각 문자에 대한 발생빈도를 조사해 자주 나타나는 문자에는 보다 짧은 부호어를, 그리고 잘 나타나지 않는 문자에는 더 긴 부호어를 할당함으로써, 전체 압축후 부호어의 길이를 원래의 정보원 길이보다 더 축소시킬 수 있는 통계적 특성을 이용한 압축기법이다.
이 방식의 일례를 그림 6-6에 나타내었다.

<그림 6-6> 허프만 압축기법

그림의 경우에 있어서는 원래의 정보원 데이터 내의 각 문자들은 3비트의 고정된 길이로서 표현되지만 허프만 압축기법에 의해 가장 자주 나타나는 A라는 문자에는‘0’, 즉 1비트의 부호어가, 그리고 가장 자주 나타나지 않는 문자인 H에는‘111111’이라는 6비트의 부호어가 할당되어 있다. 따라서 압축전과 압축후의 전체 데이터길이의 비율을 계산한 결과 압축에 의해 20%의 축소효과를 가져왔음을 알 수 있다. 허프만 압축기법을 적용한 압축 방식으로는 현재 팩시밀리 통신의 표준으로서 권고되고 있는 수정 허프만부호가 있다.

팩시밀리 통신은 앞에서도 언급한바와 같이 이미지정보이므로 서류의 한 줄당 최소 1728비트의 데이터가 필요하게 된다. 수정 허프만 기법은 각 줄당 1728개에 달하는 데이터가 모두 흑(‘1’인비트)과 백(‘0’인비트)으로 이루어져 있으며 또 이미지정보의 경우 흑과 백의 분포가 상호연관되어 있는 점에 착안, 각 줄당 흑과 백의 반복갯수마다 앞의 허프만 기법을 적용해 압축부호어를 구함으로써 데이터를 축소시킬 수 있게 된다. 현재 통계에 의하면 이 기법에 의해 원래 팩시밀리 통신의 이미지정보를 평균 약1/8이하로 축소해 전송할 수 있다고 한다. 허프만 압축기법의 또다른 변형으로는 상용 압축파일 가운데서 가장 압축률이 우수한 LHARC라는 압축파일이 채용하고 있는‘적응적 허프만부호’를 들 수 있다. 허프만 압축기법이 미리 조사된 정보원 데이터의 통계적 성질을 이용해 압축을 수행하는 반면, 이 기법은 원래 데이터의 각 문자 입력시마다 적응적으로 발생문자의 빈도수를 계산해 확률값에 따라 허프만부호를 할당하는 압축방식이다. 동적 압축기법은 압축수행에 소요되는 시간 때문에 정보통신분야 에서는 잘 이용하지 않는다.