한양과기고 에듀테크 수업도구 대시보드

허프만 코딩 — 자주 쓰는 글자는 짧게

보통 컴퓨터는 모든 글자를 똑같이 8비트로 저장한다. 하지만 글에서 e는 z보다 훨씬 자주 나온다. 허프만 코딩은 자주 나오는 글자에 짧은 비트열, 드물게 나오는 글자에 긴 비트열을 배정해 전체 크기를 줄인다. ZIP · PNG · JPEG · MP3 안에서 실제로 쓰이는 무손실 압축의 핵심 아이디어다.

1. 글자 세기

2. 가장 작은 둘을 계속 합치기 (탐욕 알고리즘)

‘트리 만들기’를 누른 뒤 다음 단계로 진행하세요.

3. 완성된 허프만 트리 & 코드

왼쪽 가지 = 0, 오른쪽 가지 = 1. 뿌리에서 잎(글자)까지 내려가며 만나는 숫자를 이으면 그 글자의 코드가 된다.

4. 얼마나 줄었을까?

–

고정 8비트 (bits)

–

허프만 (bits)

–

절약률

ASCII 8비트 고정–

허프만 가변 길이–

인코딩된 비트열:

–

5. 알고리즘 (의사코드)

# 1. 각 글자를 (빈도, 잎노드) 로 만들어 최소 힙에 넣는다 heap = [(freq[c], Leaf(c)) for c in freq] heapify(heap) # 2. 노드가 1개 남을 때까지: 가장 작은 둘을 꺼내 합친다 while len(heap) > 1: f1, a = heappop(heap) # 가장 작은 것 f2, b = heappop(heap) # 그 다음 heappush(heap, (f1 + f2, Node(left=a, right=b))) root = heap[0][1] # 남은 하나가 트리의 뿌리 # 3. 뿌리에서 내려가며 왼쪽=0, 오른쪽=1 을 이어 코드 생성 def walk(node, path): if node.is_leaf: code[node.glyph] = path or "0" else: walk(node.left, path + "0") walk(node.right, path + "1")

6. 왜 이게 통할까?

접두사가 겹치지 않는다 (Prefix-free)

모든 글자가 트리의 잎에만 있으므로, 어떤 코드도 다른 코드의 앞부분이 될 수 없다. 덕분에 0110100 같은 비트열을 구분 기호 없이 왼쪽부터 읽어 내려가며 딱 하나로 해독할 수 있다.

탐욕적 선택이 최적이다

매 단계 "가장 빈도 낮은 둘"을 합치면, 드문 글자가 트리 깊은 곳(긴 코드)으로 밀려난다. 이 단순한 규칙이 놀랍게도 전체 비트 수를 최소로 만든다는 것이 수학적으로 증명돼 있다.

편향될수록 이득

특정 글자 몇 개가 압도적으로 자주 나오면 절약률이 커진다. 반대로 모든 글자가 똑같은 빈도면 허프만 코드도 고정 길이와 같아져 이득이 없다 (엔트로피 한계).

실제 어디에 쓰나

ZIP/gzip(DEFLATE), PNG, JPEG의 마지막 단계, MP3, 폰트 파일 등. 보통 사전 기반 압축(LZ77) 뒤에 허프만을 한 번 더 씌워 마무리한다.

1952년 David A. Huffman이 MIT 대학원 수업 과제로 고안 — 담당 교수는 Robert Fano였다.