> huffman | 최적 | 코드 <
// Huffman 코딩 - 최적의 프리픽스 프리 압축 알고리즘
최적 코드
주어진 빈도에 대해 평균 코드 길이가 가장 짧도록 코드를 생성합니다.
프리픽스 프리
어떤 코드도 다른 코드의 접두사가 아니므로, 모호함 없이 복호화할 수 있습니다.
빈도 기반
자주 등장하는 문자는 자동으로 더 짧은 코드를 받아 압축 효율을 높입니다.
>> 기술 정보
Huffman 코딩의 동작 원리:
Huffman 코딩은 문자 빈도로부터 이진 트리를 하향식이 아니라 상향식으로 구성합니다. 가장 빈도가 낮은 두 노드를 반복적으로 하나의 부모 노드로 합치면서, 최종적으로 루트 노드 하나만 남을 때까지 진행합니다. 왼쪽 가지는 '0', 오른쪽 가지는 '1'을 의미하며, 더 자주 등장하는 문자는 루트에 더 가까운 위치에 배치되어 더 짧은 코드를 가지게 됩니다. 그 결과 주어진 빈도 분포에 대해 거의 최적의 압축률을 얻을 수 있습니다.
Huffman 코딩 예시:
Text: "AABBBCCCC"
Frequencies:
A: 2
B: 3
C: 4
Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)
Tree:
Root(9)
/ \
C(4) AB(5)
/ \
A(2) B(3)
Codes:
C: 0
A: 10
B: 11
Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000
왜 Huffman 코딩을 사용해야 할까요?:
- ▸이론적인 엔트로피 한계에 가까운 압축률
- ▸구현이 비교적 단순함
- ▸ZIP/JPEG 등 다양한 포맷의 핵심 구성 요소
- ▸무손실 압축으로 데이터 손실 없음
- ▸실제 서비스에서 검증된 높은 효율성
>> 자주 묻는 질문
Huffman 코딩이란 무엇인가요?
Huffman 코딩은 1952년 David A. Huffman이 제안한 최적의 프리픽스 프리 압축 알고리즘입니다. 문자 등장 빈도에 따라 가변 길이의 코드를 할당하며, 자주 등장하는 문자일수록 더 짧은 코드를 부여하여 평균 코드 길이를 최소화합니다.
왜 프리픽스 프리(prefix-free)라고 하나요?
어떤 코드도 다른 코드의 접두사가 되지 않을 때 그 부호 체계를 프리픽스 프리라고 부릅니다. 예를 들어 문자 'A'의 코드가 '01'이라면, 다른 어떤 문자도 '01'로 시작하는 코드를 가질 수 없습니다. 이 속성 덕분에 별도의 구분자 없이도 왼쪽에서 오른쪽으로 비트를 읽어가며 항상 정확하게 복호화할 수 있습니다.
Huffman 코딩의 효율은 어느 정도인가요?
Huffman 코딩은 주어진 빈도 분포에 대해 이론적인 엔트로피 한계에서 보통 1비트 이내까지 가까운 압축률을 달성합니다. 영어 텍스트의 경우 대략 60~70% 정도의 압축을 기대할 수 있으며, 문자 빈도에 편차가 클수록 효과가 더욱 큽니다.
Huffman 코딩은 어디에서 사용되나요?
Huffman 코딩은 JPEG 이미지 압축, ZIP 파일 압축(LZ77과 결합된 DEFLATE), MP3 오디오 등 다양한 포맷에서 사용됩니다. 보통 다른 알고리즘과 함께 사용되며, 예를 들어 JPEG에서는 DCT와 양자화 이후에 Huffman을 적용하고, ZIP에서는 LZ77 이후 단계에서 Huffman을 사용합니다.
// 계산 예시
| Symbol | Freq | Bits | Code |
|---|---|---|---|
| A | 4 | 1 | 0 |
| B | 2 | 2 | 10 |
| C | 1 | 2 | 11 |
// 코드 예제
Input AAAABBC (7 symbols, 56 bits as 8-bit ASCII) Counts A=4 B=2 C=1 Merge C(1)+B(2) -> node(3); node(3)+A(4) -> root(7) Codes A=0 B=10 C=11 (0/1 on left/right branches; ties may swap) Encoded 0 0 0 0 10 10 11 = 4*1 + 2*2 + 1*2 = 10 bits
>> 더 많은 질문
Q: 허프만 코드는 유일한가요?
A: 꼭 그렇지는 않습니다. 빈도가 같으면 노드 선택과 0/1 할당이 달라질 수 있습니다. 하지만 올바른 허프만 트리라면 코드 길이와 총 크기는 항상 최적이며 같습니다.
Q: 접두어 없음(prefix-free)이란?
A: 어떤 코드도 다른 코드의 앞부분이 되지 않는다는 뜻입니다. 구분자 없이 루트에서 잎까지 비트를 따라가며 복호할 수 있습니다.
Q: 허프만이 최적이 아닌 경우는?
A: 심볼마다 정수 비트를 배정하기 때문에 확률이 매우 치우친 경우(예: 0.99) 효율이 떨어집니다. 산술 부호화가 엔트로피에 더 가깝습니다. 또한 복호기에 코드 표가 필요합니다.