[알고리즘]파일 압축 알고리즘 - 허프만 인코딩

 

파일압축 알고리즘의 목적

파일 압축에 대한 알고리즘의 경우 시간보다 공간을 절약하는 것에 초점을 맞추어 연구한다.

컴퓨터 파일 대부분이 중복되는 데이터가 있다는 것에 착안하여 텍스트 파일, 이미지, 사운드 등의 파일을 압축한다.

 

이 글에서 다루는 허프만 인코딩이 압축 알고리즘의 대표격 알고리즘에 속한다.

 

허프만 알고리즘

허프만 알고리즘은 트라이(Trie) 자료구조를 기반으로 만든다.

트라이는 하나의 문자 코드가 다른 문자 코드의 접두부(prefix)가 되지 않는 것을 보장하는 자료구조이다.

트라이를 트리와 혼동하는 경우가 있는데 Trie의 어원은 retrieve로부터 왔으며 트리와는 엄연히 다른 자료구조이다.

 

 

허프만 인코딩은 여러 트라이 중 가장 좋은 트라이를 결정하는 기법이라고 볼 수 있다.

우선순위 큐(Priority Queue)를 사용하여 빈도수가 가장 작은 문자부터 차례로 트라이를 만든다.

한 문자의 코드가 다른 문자의 코드 워드의 prefix가 될 수 없다는 특징이 있어 Prefix Code 라고도 불린다.

 

트리를 구축하는 과정은 크게 4가지다.

1. 데이터+빈도수를 모두 PQ에 insert한다.

2. 가장 빈도수가 낮은 두 노드를 골라 PQ에서 빼고

3. 새로운 노드를 만들어 2번에서 빼둔 노드 둘을 연결한다(빈도수를 합치는 과정)

4. 이걸 다시 PQ에 넣는다.

2~4 과정을 반복하다보면 허프만 트리가 구축된다.