[정보이론] 허프만 코딩(Huffman Coding)

 1952년에, David Huffman의 논문에서 허프만 코딩이 발표되었다. (교재에 따라 LZW를 먼저 배우는 경우도 있다.) 확률이 높은(발생빈도가 높은) symbol에 짧은 길이의 코드를 부여하고, 확률이 낮은(발생빈도가 낮은) symbol에 긴 길이의 코드를 부여하면서, symbol당 평균 bits의 개수를 줄이면서 총 데이터양(전체 코드 길이)을 줄여 압축한다. 허프만 코딩은 무손실 압축기법이기도 하다. (압축 과정에서 정보의 손실이 없다.)

 

 Symbol은 코드를 통해 나타내고자 하는 값이다. 참고로 통신에서의 Symbol은 전송하고자 하는, 혹은 저장하고자 하는 값이라고 봐도 무방하다. 만일 학점에 대한 정보를 코드로 표현하고 싶다면, A, B, C, D, F와 같은 각각의 학점들이 Symbol이 되는 것이다.

 

 Code는 101, 0011 등과 같이 0과 1로 표현된다. 이진수 0과 1로 표현되는 이유는 보통 데이터를 송수신하거나 저장할 때, bit를 사용하기 때문이다. bit는 정보의 양을 세는 단위로, 0아니면 1로 표현된다. bit는 binary digit의 줄임말로, binary는 이진수를 뜻한다. digit는 라틴어 digitus에서 유래한 단어로, 손가락, 발가락 이라는 뜻이다. 우리는 각 Symbol들에 대해서 어떤 코드를 사용할지 미리 약속해놓기 때문에, 101, 0011 등의 코드를 송수신한 뒤 쉽게 Symbol을 복구해낼 수 있다.

 

 Huffman Coding(부호화)을 사용하기 위해서는, 어떤 symbol들이 등장하는지 파악해야 하고, 각 symbol들이 나올 확률을 알고 있어야 한다. Huffman Coding은 소수의 symbol을 표현하고자 하는 경우에, 각 symbol들의 확률을 정확히 알고 있는 경우에 유리하다(=높은 압축률을 기대할 수 있다). 소수의 symbol만을 표현하고자 한다면, ASCII code를 사용하여 하나의 symbol을 8bits로 표현하는 것보다, 각 symbol에 코드를 할당해주는 것이 훨씬 경제적이다. 

 

[같이 보기 : ASCII code(아스키 코드), https://seongsu-minki.tistory.com/15]

 

 A, B, C, D, F 다섯 종류의 학점을 코드로 표현하는 경우를 가정해보자. ASCII code에서는 학점 하나를 나타내기 위해 8bits가 필요하다. 그러나 우리는 3bits만으로도 5종류의 symbol을 표현할 수 있다. ( $ 2^{3} $ = 8 > 5종류이므로) ASCII code로 symbol A, B, C, D, F에 대한 정보를 표현하기 위해 8bits*5종류 = 40bits를 사용해야 하지만, 다섯 종류의 학점 symbol만이 나온다는 것을 미리 알고 있을 때는 3bits*5종류 = 15bits만으로도 똑같은 정보를 저장하거나, 송수신할 수 있게 된다.

 

 Huffman 코딩은 코드를 보내는 전송횟수는 원본(ASCII)과 같지만, 자주 발생하는 코드의 길이를 줄여 symbol당 평균 bits수를 줄이면서 총 데이터 전송량을 줄여 압축한다. 단, 발생확률을 정확히 모르거나, symbol들의 값을 모두 파악하지 못한다면 Huffman 코딩을 사용하기 어렵다. 또한 symbol 개수가 많은 경우 압축에 불리할 수 있다.

 

참고로 symbol에 따라 코드의 길이가 다른 코드를 가변길이 코드(variable length code)라고 한다. 

 

MIT 학생들의 성적 분포

 

 Huffman Coding을 효과적으로 설명하기 위해, 교재에 나와 있는 MIT 학생들의 성적 분포표를 가져왔다.

 

 

 제일 먼저, Symbol에는 A, B, C, D, F와 같은 성적들이 할당되어 있다.

 

 바로 옆 p는 Probability의 줄임말로, symbol의 할당 확률을 의미한다. (각 symbol이 발생할 확률) 각 symbol들의 확률 값을 다 더하면 당연히 1이다. 이는 어떤 사건에 대한 모든 확률 값들을 더하면 100%가 된다는 말과 똑같다. 확률은 0과 1 사이의 실수이며, %는 가독성을 위해 확률 값에 100을 곱한 단위이므로 100%와 확률 1은 같다.

 

 Information은 확률에 따른 symbol의 기대 bits 수로, $log_{2}{(1/p)}$와 같은 수식으로 표현된다. 0.5의 확률을 가진 symbol은 $log_{2}{(1/0.5)}$ = 1이므로, 1bit의 기대 bit를 가진다. 만일 1bit보다 작은 bit로 표현이 가능하다면 평균 bits/symbol 값이 낮아져 효율적인 압축이 가능해지고, 1bit보다 많은 bit로 표현한다면 다소 비효율적인 압축이라고 할 수 있다.

 

[위의 로그 수식 모양이 왜 저따구죠? 수식에 대한 설명은 다음 링크를 참조하세요. 

https://seongsu-minki.tistory.com/13]

 

 Contribution to average 값은 각 symbol의 Information과 p를 곱한 값이다. 각 symbol의 Contribution to average값을 모두 더해준 값을 entropy라 부른다. entropy는 이론상 최대 압축 값으로, 아무리 뛰어난 압축 기술이라도 entropy값보다 더 작게 압축하는 것은 불가능하다. 제시되어 있는 자료의 entropy = 1.840bits라는 것을 알 수 있다.

 

 Code는 각 symbol들이 송신하는 Code의 내용으로, 어떻게 저런 값이 나왔는지는 조금 뒤에 살펴보겠다.

 

 Code Length는 실제 코딩 후 코드들의 길이이다. symbol들은 code length만큼의 정보량을 저장하거나 송수신 하므로, code length를 각 symbol의 데이터양이라고 봐도 무방하다. Information보다 Code Length가 짧다면 이 code가 나타내는 symbol은 압축에 기여한 것이고, 길다면 이 symbol은 압축에 다소 기여하지 못한 것이다.

 

 맨 오른쪽의 Contribution to average는 p에 Code Length를 곱한 값이다. (왼쪽 Contribution to average 값은 p에 Information을 곱한 값이다.) 각 symbol들의 Contribution to average 값을 모두 더한 값은 압축 후 실제 평균 bits/symbol 값을 나타낸다. 앞서 말했듯 이 값은 이론적으로 entropy보다 작을 수 없다. (이는 수학적으로 증명되었다.) [1.875bits > 1.840bits에서 예상대로 entropy보다 큰 값이 나왔다. 구한 값과 entropy의 차이가 작으므로, 훌륭한 압축이라고 할 수 있다.]

 

 

 이제 Huffman Code의 원리를 살펴보자. 모든 symbol 값들과 확률을 나열한 뒤, 확률이 제일 작은 두 개의 symbol부터 코드 0과 1을 차례대로 분배해준다. (선택된 두 symbol 중 확률이 큰 symbol에 1, 확률이 작은 symbol에 0을 할당해주면 Huffman Code의 가독성이 좋아진다.) 그 다음으로 확률이 적은 두 개의 symbol을 찾아 0과 1을 할당할 때, 새로운 숫자를 앞쪽에 할당해준다. (새우깡은 새 앞에로 외우면 편하다,,.) 앞서 보여주었던 MIT 학생들의 성적분포표를 가지고 Huffman Coding을 해보자. (확률이 같은 두 symbol 중 하나의 symbol을 골라 코드를 할당할 때, 코드의 길이가 짧은 symbol을 고르면 효율적이다.)

 

Start : (A = ‘-’ p = 0.25) (B = ‘-’ p = 0.5) (C = ‘-’ p = 0.125) (D = ‘-’ p = 0.100) (F = ‘-’ p = 0.025)

Next : (A = ‘-’ p = 0.25) (B = ‘-’ p = 0.5) (C = ‘-’ p = 0.125) (D = ‘1’ F = ‘0’ p = 0.125)

Next : (A = ‘-’ p = 0.25) (B = ‘-’ p = 0.5) (C = ‘1’ D = ‘01’ F = ‘00’ p = 0.25)

Next : (B = ‘-’ p = 0.5) (A = ‘1’ C = ‘01’ D = ‘001’ F = ‘000’ p = 0.5)

FINAL : (B = ‘1’ A = ‘01’ C = ‘001’ D = ‘0001’ F = ‘0000’ p = 1)

 

 Huffman은 머리가 좋다. 위와 같은 방식으로 Coding을 진행한다면, 사용자가 Coding을 하는 중 헷갈려 잘못 기입하거나 통신 중 에러가 나지 않는 한, 101이 들어오더라도, 심지어 1010111과 같은 값이 들어오더라도 수신 값이 (10,1)인지 (1,01)인지 헷갈릴 일이 없다. Huffman Coding은 Variable length code인데도 말이다! (Variable length code는 symbol마다 코드 길이가 다른 코드를 지칭한다. Fixed length code는 이와 대비되는 단어로, symbol들의 코드 길이가 모두 같다. 뒤에 설명할 LZW 알고리즘은 Fixed length code에 해당한다.) 왜 안 헷갈리지? 10이라는 코드가 없기 때문이다! 1로 시작하는 코드는 B밖에 없으므로, (10,1)와 같은 코드는 수신될 수 없다. Variable length code임에도, 수신측에서 코드가 끝나는 지점을 별도로 알려주지 않더라도 각 symbol들에 대한 코드만 갖고 있다면 해석하는 데에 전혀 지장이 없다! ( = Huffman Coding은 Prefix-condition을 만족한다!) 1010111은 (1,01,01,1,1)로 해석할 수 있다. 이는 마찬가지로, 10, 101, 011과 같은 코드가 없기 때문에 symbol의 개수에 대한 정보가 없음에도 문제없이 해석할 수 있는 것이다!

 

 Huffman 코드는 특히 작은 양의 symbol을 다룰 때, 확률이 높은 symbol이 존재할 때 유리하다. 다만, Huffman Coding을 위해서 각각의 symbol을 모두 파악하고 있어야하고, 각 symbol의 확률을 정확하게 알아야 한다는 한계점이 있다. 만일 부정확한 확률 정보를 갖고 있다면, 압축률은 현저히 떨어질 것이다.

 

 

--참고자료--

-Information Theory 교재 Chap5 이미지 참고

https://mtlsites.mit.edu/Courses/6.050/2014/notes/chapter5.pdf