Calcolatore lunghezze Huffman

La codifica di Huffman è il classico codice prefisso binario a ridondanza minima usato in ZIP, PNG, DEFLATE, JPEG e in innumerevoli laboratori didattici. In base a quanto spesso compare ogni simbolo, l'algoritmo assegna stringhe di bit più corte ai simboli frequenti e più lunghe a quelli rari, così che nessun codice sia prefisso di un altro. Questo calcolatore di lunghezze del codice Huffman accetta un elenco di frequenze strettamente positive, costruisce l'albero di Huffman ottimale con spareggio deterministico e restituisce la lunghezza di codice di ogni simbolo, il numero totale di bit codificati del multinsieme, la lunghezza media, l'entropia di Shannon in bit per il confronto, la ridondanza e la somma di Kraft. Un alfabeto a un solo simbolo riceve lunghezza zero, il codice vuoto che soddisfa ancora la proprietà di prefisso.

Cosa significano le lunghezze Huffman ottimali e come si costruisce l'albero

Un codice prefisso binario associa a ogni simbolo dell'alfabeto una stringa di bit tale che nessun codice sia prefisso proprio di un altro; tale proprietà consente al decodificatore di analizzare un flusso concatenato senza separatori. La costruzione è semplice ed esatta: si colloca ogni simbolo in una coda di priorità indicizzata per frequenza; si estraggono ripetutamente i due nodi più leggeri, si crea un genitore il cui peso è la loro somma e si reinserisce il genitore finché resta una sola radice.

La lunghezza di codice di una foglia è la sua profondità in quell'albero. Quando due nodi condividono lo stesso peso, questa implementazione spartisce con un identificatore di inserimento stabile, così che ingressi identici producano sempre gli stessi vettori di lunghezze tra runtime. Per un solo simbolo la lunghezza ottimale è zero: il codice vuoto non usa bit e forma ancora un codice prefisso valido per un alfabeto singleton.

Con due o più simboli ogni lunghezza è almeno uno. La somma di Kraft di due elevato a meno ogni lunghezza è al più uno per qualsiasi codice prefisso completo ed è riportata affinché Lei possa verificare la disuguaglianza di Kraft senza ricostruire l'albero.

Dove servono le lunghezze di Huffman, e i loro limiti

I corsi di teoria dell'informazione e i colloqui di programmazione usano un calcolatore di lunghezze del codice Huffman affinché gli studenti verifichino profondità ottimali e bit totali senza disegnare a mano l'albero di ogni tabella di frequenze. Gli ingegneri della compressione confrontano la lunghezza media di Huffman con l'entropia di Shannon per dimensionare intestazioni, scegliere tabelle statiche o dinamiche, o insegnare perché i codici in stile DEFLATE restano vicini al bound di entropia. Una validazione fallita non consuma saldo.

Mantenga gli alfabeti entro il massimo pubblicato, invii solo conte strettamente positive anziché mescolare zeri che richiederebbero casi speciali, e fissi nei test l'array lengths restituito.