Codice come albero
Un codice senza prefisso si mappa a un albero binario: la radice rappresenta l'inizio della decodifica, i rami sinistri rappresentano il bit 0, i rami destri rappresentano il bit 1, e le foglie rappresentano le parole in codice complete.
Il vincolo geometrico: ogni foglia termina un percorso da radice a foglia. Nessuna foglia può avere un discendente (se lo avesse, la sua parola in codice sarebbe un prefisso della parola in codice del discendente, violando la proprietà senza prefisso).
Questo dà alla disuguaglianza di Kraft un'interpretazione geometrica:
Ogni foglia a profondità d 'occupa' una frazione 2^(−d) della capacità totale dell'albero. La capacità totale di un albero binario completo a profondità D è 1. Un codice senza prefisso usa foglie a varie profondità; la somma di Kraft misura l'occupazione totale.
Somma di Kraft = 1: codice completo (ogni percorso termina a una foglia — imballaggio perfetto).
Somma di Kraft < 1: codice incompleto (parte della capacità dell'albero inutilizzata — potrebbero essere aggiunti più simboli).
Somma di Kraft > 1: impossibile per i codici senza prefisso (alcuni percorsi dovrebbero condividere una foglia).
Foglie più profonde = Codici più lunghi = Minore capacità
Una foglia a profondità 1 usa metà della capacità dell'albero (2^(−1) = 0,5).
Una foglia a profondità 3 usa un ottavo (2^(−3) = 0,125).
Posizionare una parola in codice breve in alto nell'albero blocca tutti i suoi discendenti dall'essere usati — scambi un codice breve per molti potenziali codici più lunghi.
Costruire un albero senza prefisso
Considera 5 simboli con lunghezze l = {1, 2, 3, 3, 3}. Somma di Kraft = 2^(−1) + 2^(−2) + 3·2^(−3) = 0,5 + 0,25 + 0,375 = 1,125 > 1.
Questo supera 1: queste lunghezze sono incompatibili con un codice senza prefisso. Almeno una lunghezza deve aumentare.
Correggi: cambia l_1 da 1 a 2. Nuove lunghezze {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0,5 + 0,375 = 0,875 < 1. Valido, ma incompleto.
Correggi: cambia l_1 da 2 a 2, aggiungi l_2 = 3 per usare la capacità rimanente. Kraft = 0,875; rimanente = 0,125 = 2^(−3): spazio per un'altra foglia a profondità 3.
Perché l'entropia limita la lunghezza del codice
La disuguaglianza di Kraft vincola la struttura del codice (le lunghezze devono adattarsi all'albero). L'entropia di Shannon vincola l'efficienza del codice (la lunghezza media non può battere un limite teorico).
Lunghezze di codice ottimali. Per un simbolo con probabilità p_i, la lunghezza di codice ideale è log₂(1/p_i). I simboli rari meritano codici lunghi; i simboli frequenti meritano codici brevi. Questo rispecchia l'uguaglianza di Kraft: 2^(−l_i) = p_i quando l_i = log₂(1/p_i).
Ma log₂(1/p_i) è raramente un numero intero. Arrotondare per eccesso a ⌈log₂(1/p_i)⌉ dà la lunghezza di Huffman, che soddisfa H ≤ L < H + 1.
Lettura geometrica. Traccia ogni simbolo come un punto nell'albero binario a profondità l_i. La somma di Kraft misura la copertura totale delle foglie. L'entropia misura la media ponderata della profondità, ponderata per la probabilità. Il teorema di Shannon: la profondità media ponderata per la probabilità ≥ il contenuto di informazione medio ponderato per la probabilità.
Verifica del limite di entropia
L'esempio sviluppo: p = [1/2, 1/4, 1/8, 1/8] per i simboli {A, B, C, D}.
Lunghezze ottimali: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Questi sono tutti numeri interi — una corrispondenza perfetta. Codice Huffman: A=0, B=10, C=110, D=111.
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 0,5 + 0,5 + 0,375 + 0,375 = 1,75.
H = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75. L = H esattamente: codice ottimale.
Un esempio completo sviluppo
Pipeline completa: data le probabilità, calcola l'entropia, verifica che un codice soddisfi il limite.
Sorgente: p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
H = 1,75 bit (calcolato sopra).
Un codice a blocco naive: 4 simboli → 2 bit ciascuno → L = 2,0. Overhead rispetto all'entropia: 2,0 − 1,75 = 0,25 bit/simbolo = 12,5% spreco.
Il codice a lunghezza variabile risparmia il 12,5% rispetto al codice a lunghezza fissa. Per messaggi grandi, questo è sostanziale.
Tasso di entropia dell'inglese. Shannon stimò l'entropia dell'inglese scritto a circa 1,0-1,3 bit per carattere, nonostante usi codici ASCII a 5 bit. Questo rapporto 4:1 riflette la ridondanza massiccia nel linguaggio naturale — le lettere comuni si raggruppano, le parole si ripetono, la grammatica vincola le sequenze.
La compressione non può battere l'entropia
Rapporto di compressione: H / (lunghezza del codice a blocco). Per il nostro esempio: 1,75/2,0 = 0,875 — efficienza 87,5%.
Puoi comprimere ulteriormente? Solo usando il contesto: se codifichi coppie o triple di simboli insieme, l'entropia congiunta H(X,Y) potrebbe essere minore di 2·H(X) a causa delle dipendenze statistiche. Questa è l'estensione del teorema della codificazione senza rumore agli n-grammi.