[알고리즘] 허프만 트리를 이용한 텍스트 압축

엔트로피 인코딩(entropy encoding)은 정보 공학 주제 중 하나로, 데이터 압축에 있어 출현 빈도에 따라 데이터 압축률이 달라진다는 이론이다.

 

허프만 코딩은 텍스트 압축을 위해 사용되는 방법으로,

데이터에서 출현빈도가 높은 문자는 적은 비트의 코드로 변환하고, 출현 빈도가 낮은 문자는 많은 비트로 변환하여 표현함으로써 전체 데이터를 표현하는데 필요한 비트 수를 줄이는 방식이다.

 

"AAAAAAABBCCCDEEEEFFFFFFG"를 허프만 코딩으로 압축하려고 한다면 글자의 출현 빈도를 다음과 같이 정리할 수 있다.

 

출현 빈도가 적은 순서대로 이진 트리를 구성하고, 해당 트리 루트 노드에 문자 출현 빈도를 더해 설정한다.

이와 같이 모든 데이터에 대해 반복한다. (매 회차 내림차순 정렬 필요)

마지막으로 전체 트리에 대해 각 자기의 왼쪽에는 0, 오른쪽에는 1을 대입하여 허프만 트리를 완성한다.

A = 00

F = 10

E = 11

C = 011

B = 0100

D = 01010

G = 01011

 

00 00 00 00 00 00

0100 0100

011 011 011

01010

11 11 11 11

10 10 10 10 10 10

01011

이런식으로 바뀌게 된다.