[알고리즘]허프만코드

1. 허프만 코드 개요

허프만 코드는 1952년 다프트 허프만이 고안한 무손실 데이터 압축 알고리즘이다. 이 코드는 각 문자 또는 데이터 심볼이 나타나는 빈도수에 따라 가변 길이의 이진수를 할당하는 방식으로, 전체 데이터의 세트에 대해 평균 비트 수를 최소화하는 것이 목표이다. 허프만 코드는 정보 이론에서 도출된 엔트로피(정보량)를 바탕으로 하며, 특정 데이터 세트의 문자 분포를 분석해 가장 빈번히 등장하는 문자는 짧은 코드로, 드물게 등장하는 문자는 긴 코드로 표현한다. 이를 통해 같은 데이터를 고정 길이 코드보다 적게 표현할 수 있게 되어 데이터 압축률이 향상된다. 예를 들어, 텍스트 파일의 경우 일반적으로 영어 알파벳이 사용되며, `e`는 전체 문자 중 12.7%를 차지하고, `z`는 0.074%를 차지한다. 허프만 코드는 이러한 빈도 차이를 반영하여 `e`에는 가장 짧은 코드인 0 또는 10을, `z`에는 가장 긴 코드를 할당하는 방식을 사용한다. 이 방법의 특징은 데이터의 문자별 발생 빈도에 따라 최적의 코드를 자동으로 생성한다는 점이며, 입출력 과정에서 압축률이 높을수록 효율이 상승한다. 허프만 코드는 텍스트 압축뿐만 아니라 이미지, 영상…