[한국은행 전산학 기출][2010] 허프만 트리를 이용한 문자열 압축

허프만 트리... 이름과 어렴풋한 트리와 0101101의 비트 나열만 기억나는 나...를 반성해 보고자 풀이를 정리한다.

 

이 문제는 한국은행에서 공개한 전산학 기출 문제 중, 2010년 전산학술 문제이다.

 

문제는 다음과 같다.

---

문제

 

허프만(Huffman) 압축 알고리즘을 이용하여 ACABFEAFDE의 입력 문자를 압축하려고 한다. 아래 물음에 답하시오.

 

(1) 허프만 트리를 그리고, 허프만 코드를 작성하시오.

 

데이터	빈도수	등장 확률
A	3	0.3
B	1	0.1
C	1	0.1
D	1	0.1
E	2	0.2
F	2	0.2

 

(2) '(1)' 문항에서 1글자를 8bit ASCII 코드로 계산하였을 때, 압축률(%)은 얼마인가? (단, 소수 첫째자리에서 반올림하시오.)

 

---

풀이

(1) 허프만 트리를 그리고, 허프만 코드를 작성하여라.

 

허프만 트리는 문자열 압축을 위해 사용하는 트리이다.

각 문자의 등장 빈도가 주어졌을 때, 등장 빈도를 기준으로 오름차순 정렬을 하는 우선순위 큐를 이용하여 허프만 트리를 그릴 수 있다.

 

주어진 데이터와 등장 확률을 트리의 노드 하나로 하여, 등장 확률을 기준으로 우선순위 큐를 작성하면 다음과 같다.

 

priority queue의 initial 상태

이제 이 우선순위 큐에서 가장 등장 확률이 가장 낮은 두 개의 노드를 각각 left node와 right node로 하고, 해당 노드들의 등장 확률을 합한 것을 가지는 부모 노드를 만들어 sub tree를 생성하여 다시 큐에 집어넣는다.

 

첫 번째 merge 이후 큐 상태

이 과정을 계속 반복하여 큐에 노드가 하나 남을 때 까지 같은 과정을 반복하면 다음의 진행 과정을 거치게 된다.

 

두 번째 merge 이후 큐 상태

세 번째 merge 이후 큐 상태

세 번째 merge 이후 큐 상태

이제 큐에 노드가 두개 남았기 때문에, 마지막으로 한번만 더 병합하면 아래와 같은 허프만 트리를 얻을 수 있다.

허프만 트리에서 허프만 코드를 얻는 방법은 아래의 트리에 그려져 있는 것 처럼,

부모 노드에서 시작해서 내가 원하는 문자의 leaf node까지의 경로에서 left sub tree로 갈때는 0, right sub tree로 갈때는 1을 기록하면 된다.

merge가 끝난상태 (허프만 트리)

예를 들어, 문자 D의 허프만 코드를 구하기 위해서는

먼저 root에서 right sub tree로 가야 하므로 1

그 다음에는 left sub tree로 가야 하므로 10

그 다음에는 left sub tree로 가야 하므로 100

이때 도착한 노드가 leaf node이며 D이므로 더이상의 진행을 하지 않는다.

따라서, D의 허프만 코드는 100으로 구할 수 있다.

 

문제에서 구하라는 모든 문자에 대한 허프만 코드를 구하면 다음과 같다.

 

데이터	허프만 코드
A	11
B	1010
C	1011
D	100
E	00
F	01

 

허프만 코드를 보면 알 수 있듯이, 등장 확률이 높은 문자열은 짧은 코드로, 등장 확률이 낮은 문자열은 긴 코드로 변환하여 많이 나오는 애를 어떻게든 줄여서 문자열을 압축함을 알 수 있다.

 

여기서 아직 해결하지 못한 의문이 한 가지 있는데, 나는 노드를 merge 한 후 생성된 sub tree의 우선순위를 동등한 확률을 가진 기존 노드들보다 우선으로 뒀는데, 이렇게 해도 상관이 없나 궁금하다. 찾아보면 다들 그냥 각자 원하는대로 하는것같은데.. 그럼 뭐 결과적으로 압축률은 똑같이 나올텐데 허프만 코드 자체는 트리 모양에 따라 달라진단 말이지? 우째야 하는고 (아시는 분 있으면 댓글 좀 달아주세요)

 

(2) 압축률 구하기

 

원래 문자열은 ACABFEAFDE으로, 10글자로 이루어져 있다.

 

만약 이것을 문제에서 제시한 것 처럼 한 글자에 8bit인 ASCII 코드로 나타낼 경우,

이 문자열을 표현하기 위해 10글자 * 8bit = 80bit 가 필요하다.

 

만약, 우리가 구한 허프만 코드를 이용하여 문자열을 바꾸면 1110111110100100110110000 로 문자열을 나타낼 수 있다.

따라서 허프만 코드로 압축한 문자열은 25bit가 필요하다.

 

결국, 허프만 코드를 사용하기 전에는 80bit가 필요했는데 허프만 코드를 이용하면 25bit만으로 문자열을 나타낼 수 있다.

 

이때, 압축률은 25/80 * 100 = 31.25% 이다.

 

---

정말 기본 개념 중 기본인데... 오랜만에 봤다고 어떻게 하더라 싶었던 문제이다.

기본에 충실하자!!@!@!@!!!@