허프만 코딩(Huffman coding)은 텍스트 압축 방법으로,

원본 데이터에서 자주 출현하는 문자는 작은 비트의 코드로 변환하고

출현 빈도가 낮은 문자는 큰 비트의 코드로 변환하여

전체 데이터를 최소한의 비트 수로 압축하는 방식이다.

이 과정에서 각 문자를 표현하기 위한 허프만 트리(Huffman tree)를 구성해야 한다.

예를 들어 AAAAAAABBCCCDEEEEFFFFFFG를 압축하려 할 때,

각 문자의 개수는 다음과 같다:

A:7개, F:6개, E:4개, C:3개, B:2개. D:1개, G:1개

이 상황에서 우선 가장 작은 D와 G를 묶어 둘의 합인 2가 부모가 되도록 트리를 구성한다.

이 후 가장 작은 두 노드인 B와 2를 묶어 합인 4이 부모가 되도록 트리를 구성한다.

이와 같은 작업을 반복하여 아래와 같은 트리를 구성한다.

최종적으로 전체 트리에 있어서 왼쪽 자식은 0, 오른쪽 자식은 1의 비트를 부여하면 허프만 트리가 완성된다.

이러한 과정을 통하여 문자열을 압축하면 아래와 같은 코드가 나온다.

AAAAAAABBCCCDEEEEFFFFFFG

0000000000000001000100011011011010101111111110101010101001011

각 문자에 대한 비트코드를 출력하는 프로그램을 작성하시오.

허프만(Huffman) 트리 timer 1s memory 128MB

허프만(Huffman) 트리 1s 128MB