Codice di Huffman
Codice a lunghezza fissa
Risparmiato
Entropia

Simbolo Occorrenze Codice Bit Bit in totale

Ulteriori informazioni sulla codifica di Huffman

Costruttore di codici di Huffman

Perché una lettera frequente come la e dovrebbe occupare tanti bit quanti una rara come la q? La codifica di Huffman dà codici brevi ai simboli frequenti e codici lunghi a quelli rari, e lo fa nel miglior modo possibile. Scrivi un testo o scegli un esempio e costruisci il suo albero di Huffman un passo alla volta: i due alberi più leggeri si uniscono sotto un nuovo nodo, ancora e ancora, finché non resta un solo albero. A quel punto ogni percorso dalla cima compone un codice, e puoi seguire ogni simbolo attraverso i bit codificati. Scrivi un testo o scegli un esempio. Ogni simbolo parte come una foglia con il suo numero di occorrenze. Procedi passo per passo nella costruzione: ogni passo unisce i due alberi più leggeri sotto un nuovo nodo con la loro somma, finché non resta un solo albero. A quel punto il percorso dalla cima a una foglia dà il suo codice, 0 per sinistra e 1 per destra. Fai clic su una foglia, una riga o un pezzo dei bit per seguire un simbolo, e confronta il totale con un codice a lunghezza fissa e con l'entropia.

Come funziona

  1. Scrivi o incolla un testo, oppure scegli un esempio come ABRACADABRA o MISSISSIPPI RIVER.
  2. Procedi nella costruzione con Passo successivo, oppure premi Avvia: ogni passo unisce i due alberi più leggeri sotto un nodo con la loro somma.
  3. Quando l'albero è completo, fai clic su una foglia, una riga della tabella o un pezzo dei bit per seguire un simbolo, e confronta i totali nei riquadri.

Come si costruisce l'albero

Conta quante volte compare ogni simbolo e fai di ciascuno un albero di una sola foglia, pesato con il suo numero di occorrenze. Poi ripeti un unico passo semplice: prendi i due alberi con i pesi più piccoli e appendili sotto un nuovo nodo il cui peso è la loro somma. Ogni passo lascia un albero in meno, quindi dopo n − 1 passi per n simboli resta un solo albero. I simboli rari sono stati uniti per primi e stanno in profondità; quelli comuni sono stati uniti tardi e stanno vicino alla cima.

Leggere i codici

Scendi dalla cima: un passo a sinistra aggiunge uno 0, un passo a destra un 1. Il percorso fino a una foglia è il codice di quel simbolo. Poiché i simboli stanno solo nelle foglie, nessun codice è l'inizio di un altro, quindi una sequenza di bit si può decodificare senza alcun separatore: segui i bit giù per l'albero e, ogni volta che raggiungi una foglia, scrivi il suo simbolo e ricomincia dalla cima. Per ABRACADABRA, Huffman ha bisogno di 23 bit, contro i 33 di un codice fisso di 3 bit per lettera.

Domande frequenti

Perché il codice di Huffman è il migliore possibile?

Tra tutti i codici che assegnano a ogni simbolo una propria sequenza di bit interi, nessuno ha un totale più breve per le occorrenze date. La dimostrazione segue la costruzione: in un codice ottimo i due simboli più rari si possono sempre rendere fratelli al livello più profondo, e unirli lascia un problema più piccolo dello stesso tipo. Il numero totale di bit è uguale alla somma dei pesi di tutti i nodi interni dell'albero.

Che cos'è un codice prefisso?

Un codice in cui nessuna parola di codice è l'inizio di un'altra, come 0, 10, 110 e 111. Questa proprietà permette a un decodificatore di leggere un flusso di bit senza separatori, perché sa sempre dove finisce una parola di codice. Ogni codice di Huffman è un codice prefisso: i simboli stanno solo nelle foglie dell'albero.

L'albero di Huffman è unico?

Non del tutto: quando due alberi hanno lo stesso peso, si può prendere prima l'uno o l'altro, e sinistra e destra si possono scambiare. Scelte diverse danno codici diversi, ma sempre lo stesso numero totale di bit. Il costruttore risolve i pareggi sempre nello stesso modo, quindi un testo dà sempre lo stesso albero.

Quanto si avvicina Huffman all'entropia?

La lunghezza media dei codici è almeno pari all'entropia e la supera di meno di un bit. È uguale all'entropia quando ogni probabilità è una potenza di un mezzo, come nell'esempio delle occorrenze dimezzate. La codifica aritmetica e i moderni range coder evitano il limite dei bit interi e si avvicinano ancora di più.

Il mio testo viene inviato da qualche parte?

No. L'albero e i codici vengono calcolati nel tuo browser, e il tuo testo resta nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor