분류 전체보기 (165)
과학 꼼지락 (35)
수학 꼼지락 (41)
 시 꼼지락 (21)
언어 꼼지락 (6)
잡다 꼼지락 (61)
비밀 꼼지락 (0)
BLOG main image





수학 꼼지락
2007. 1. 14. 23:03
지난번에 압축에 관한 글을 올리고서 압축에 관하여 좀 찾아 봤는데 Huffman coding이라는 것이 있더군요. 이 방법은 1954년 Huffman이라는 사람이 고안했습니다. 문서 내에서 모든 글자가 같은 빈도로 사용되지는 않는 것에 착안한 것입니다. 가장 많은 횟수로 사용된 글자를 가장 짧은 부호어에 대응시키는 것이지요. 그리고 점점 사용 횟수가 많아져 갈수록 점점 긴 부호어에 대응 시키는 것입니다. 이 방법을 사용하면 통계적으로 통신이미지 정보를 1/8의 크기로 만든다고 합니다. 이렇게 압축률이 좋다보니 요즘에도 많이 사용되고 있다고 합니다. JPEG 나 MPEG 포맷의 형태가 Huffman coding을 이용한 포맷입니다. 이들은 그림에서 가장 많이 사용된 색을 가장 짧은 부호어로 표시하는 방식을 이용합니다.

그럼 어떻게 압축을 하는지 구체적으로 알아봅시다.

예를 들어,

i like selly.

라는 문장이 있다고 합시다.
위 문장을 표현하기 위해서 알파벳을 컴퓨터가 알아듣는 이진법으로 바꿉시다.
알파벳은 모두 26자 그리고 . 까지 하면 27 이므로 이진법의 다섯자리수들을 사용하면 되겠군요.
그러면 11개의 글자가 각각 5자리씩을 차지하니 결국 55개의 수가 사용되는군요.

그러면 이제 Huffman coding을 해 봅시다.
먼저 위 문장에서 쓰인 알파벳과 그 회수를 보면 (띄어쓰기는 생각하지 않겠습니다.)

i - 2회,  l - 3회,  k - 1회, s - 1회, e - 2회, y - 1회 . - 1회

이렇게 쓰였습니다.

여기서 가장 많이 사용된 l 에 가장 짧은 부호어 1을 부여합니다.
그리고 그다음으로 많이 사용된 문자 i 와 e 에는 그보다 긴 부호어 00과 01을 각각 부여합니다.
그뒤 가장 적은 회수로 사용된 k와 y . 에는 더 긴 부호어 000과 001 그리고 010을 부여합니다.

결국 쓰이는 문자수는

1*3 + 2*2*2 + 3*3 = 3 + 8 + 9 = 20개가 됩니다.

55개가 쓰이던 것을 20개로 줄였습니다. 압축률은 36.364% 가 되는군요.
이 경우에는 허프만코딩을 사용한 것 치고는 압축률이 상당히 낮게 나왔네요.
뭐 그래도 100%전송보다야 훨씬 경제적이지 않습니까?

이렇게 경제적이고 좋은 압축방법.. 앞으로 더 좋은 압축 방법들이 많이 나왔으면 좋겠습니다.

'수학 꼼지락' 카테고리의 다른 글

이발사 면도 딜레마  (5) 2007.02.22
Huffman coding  (0) 2007.01.14
버스 정류장에서의 몬티-홀 딜레마  (7) 2007.01.05
압축  (2) 2006.12.23
이름   
비밀번호 
홈페이지 
비밀글