허프만 인코딩은 탁월한 글자 압축 알고리즘이다.

이 알고리즘은 1952년 Davide Huffman에 의해 개발되었다.

기본 아이디어는 각 문자를 2진 순서를 이용해서 자주 등장하는 글자에게 비트를 작게 할당하고

아주 드문 글자에게 많은 비트를 할당하여 줄이는 방식이다.

그리고 모든 글자의 2진 순서는 다르다.

보통 이진트리형태로 표현하여 글자를 단말노드(트리의 마지막)에 배치하는 형태이다.

예를 들어 아래의 그림과 같은 이진트리에 각 문자가 배치되었다고 하면

A 는 00, B는 01, C는 10, D는 110, E는 111로 코드를 갖게 된다.

이를 바탕으로 주어진 문자를 압축을 하게 된다.

여러분들은 역으로 허프만 코드가 주어질 경우 압축된 데이터를 원래의 문자로 변경하는 것이다.

주어진 압축 이진코드를 읽어 원래의 문자로 출력하는 것이다.

허프만 인코딩을 디코딩하기 timer 1s memory 256MB

허프만 인코딩을 디코딩하기 1s 256MB