Huffman Coding

Huffman Coding이란

고정 길이 코드 vs 접두어 코드

고정 길이 코드는 대표적으로 아스키 코드가 있습니다. 아스키 코드는 항상 8bit의 길이를 가지고 있습니다. 다루기에는 간단하지만, 저장 공간 활용에 있어서 제한이 있습니다. 이를 해결하기 위해서 가변 길이 코드가 존재합니다. 가변 길이 코드 중에서도 접두어 코드는 앞서 나온 문자가 다음에 나올 문자의 접두어가 되면 안 되는 특징을 가진 코드입니다. 예를 들어 다음은 접두어 코드가 아닌 경우 입니다.

a: 01
b: 101
c: 010

위 코드에서 01은 010의 접두어이기 때문에 접두어 코드가 아닙니다. 반면 다음은 접두어 코드의 예입니다.

a: 01
b: 10
c: 111

이 접두어 코드를 아스키코드로 한다면 총 24bit의 저장 공간을 소비합니다. 반면에 압축한 상태 그대로 이진 코드로 표현한다면 0110111로 7bit로 압축이 가능하게 됩니다. 이처럼 입력 문자의 빈도수를 가지고 압축하는 것이 Hffman Coding입니다.

Huffman Coding의 원리

Huffman Tree를 만들어서 압축을 하기 위해서는 다음과 같은 원리도 수행됩니다.

• 압축할 파일을 스캔하여 각 문자의 빈도수를 계산합니다.
• 빈도 수를 우선순위로 최소 힙을 구성합니다.

• 빈도 수가 가장 작은 두 노드들을 삭제합니다.
• 삭제한 두 노드 중에 작은 것을 왼쪽 자식 노드, 큰 것을 오른쪽 자식 노드로 하는 노드를 삽입합니다.

• 노드가 하나가 남을 때까지 반복합니다.
• 마지막 노드가 루트 노드가 됩니다.
• 빈도 수가 높은 문자에는 짧은 이진 코드를 부여하고 빈도 수가 낮은 문자에는 긴 이진 코드를 부여하여 압축 효율을 높입니다.

Huffman Coding 복원

각 문자에 대응되는 허프만 코드는 가변 길이 코드이기 때문에 01#001#110과 같이 구분자를 사용하지 않고 01001110을 사용할 수 있습니다. 그렇다면 복원할 때는 긴 비트 스트링을 어디서 끊어야 할까요?
기본적으로 알려진 방법으로는 첫 번째 비트인 트리 상 루트 노드로부터 비트가 0이면 왼쪽 1이면 오른쪽으로 타고 내려가다가 리프 노드에 도달하는 순간에 리프 노드가 가진 문자로 변환하고, 그 다음 비트들도 같은 방법으로 문자로 변환할 수 있습니다. 하지만 이 방법은 Huffman Tree의 높이에 시간복잡도가 비례한다는 특성을 가지고 있습니다.