허프만 압축

허프만 압축

기존의 파일의 문자를 고정 변환 방식을 이용 하는 대신 빈도 순으로 문자가 가진 비트를 줄여 효율적인 메모리 사용하는 방법

변환시킨 문자 코드 사이에는 접두부 특성이 존재하는데, 문자에 할당된 이진코드는 어떤 다른 문자에 할당된 이진 코드의 접두부가 되지 않는다는 것을 의미한다.

접두부 특성을 가진 코드의 장점은 코드와 코드 사이를 구분할 특별한 코드가 필요하지 않다.

따라서 각 문자의 출현 빈도수에 기반을 둔 이진트리를 만들어서 각 문자에 이진 트리 내부의 이진코드를 할당하면 허프만 코드가 완성이 된다.

Pseudo Code

입력: 입력 파일의 n개의 문자에 대한 각각의 빈도수
출력: 허프만 트리

1. 각 문자에 대해 노드를 만들고, 그 문자의 빈도수를 노드에 저장한다.
2. n개의 노드들의 빈도수에 대해 우선순위 큐 Q를 만든다.
3. while(Q에 있는 노드 수 >= 2) {
4.			빈도수가 가장 작은 2개의 노드(A와 B)를 Q에서 제거한다.
5.			새 노드 N을 만들고 A와 B를 N의 자식 노드로 만든다.
6.			N의 빈도수 <- A의 빈도수 + B의 빈도수
7.			노드 N을 Q에 삽입한다.
		 }
8. return Q

수행과정

line 3: Q에서 T와 G를 제거한 후, 새 부모 노드를 Q에 삽입한다.

Q에서 T와 G의 부모 노드와 C를 제거한 후 새 부모 노드를 Q에 삽입한다.

Q에서 C의 부모 노드와 A를 제거한 후, 새 부모노드 Q에 삽입

오른쪽으로 1을 부여하고 왼쪽으로 0을 부여하면서 코드를 완성시킨다.

허프만 코드의 압축률

고정 길이 비트의 경우 930 * 8 = 7,440 Bit
압축된 bit의 경우, 450+270+360+540 = 1620 Bit을 요구한다.
따라서 약 21.8%의 압축률을 보여준다.

복호화

복호화 또한 코드 하나하나 분리하여 허프만 코드로 생성된 트리를 따라가면 복호화가 가능하다.

시간 복잡도

line 1에서 n개의 노드를 만들고, 각 빈도수를 노드에 저장하므로 $O(n)$ 시간이 필요하다.
line 2에서 n개의 노드로 우선순위 큐를 만드므로 $O(n)$이 필요하다.
line 3~7에서 노드를 제거하고 삽입 연산을 수행하므로 $O(logn)$이 필요하다.
해당 행동을 n번 하므로 $O(nlogn)$ 수행된다.
따라서 최종 시간복잡도는 $O(nlogn)$이다.