Informazioni su questo esperimento
Ogni file ZIP, immagine PNG e traccia MP3 è più piccola dei dati grezzi perché elimina le ripetizioni. Prova due classici metodi senza perdita di dati con un tuo messaggio. La codifica a lunghezza di sequenza sostituisce una sequenza di simboli identici con un conteggio: è eccellente per le immagini semplici e inutile per il testo comune. La codifica di Huffman assegna codici brevi ai simboli frequenti e codici lunghi a quelli rari. I codici vengono costruiti passo dopo passo a partire da un albero, ottenendo un risultato che dista meno di un bit per simbolo dal limite teorico scoperto da Claude Shannon nel 1948.
Obiettivi di apprendimento
- Spiega la differenza tra compressione senza perdita di dati e compressione con perdita di dati
- Codifica e decodifica un messaggio con la codifica a lunghezza di sequenza e spiega quando è utile
- Costruisci un albero di Huffman unendo ripetutamente i due simboli meno frequenti
- Leggi le parole di codice dall’albero e spiega perché nessun codice è l’inizio di un altro
- Confronta le dimensioni compresse con il limite di entropia e calcola un rapporto di compressione
Come si usa
- 1Scegli la riga Pixel e la codifica per lunghezza delle sequenze. Di quanti bit ha bisogno la riga prima e dopo? Perché funziona così bene?
- 2Passa a Hamlet con la codifica per lunghezza delle sequenze. Perché il messaggio diventa più grande?
- 3Scegli Mississippi e premi «Crea l’albero». Quali due alberi vengono uniti a ogni passaggio e perché?
- 4Quando l’albero è completo, trova la parola di codice della lettera più comune e di quella più rara. Conta i bit.
- 5Decodifica a mano i primi bit del messaggio codificato, percorrendo l’albero dalla radice.
- 6Scrivi un messaggio che usa una sola lettera e poi uno in cui tutte le lettere sono diverse. In entrambi i casi, confronta la codifica di Huffman con il limite di entropia.
Il modello
Ipotesi
- Il messaggio originale usa 8 bit per carattere, come in ASCII.
- Ogni coppia lunghezza della sequenza viene memorizzata come un contatore a 8 bit e un carattere a 8 bit, quindi le sequenze più lunghe di 255 vengono suddivise.
- La dimensione Huffman conta solo il messaggio codificato. Un file reale deve memorizzare anche la tabella dei codici o le frequenze, un aspetto importante per i messaggi brevi.
- Quando due alberi hanno lo stesso peso, viene scelto per primo quello creato per primo, e l’albero più leggero diventa il ramo 0. Altre regole per risolvere i pareggi producono codici diversi della stessa lunghezza totale.
Provalo in classe
- Q1Codifica BBBBBWWWBBBBBBBB con la codifica a lunghezza di sequenza. Di quanti byte ha bisogno?
- Q2Costruisci l’albero di Huffman per le frequenze A 5, B 2, R 2, C 1, D 1 e trova il numero totale di bit per ABRACADABRA.
- Q3Perché un codice di Huffman deve essere un codice prefisso? Cosa andrebbe storto se A fosse 0 e B fosse 01?
- Q4Un testo usa 8 lettere diverse con la stessa frequenza. Qual è la sua entropia e Huffman può comprimerlo?
- Q5JPEG e MP3 comprimono molto più della codifica di Huffman. A cosa rinunciano per riuscirci?
Domande frequenti
Dove viene usata oggi la codifica di Huffman?
In molti formati di uso comune: ZIP e gzip (il metodo DEFLATE), immagini PNG, immagini JPEG dopo la fase con perdita e audio MP3. Di solito è l’ultima fase, dopo che un altro metodo ha trasformato le ripetizioni in numeri.
Si può comprimere qualsiasi file?
No. Un metodo senza perdita che riducesse le dimensioni di ogni file permetterebbe di comprimere il risultato ancora e ancora, il che è impossibile perché i file corti sono meno numerosi di quelli lunghi. I dati casuali e i file già compressi di solito non diventano più piccoli.
L’albero di Huffman è unico?
Non sempre. Quando le frequenze sono uguali, scelte diverse producono alberi e parole di codice diversi, ma tutti gli alberi di Huffman per le stesse frequenze danno lo stesso numero totale di bit.