2026-11-08고3이산 수학정보대수
88비트가 23비트로: 자주 쓰는 글자에 짧은 이름 붙이기
수형도로 허프만 부호를 만들고 로그로 엔트로피 하한을 계산해 압축의 한계를 검산한다
출발 강좌대학 공개강좌 · 멀티미디어(세종대학교 · 2 차시 . 허프만 부호화 (Huffmancoding))
- 대수[12대수01-04] 로그의 뜻을 알고, 그 성질을 이용하여 계산할 수 있다.
- 이산 수학[12이수04-06] 수형도와 생성수형도의 뜻을 알고, 이를 의사 결정에 활용할 수 있다.
- 정보[12정02-01] 디지털 데이터 압축의 개념과 필요성을 이해하고, 압축의 효율성을 분석하여 평가한다.
01 Intro — 모든 글자에 같은 길이를 줘야 할까?
모스 부호에서 영어 알파벳 E는 점 하나로 표시된다. 영어 글에서 가장 자주 나오는 글자이기 때문이다. 반대로 드물게 쓰이는 글자에는 점과 선을 여러 개 붙인 긴 부호가 배정되어 있다. 자주 쓰는 것은 짧게, 드물게 쓰는 것은 길게 적으면 전체 전송 시간이 줄어든다는 생각이 19세기 전신 부호에 이미 담겨 있었던 셈이다.
컴퓨터는 보통 이와 반대로 움직인다. 아스키(ASCII) 방식으로 글자를 저장하면 A든 Z든 똑같이 8비트를 쓴다. 이렇게 하면 읽고 쓰기는 편하지만, 자주 나오는 글자와 거의 나오지 않는 글자가 같은 자리를 차지하므로 낭비가 생긴다. 사진·음악·동영상 파일이 지금처럼 작아질 수 있었던 바탕에는 이 낭비를 수학적으로 줄이는 방법이 있다.
그렇다면 질문은 이것이다. 글자마다 길이를 다르게 주되 받는 쪽이 헷갈리지 않게 하려면 어떻게 해야 하고, 그렇게 해서 줄일 수 있는 길이에는 한계가 있을까?
토큰을 사거나 구독하면 전체를 볼 수 있어요
탐구 내용, 직접 해 보는 탐구, 참고문헌까지 모두 열려요.