1. 개요

- 이진트리의 개념을 활용하여 문자열을 매우 효율적으로 무손실 압축할 수 있다. 허프만 코딩은 주어진 문자열의 정보를 손실 없이 효율적으로 압축하는 대표적인 암호화 기법의 하나로, 그 과정에서 이진트리를 사용한다.

- 간단히 설명하면, 어떤 문자열이 주어진다 할 때, 허프만 코딩은 이를 구성하는 각 문자들을 빈도순으로 정렬한 후 빈도가 가장 적은 문자들부터 이진트리를 구성한다. (문자들은 오로지 이진트리의 말단노드에만 위치한다. 이처럼 허프만 코딩 과정에서 생성되는 트리를 허프만 트리라 한다.) 이러한 이진트리를 구성했을 때, 루트에서부터 각 말단노드까지 왼쪽 자식 또는 오른쪽 자식을 선택하여 만들어지는 경로가 있다. 이 경로가 만드는 이진수를 말단노드의 각 문자가 갖는 ‘허프만 코드‘라 하며, 이러한 허프만 코드로 원 문자열을 다시 구성했을 때 그 길이는 원 문자열의 길이보다 짧아진다.

- 허프만 코딩은 현재 문자열/사진/영상 등의 압축에서 널리 사용되며, 수개의 런을 합병정렬 할 때 전체 숫자간 비교횟수를 최소로 하는 런의 합병 순서를 구할 때에도 사용할 수 있다. (각 런의 길이를 ‘문자열의 등장 빈도’로 보고 이를 기준으로 허프만 트리를 구성 후 이를 후위순회 하면 된다.)

2. 구체적인 알고리즘

허프만 코딩은 min-heap을 이용해 쉽게 구현할 수 있다.

(1) 각 문자의 빈도를 구해 그 값으로 min-heap을 구성한다.

(2) min-heap에서 두 숫자를 뽑고, 이 숫자들의 합을 키값으로 하는 노드 아래 두 숫자에 해당하는 노드를 붙여 새로운 트리를 만든다. 그리고는 이 숫자들의 합을 다시 min-heap에 넣는다.

(3) min-heap에 숫자가 하나만 남을 때까지(=루트노드) 2)의 과정을 반복한다.

3. 허프만 코드 구하기

위 2번에서 만든 허프만 트리의 루트에서부터 왼쪽 자식 또는 오른쪽 자식을 선택하여 탐색하면 (각 문자의 빈도를 키값으로 갖는) 말단노드에 도착할 수 있다. 이때 왼쪽 자식을 선택할 때마다 0, 오른쪽 자식을 선택할 때마다 1을 코드에 추가하면 말단노드에 도착했을 때 그 경로에 해당하는 0과 1로 만들어지는 코드가 있는데, 이 코드가 각 말단노드 문자에 해당하는 허프만 코드다.