홍라이프 계산기허프만 부호 생성기 쉽게 이해하기 — 개념과 원리
허프만 부호화는 자주 나오는 문자에는 짧은 비트열을, 드물게 나오는 문자에는 긴 비트열을 붙여 주어진 빈도에서 가장 짧은 접두 부호를 만드는 방법입니다. 이 도구는 입력한 글로 부호 트리를 만들고, 문자별 부호와 전체 부호 길이를 보여 줍니다. 허프만 부호는 ZIP·PNG·gzip이 쓰는 DEFLATE와 JPEG의 기본 방식에도 들어 있습니다.
계산 방법
- 각 문자가 나온 횟수를 셉니다.
- 모든 문자를 횟수를 가중치로 한 잎(leaf) 노드로 둡니다.
- 가장 가벼운 두 노드를 꺼내 가중치의 합을 갖는 새 노드로 묶고, 트리가 하나 남을 때까지 반복합니다.
- 뿌리에서 내려가며 왼쪽은 0, 오른쪽은 1을 붙여 부호를 읽습니다.
- 부호화 비트 수 = Σ 문자 횟수 × 부호 길이
- 8비트 ASCII 대비 크기 = 부호화 비트 ÷ (문자 수 × 8) × 100이고, 절약률은 100%에서 이 값을 뺀 것입니다.
부호표 자체의 크기는 포함하지 않습니다.
원리
어떤 부호도 다른 부호의 앞부분이 되지 않으므로, 구분 기호 없이도 비트열을 앞에서부터 차례로 해독할 수 있습니다. 가장 드문 두 노드부터 묶으면 드문 문자가 트리 깊은 곳에 놓이고, 긴 부호는 거의 쓰이지 않으니 손해가 적습니다. 1952년 허프만은 이 탐욕적 선택이 최적의 접두 부호를 만든다는 것을 증명했습니다. 평균 부호 길이는 섀넌 엔트로피와 1비트 이내로 차이 납니다.
예제 풀이
- 입력: "abracadabra"(11글자), 횟수는 a = 5, b = 2, r = 2, c = 1, d = 1
- 병합: c(1)+d(1) = 2 → b(2)+r(2) = 4 → cd(2)+br(4) = 6 → a(5)+6 = 11
- 부호: a = 0, c = 100, d = 101, b = 110, r = 111
- 비트 수: 5×1 + 1×3 + 1×3 + 2×3 + 2×3 = 23비트
- ASCII는 11 × 8 = 88비트이므로 크기는 23 ÷ 88 = 26.14%, 절약률은 73.86%
결과 해석
비율이 낮을수록 압축이 잘 된 것입니다. 이 예에서 문자당 평균은 23 ÷ 11 ≈ 2.09비트로, 엔트로피 약 2.04비트에 매우 가깝습니다. 가중치가 같은 노드를 어떤 순서로 묶느냐에 따라 부호 모양은 다를 수 있지만, 최적 부호의 전체 길이는 같습니다.
흔한 실수
- 해독하려면 부호표도 함께 보내야 한다는 점을 잊는 경우. 짧은 글에서는 부호표가 절약분보다 클 수 있습니다.
- 모든 프로그램이 똑같은 부호를 낼 것이라 기대하는 경우
- 두 비율을 혼동하는 경우. 26.14%는 남는 크기, 73.86%는 줄어든 비율입니다.
자주 묻는 질문
허프만 부호화는 무손실인가요?
네. 같은 트리로 해독하면 원래 글이 그대로 복원됩니다.
산술 부호화와는 무엇이 다른가요?
허프만은 기호마다 정수 개의 비트를 쓰지만, 산술 부호화는 소수 비트까지 활용해 엔트로피에 더 가까워집니다.
왜 접두 부호가 되나요?
문자가 모두 트리의 잎에만 있어서, 한 문자로 가는 경로가 다른 문자를 지나지 않기 때문입니다.
출처: D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE, 1952 · RFC 1951, DEFLATE Compressed Data Format Specification version 1.3