3.Data Representation

이번 단원에서 Huffman Encoding 에 관해 자세히 알아 보도록 하겠습니다.
오늘 DS시간에 수업을 듣는데 허프만 코드에 대해서 나왔는데, 정말 이해가 안되서 DS공부도 할 겸 허프만 코드에 대해 공부해 보도록 하겠습니다.

허프만 코드란 Keyword encoding, Run-Length encoding 과 함께 Text Compression 의 한 종류입니다.
호프만 부호화의 기본 개념은 각 단위 정보를 표현하는 비트 수를 단위 정보들의 출현 빈도를 기본으로 할당한 것인데요.
빈도가 높은 정보는 적은 비트 수를 사용하여 표현하고, 빈도가 낮은 정보는 비트 수를 많이 사용하여 표현해서 전체 데이터의 표현에 필요한 비트의 양을 줄이는 것입니다.
 허프만 부호는 팩스전송이나 JPEG, MPEG 등 화상 정보의 압축 부호화 표준 규격에도 널리 사용됩니다.


허프만 부호화의 동작원리를 알아 봅시다.
① 발생확률이 높은 순서대로 부호를 정렬한후, 최소 발생확률 2개 부호를 선정함
② 최소 발생확률 2개 부호를 합한 값을 구한후, 발생확률이 높은 순서대로 부호 정렬
③ ①과 ②의 과정을 부호 값이 1이 될때 까지 반복함
④ 원래 확률값과 각각의 확률값을 합산하여 나온 결과값에 각각 0과1을 순차적으로 부여함

이 원리에 따라 허프만 트리를 만들어 보면 다음과 같다.


AAAAABBCDDEEEEEF 라는 문자가 있습니다.
이것을 압축하지 않으면 8bit * 17 개 = 136 bit 가 됩니다.
따라서 허프만 부호화 방법으로 압축해 보겠습니다.



첫번째




빈도순으로 정렬을 하고 가장 빈도가 낮은 둘을 더합니다.
그리고 다시 정렬을 하는데 여기서는 2로 나왔기 때문에 제자리에 두고 다시 옆수와 더합니다.



계속해서 정렬과 더하기를 반복합니다.




그럼 마지막으로 다음과 같은 트리가 완성되게 됩니다.



이렇게 해서

A   0
B   110
C   11010
D   1110
E    10
F    11111

으로 허프만 테이블을 만들 수 있습니다.

이것으로 위의 문자를 압축하여
0000001101101101011101110101010101011111 과 같이 나타낼 수 있습니다.
136bit 보다 훨씬 압축된게 보이시죠!?



이렇게 해서 허프만 부호화에 대해 알아보았습니다.