허프먼 부호화

전산학과 정보이론에서 허프먼 부호화 또는 허프만 코딩(Huffman coding)은 무손실 압축에 쓰이는 엔트로피 부호화의 일종으로, 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘이다. 1952년 당시 박사과정 학생이던 데이비드 허프먼이 《A Method for the Construction of Minimum-Redundancy Codes》^[1]란 제목의 논문으로 처음 발표했다.

허프먼 부호화는 문자들의 빈도로부터 접두 부호(어떤 한 문자에 대한 부호가 다른 부호들의 접두어가 되지 않는 부호)를 만들어 내는 알고리즘으로, 적게 나오는 문자일수록 더 긴 부호를 쓰고 많이 나올수록 더 짧은 부호를 쓴다. 허프먼 부호화는 주어진 빈도에 대해서 항상 최적의 접두 부호를 만들어 내며, 이 과정은 빈도가 정렬되어 있을 경우 O(n)만에 가능하다. 각 문자들의 빈도가 2의 거듭제곱 꼴이거나 모두 같을 경우 이 접두 부호는 간단한 이진 블록 부호와 동일하다.

허프먼 부호화가 항상 최적의 접두 부호를 만들어 내기는 하지만, 접두 부호가 아닌 다른 종류의 부호가 더 효율적일 수도 있다. 예를 들어 여러 문자를 하나의 부호로 묶어 표현할 수 있는 산술 부호화나 LZW 등이 허프먼 부호보다 효율적인 경우가 많으며, 이것은 대부분 하나의 기호를 정수개의 길이를 가진 부호로서 표현하도록 되어 있는 한계에서 기인한다.

위에서 아래로 진행하는 샤논파노방법과는 달리 허프먼 알고리즘의 부호화 순서는 아래에서 위로 진행한다.

1. 초기화 : 모든 기호를 출현 빈도수에 따라 나열한다.
2. 단 한 가지 기호가 남을 때까지 아래 단계를 반복한다.
   1. 목록으로부터 가장 빈도가 낮은 것을 2개 고른다.
   2. 그 다음 허프먼이 두가지 기호를 부모 노드를 가지는 부트리를 구성하고 자식노드를 생성한다. 부모 노드 단 기호들의 빈도수를 더하여 주 노드에 할당하고 목록의 순서에 맞도록 목록에 삽입한다.
   3. 목록에서 부모노드에 포함된 기호를 제거한다.

허프먼 알고리즘은 입력 기호를 리프 노드로 하는 이진 트리를 만들어서 접두 부호를 만들어 내는 알고리즘이다.