Huffman Coding (Compression Algorithm)

Fixed-length Encoding & Variable-length Encoding

일반적으로 문자(character)는 8bit의 2진수로 저장이 된다. 각 문자가 같은 크기의 저장공간을 차지하기 때문에 이것을 fixed-length encoding이라고 부른다.

 

 

따라서 문자열을 압축하기 위해서는 어떤 문자들의 저장공간을 8bit 보다 작게 가져가야 한다. 이때 사용하는 방법이 variable-length encoding이다. 문자열에서 특정 문자들이 다른 문자들에 비해 더 빈번하게 사용되는 경우가 있다. 이러한 경우 자주 사용되는 문자를 짧은 bit, 적게 사용되는 문자를 긴 bit의 2진수로 mapping 하게 된다면 총 문자열의 크기를 줄일 수 있다.

 

 

하지만 variable-length encoding의 문제는 decoding이다. 예를 들어 'abbacdbaa'라는 문자열을 압축한다고 했을 때 a가 4번, b가 3번, c가 1번, d가 1번 발생하기 때문에 빈도수를 고려하여 아래와 같이 임의의 bit로 mapping 할수 있다.

a 0
b 10
c 010
d 110

그러면 'abbacdbaa'는 0101000101101000 (0/10/10/0/010/110/10/0/0)으로 mapping 할 수 있다. 문제는 decoding이다. 이 encoding된 2진수를 다시 문자열로 decoding을 하려고 하면 아래와 같이 다양한 방법으로 decoding 될 수 있다.

0/10/10/0/010/110/10/0/0 'abbacdbaa'
010/10/0/0/10/110/10/0/0 'cbaabdbaa'
0/10/10/0/0/10/110/10/0/0 'abbaabdbaa'
010/10/0/010/110/10/0/0  'cbacdbaa'
....

 

 

이러한 모호함을 막기 위해서는 encoding시에 prefix rule을 만족하도록 mapping 정보를 정하면 된다. prefix rule이란 어떠한 character도 다른 charcter의 prefix가 될 수 없도록 하는 rule이다. 위의 예시에서 a였던 0은 c였던 010의 prefix가 되었다. 이것은 prefix rule을 위반한 것이다. prefix rule을 만족하도록 다시 아래 mapping 정보를 사용해 보자.

a 0
b 10
c 110
d 111

그러면 'abbacdbaa'는 0101001101111000 (0/10/10/0/110/111/10/0/0)으로 mapping 할 수 있다. 그리고 0101001101111000은 abbcdbaa로 유일하게 decoding 된다.

 

 

Huffman Coding

(작성중)

 

 

참고자료:

https://www.techiedelight.com/huffman-coding/