허프만이 최적의 부호를 구성하는 방법
해밍은 허프만 부호화를 최소 평균 길이 접두사 자유 부호를 구성하는 탐욕 알고리즘으로 제시합니다. 핵심 아이디어: 트리를 하향식으로 구성하며, 항상 확률이 가장 낮은 두 기호를 병합합니다.
정방향 패스 (구성)
1. 모든 기호를 확률 순서로 정렬하되, 높은 순서부터 낮은 순서로.
2. 확률이 가장 낮은 두 기호를 선택합니다. 이들을 새로운 메타 기호로 결합하며, 확률은 두 기호의 확률의 합입니다.
3. 메타 기호를 정렬된 위치에 삽입합니다.
4. 두 개의 기호만 남을 때까지 반복합니다.
5. 남은 두 기호에 0과 1을 할당합니다.
역방향 패스 (부호 할당)
병합을 역순으로 실행취소합니다: 각 분할에서 병합된 두 기호는 결합된 부모와 동일한 접두사 비트를 받으며, 추가로 0 (한 자식) 또는 1 (다른 자식)을 받습니다. 0/1 할당은 임의적입니다 — 둘 다 유효합니다.
왜 이것이 최적인가: 다른 부호가 더 작은 평균 길이 L'를 가지고 있다면, 동일한 정방향 축소를 적용하면 결국 평균 길이가 1 비트 미만인 두 기호를 생성할 것입니다 — 2-기호 부호로는 불가능합니다. 모순입니다.
알고리즘 추적
해밍의 예: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125인 4개 기호 A, B, C, D.
정방향 패스:
단계 1: 정렬됨: A(0.5), B(0.25), C(0.125), D(0.125). 가장 낮은 두 개: C, D.
단계 2: CD를 p=0.25로 병합합니다. 새 목록: A(0.5), B(0.25), CD(0.25).
단계 3: 가장 낮은 두 개: B(0.25), CD(0.25). BCD를 p=0.5로 병합합니다.
단계 4: 두 개의 기호가 남습니다: A(0.5), BCD(0.5). A=0, BCD=1을 할당합니다.
역방향 패스:
BCD → B는 10을 받고, CD는 11을 받습니다. CD → C는 110을 받고, D는 111을 받습니다.
최종 부호: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 비트.
여러 유효한 허프만 부호
해밍은 비유일성의 두 가지 원천을 언급합니다:
1. 임의적 0/1 할당. 각 분할에서, 어느 자식에든 0을 줄 수 있습니다. 전체에서 0과 1을 교환하면 동일한 L을 가진 다른 부호가 생깁니다.
2. 타이브레이킹. 두 노드의 확률이 같을 때, 둘 중 하나를 '높게' 배치할 수 있습니다 (먼저 결합). 서로 다른 타이브레이킹 선택은 구조적으로 다른 트리 — '긴' vs '넓은' — 를 생성할 수 있으며, 동일한 L이지만 다른 부호 길이 분포를 갖습니다.
긴 나무 vs 넓은 나무
긴 나무 (비뚤어진): 각 깊이 수준에서 하나의 기호 (피보나치 같은 구조). 부호 길이가 크게 다양합니다: 하나의 기호는 짧은 부호를 받고, 다른 기호들은 더 긴 부호로 계단식으로 내려갑니다.
넓은 나무 (균형 잡힌): 기호들이 깊이 수준에 고르게 분포합니다. 부호 길이가 평균 근처에 군집합니다. 더 낮은 분산.
해밍의 권장사항: 선택의 여지가 있을 때, 넓은 나무를 선호하십시오. 동일한 L이지만 부호 길이의 분산이 작음 → 더 균일한 해독 시간 → 실시간 응용에서 더 작은 버퍼 요구사항.
부호 길이 분산 계산
부호 길이의 분산: Var = E[l²] − (E[l])²
부호 {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3}에 대해 p=[0.5, 0.25, 0.125, 0.125]로:
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
동등-확률 기호에 대한 대체 넓은 부호는 모든 길이-2 부호를 사용합니다: L=2, Var=0.
압축 이득 vs 기호 분포
해밍의 규칙: 허프만 부호화는 기호 확률이 상당히 다를 때만 성과를 냅니다.
동등 확률. 모든 2^k개 기호가 동등 확률 1/2^k를 가지면, 허프만은 블록 부호를 생성합니다: 모든 기호는 길이 k를 받습니다. L = H = k. 단순 블록 부호보다 이득이 없습니다.
비뚤어진 확률. 하나의 기호가 지배적이면 (다른 것들에 대해 p >> 1/2^k), 허프만은 그것에 매우 짧은 부호 (길이 1 또는 2)를 할당하여, L을 극적으로 감소시킵니다.
쉼표 부호 (해밍의 용어). 각 확률이 남은 총량의 2/3를 초과할 때, 허프만은 자연스럽게 생성합니다: p(s1)→0, p(s2)→10, p(s3)→110, ..., 끝에 두 개의 동등 길이 부호까지. 이것은 '쉼표 부호'입니다: 1의 연속 후의 후행 0이 쉼표처럼 작용합니다.
해밍은 언급합니다: 실제 데이터 압축 (백업, 파일 보관)은 소스가 비뚤어진 확률을 가질 때 저장 용량을 절반 이상 줄일 수 있습니다 — 영어 텍스트가 주요 예입니다.
허프만 vs 블록 부호: 수치 비교
해밍의 두 번째 예: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
블록 부호: 8개 기호 → 각각 3 비트 → L_block = 3.
해밍은 허프만 부호를 계산하고 L_Huffman ≈ 2.58 비트를 보고합니다.
절감: (3 − 2.58)/3 ≈ 블록 부호화보다 14% 압축.
기호 확률이 크게 다를 때 (여기서 1/3 vs 1/30, 10:1 비율), 가변 길이 부호화가 상당히 성과를 냅니다.
자체 컴파일 프로그램
해밍은 11장을 놀라운 아이디어로 마칩니다: 허프만 인코더는 자신을 인코딩할 수 있습니다. 디코딩 트리 (디코더에게 압축된 메시지를 읽는 방법을 알려줍니다)는 압축된 데이터와 함께 전송됩니다. 수신자는 부호에 대한 사전 지식이 필요하지 않습니다.
인코더: 데이터를 샘플링하고, 확률을 추정하고, 허프만 부호를 구성하고, 디코딩 트리를 헤더로 인코딩하고, 그 다음 데이터를 인코딩합니다.
디코더: 헤더를 읽어 트리를 재구성하고, 그것을 사용하여 데이터를 디코딩합니다.
해밍의 요점: 이 전체 파이프라인은 인간 개입 없이 라이브러리 함수로 실행할 수 있습니다. 당신이 그것을 호출하면, 자동으로 압축하고 압축을 풉니다. 현대 보관 형식 (ZIP, gzip, bzip2)은 정확히 이 패턴을 구현합니다.
더 깊은 원칙: 지능은 고정된 부호 표에 있지 않고 알고리즘에 있습니다. 알고리즘은 받는 모든 데이터에 적응합니다. 이것이 해밍이 모든 위대한 공학 시스템에서 보는 패턴입니다: 내장된 적응성, 볼팅된 것이 아닙니다.