탐욕 전략이 최적인 이유
허프만 알고리즘은 탐욕 알고리즘입니다: 매 단계에서 앞을 내다보지 않고 지역적으로 최적인 선택(가장 비용이 낮은 두 노드를 병합)을 합니다. 탐욕 알고리즘이 항상 전역적으로 최적인 것은 아니지만 여기서는 그렇습니다.
최적성 논증
부호 C가 최소 평균 길이 L을 가진다고 가정하십시오. 가장 낮은 확률을 가진 두 기호 p_a & p_b를 생각해 보세요. 모든 최적 부호에서 이 두 기호는 트리의 가장 깊은 수준에서 형제 잎으로 나타나야 합니다. 왜일까요?
부모를 공유하지 않으면 더 깊은 기호를 더 짧은 부호로 교환할 수 있습니다 — L을 줄입니다. 따라서 가장 깊은 잎은 가장 확률이 낮은 기호여야 합니다.
이제 a & b를 메타-기호 ab(p_ab = p_a + p_b 포함)로 결합하면, 축소된 알파벳에서 하나의 기호를 뺀 부분에 대한 모든 최적 부호는 정확히 축소된 문제에 대한 허프만 부호입니다. 귀납법이 논증을 완성합니다.
기하학적 관점
허프만 알고리즘은 이진 트리를 아래에서 위로 구성하여 가장 확률이 낮은 기호를 가장 깊은 곳에 배치합니다. 이렇게 하면 Σ p_i · depth(i) = L을 최소화합니다.
동등한 관점: 각 잎의 가중치가 그 확률인 가중 경로 길이를 최소화하도록 트리 잎에 레이블을 할당하고 있습니다.
탐욕 단계 실행
확률: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. 합 = 1.0 ✓
단계 1: 가장 낮은 두 개: C(0.2), D(0.1). 병합 → CD(0.3). 목록: A(0.4), B(0.3), CD(0.3).
단계 2: 가장 낮은 두 개: B(0.3), CD(0.3) (동점 — 둘 다 유효). 병합 → BCD(0.6). 목록: A(0.4), BCD(0.6).
단계 3: A(0.4), BCD(0.6) 병합 → root(1.0). A=0, BCD=1 할당.
역방향: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 비트.
코드-길이 분산
두 허프만 부호는 같은 L을 달성할 수 있지만 다른 코드-길이 분포를 가질 수 있습니다. 코드 길이의 분산은 이 분포를 측정합니다:
Var(l) = E[l²] − (E[l])²
여기서 E[l] = L (평균 코드 길이)이고 E[l²] = Σ p_i · l_i²입니다.
분산이 중요한 이유:
1. 버퍼 요구 사항. 실시간 복호화에서 각 기호는 가변 개수의 비트를 취합니다. 높은 분산은 일부 기호가 많은 비트를 취한다는 의미입니다 — 항상 완전한 기호를 읽을 수 있도록 보장하려면 더 큰 입력 버퍼가 필요합니다.
2. 복호화 지연. 높은 분산 부호는 긴 최악의 경우 복호화 경로를 가집니다. 낮은 분산(넓은) 부호는 최악의 경우를 더 촘촘하게 제한합니다.
3. 견고성. 높은 분산 부호에서 손실된 비트는 더 많은 동기화 손상을 야기합니다. 왜냐하면 긴 부호어는 완전히 다시 읽어야 하기 때문입니다.
해밍의 권장 사항: 여러 유효한 허프만 부호가 존재할 때(동점 해결 선택), 낮은 분산을 가진 부호를 선호하십시오 — 넓은 트리.
두 트리의 분산 계산
p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 & 부호 A=0, B=10, C=110, D=111 사용:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
3-기호 허프만 부호 전체 과정
완전한 전체 과정 예제: 허프만 부호를 구성하고, L을 계산하고, H를 계산하고, L ≥ H를 검증하고, Var을 계산합니다.
소스: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
허프만 구성:
단계 1: 정렬됨: X(0.6), Y(0.3), Z(0.1). 가장 낮은 두 개: Y(0.3), Z(0.1).
병합 → YZ(0.4). 목록: X(0.6), YZ(0.4).
단계 2: X(0.6), YZ(0.4) 병합 → root(1.0). X=0, YZ=1 할당.
YZ → Y=10, Z=11.
부호: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 비트.
엔트로피: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 비트.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 엔트로피보다 8.1% 높음.
분산: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
당신의 차례: 완전한 파이프라인
참고용 log₂ 값: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.