한국은행 전산학 기출 [2010] 허프만 트리 활용 문자열 압축: 자세한 풀이와 예제

한국은행 전산학 기출 (2010): 허프만 트리를 이용한 문자열 압축 풀어보기

허프만 트리는 문자열 압축에 사용되는 트리 구조입니다.

허프만 코드는 문자열을 압축하기 위해 각 문자에 할당되는 고유한 이진 코드입니다.

문자열 압축은 데이터 크기를 줄여 저장 공간을 절약하고 전송 속도를 높이는 데 유용한 방법입니다.

허프만 트리는 문자의 등장 빈도를 기반으로 구성됩니다.

빈도가 높은 문자는 짧은 코드를, 빈도가 낮은 문자는 긴 코드를 할당하여 압축 효율을 높입니다.

허프만 트리를 이용한 문자열 압축 과정은 다음과 같습니다.

1. 문자의 등장 빈도를 계산합니다.
2. 빈도가 가장 낮은 두 문자를 선택하여 노드를 생성합니다.
3. 두 노드의 빈도를 합하여 새로운 노드의 빈도로 설정합니다.
4. 새로운 노드를 트리에 추가합니다.
5. 2~4번 과정을 반복하여 모든 문자가 트리에 포함될 때까지 수행합니다.
6. 루트 노드에서 각 문자 노드까지의 경로를 따라 0과 1을 할당하여 허프만 코드를 생성합니다.

예를 들어, 문자열 “AABAACDAB”를 허프만 트리를 이용하여 압축하는 과정은 다음과 같습니다.

1. 각 문자의 등장 빈도를 계산합니다.
* A: 4
* B: 2
* C: 1
* D: 1
2. 빈도가 가장 낮은 문자인 C와 D를 선택하여 새로운 노드를 생성합니다.
3. 두 노드의 빈도를 합하여 새로운 노드의 빈도를 2로 설정합니다.
4. 새로운 노드를 트리에 추가합니다.
5. 빈도가 가장 낮은 문자인 B와 새로운 노드를 선택하여 새로운 노드를 생성합니다.
6. 두 노드의 빈도를 합하여 새로운 노드의 빈도를 4로 설정합니다.
7. 새로운 노드를 트리에 추가합니다.
8. 빈도가 가장 낮은 문자인 A와 새로운 노드를 선택하여 새로운 노드를 생성합니다.
9. 두 노드의 빈도를 합하여 새로운 노드의 빈도를 8로 설정합니다.
10. 새로운 노드를 트리에 추가합니다.
11. 루트 노드에서 각 문자 노드까지의 경로를 따라 0과 1을 할당하여 허프만 코드를 생성합니다.
* A: 0
* B: 10
* C: 110
* D: 111

따라서 문자열 “AABAACDAB”는 허프만 코드를 이용하여 “0001001101110”으로 압축될 수 있습니다.

허프만 트리를 이용한 문자열 압축은 빈도가 높은 문자에 짧은 코드를 할당하여 압축 효율을 높이는 효과적인 방법입니다.

특히, 영어와 같이 빈도 분포가 불균일한 언어에서 효과적인 압축 방법입니다.