Codici di Huffman: esempi, applicazione

Al momento, poche persone ci pensanocome funziona la compressione dei file. Rispetto al passato, utilizzare un personal computer è diventato molto più semplice. E quasi tutti coloro che lavorano con il file system utilizzano gli archivi. Ma poche persone pensano a come funzionano e a come vengono compressi i file. La primissima versione di questo processo erano i codici Huffman, e sono utilizzati fino ad oggi in vari archiviatori popolari. Molti utenti non pensano nemmeno a quanto sia facile comprimere un file e come funziona. In questo articolo vedremo come si verifica la compressione, quali sfumature aiutano ad accelerare e semplificare il processo di codifica e scopriremo anche qual è il principio di costruzione di un albero di codifica.

Storia dell'algoritmo

Il primo algoritmo per la conduzione efficacela codifica delle informazioni elettroniche divenne un codice proposto da Huffman a metà del ventesimo secolo, precisamente nel 1952. È lui che al momento è l'elemento di base principale della maggior parte dei programmi creati per comprimere le informazioni. Attualmente, alcune delle fonti più popolari che utilizzano questo codice sono ZIP, ARJ, archivi RAR e molti altri.

Inoltre, questo algoritmo di Huffman viene applicato acompressione di immagini JPEG e altri oggetti grafici. Ebbene, tutti i fax moderni utilizzano anche la codifica inventata nel 1952. Nonostante sia passato così tanto tempo dalla creazione del codice, è ancora utilizzato nelle nuove shell e su apparecchiature di tipo vecchio e moderno.

Il principio della codifica efficiente

L'algoritmo di Huffman si basa sullo schemaconsente di sostituire i caratteri più probabili e comuni con codici binari. E quelli meno comuni vengono sostituiti con codici più lunghi. Il passaggio a codici Huffman lunghi avviene solo dopo che il sistema ha utilizzato tutti i valori minimi. Questa tecnica consente di ridurre al minimo la lunghezza del codice per ogni carattere del messaggio originale nel suo complesso.

Il punto importante è quello all'iniziola probabilità di codifica dell'occorrenza delle lettere dovrebbe essere già nota. È da loro che verrà composto il messaggio finale. Sulla base di questi dati, viene costruito un albero del codice di Huffman, sulla base del quale verrà eseguito il processo di codifica delle lettere nell'archivio.

Esempio di codice di Huffman

Per illustrare l'algoritmo, prendiversione grafica della creazione di un albero del codice. Affinché l'uso di questo metodo sia efficace, vale la pena chiarire la definizione di alcuni dei valori necessari per il concetto di questo metodo. L'insieme di un insieme di archi e nodi diretti da nodo a nodo è chiamato grafo. L'albero stesso è un grafico con un insieme di proprietà specifiche:

• ogni nodo non può includere più di uno degli archi;
• uno dei nodi deve essere la radice dell'albero, cioè gli archi non devono assolutamente entrarvi;
• se inizi a muoverti lungo gli archi dalla radice, questo processo dovrebbe consentirti di raggiungere assolutamente uno qualsiasi dei nodi.

C'è anche un tale concetto incluso nei codiciHuffman è come una foglia su un albero. Rappresenta un nodo da cui non dovrebbero uscire archi. Se due nodi sono collegati da un arco, allora uno di loro è un genitore, l'altro è un figlio, a seconda di quale nodo esce l'arco e da quale entra. Se due nodi hanno lo stesso nodo padre, vengono comunemente definiti nodi di pari livello. Se, oltre alle foglie, i nodi hanno diversi archi, questo albero è chiamato binario. Questo è esattamente ciò che è l'albero di Huffman. La particolarità dei nodi di questa costruzione è che il peso di ogni genitore è uguale alla somma del peso di tutti i suoi figli nodali.

Algoritmo di costruzione di alberi di Huffman

La creazione di un codice Huffman viene eseguita dalle lettereinserire l'alfabeto. Viene creato un elenco di quei nodi che sono liberi nel futuro albero del codice. Il peso di ogni nodo in questo elenco dovrebbe essere lo stesso della probabilità di occorrenza della lettera del messaggio corrispondente a quel nodo. In questo caso, tra diversi nodi liberi dell'albero futuro, viene selezionato quello che pesa di meno. Inoltre, se gli indicatori minimi vengono osservati in più nodi, è possibile scegliere liberamente una delle coppie.

Quindi viene creato il genitorenodo, che dovrebbe pesare tanto quanto pesa la somma di questa coppia di nodi. Successivamente, il genitore viene inviato all'elenco con i nodi liberi e i figli vengono rimossi. In questo caso, gli archi ricevono gli indicatori corrispondenti, uno e zero. Questo processo viene ripetuto esattamente per il tempo necessario per lasciare un solo nodo. Quindi le cifre binarie vengono scritte dall'alto verso il basso.

Miglioramento dell'efficienza di compressione

Per migliorare l'efficienza di compressione, è necessarioQuando si crea un albero del codice, utilizzare tutti i dati relativi alla probabilità che le lettere appaiano in un particolare file allegato all'albero e non consentire che vengano disperse su un numero elevato di documenti di testo. Se si scorre prima questo file, è possibile calcolare immediatamente le statistiche sulla frequenza con cui vengono trovate le lettere dell'oggetto da comprimere.

Accelera il processo di compressione

Per velocizzare l'algoritmo, identificare le letteredovrebbe essere eseguito non in base agli indicatori della probabilità di comparsa di una particolare lettera, ma in base alla frequenza della sua comparsa. Questo rende l'algoritmo più semplice e molto più veloce con cui lavorare. Inoltre evita le operazioni di divisione e virgola mobile.

Inoltre, operando in questa modalità, il dinamicoil codice Huffman, o meglio l'algoritmo stesso, non è soggetto ad alcuna modifica. Ciò è principalmente dovuto al fatto che le probabilità sono direttamente proporzionali alle frequenze. Vale la pena prestare particolare attenzione al fatto che il peso finale del file o del cosiddetto nodo radice sarà uguale alla somma del numero di lettere nell'oggetto da elaborare.

conclusione

Codici Huffman: semplici e consolidatiun algoritmo che è ancora utilizzato da molti noti programmi e aziende. La sua semplicità e chiarezza consentono di ottenere risultati efficaci di compressione di file di qualsiasi dimensione e di ridurre notevolmente lo spazio su disco di archiviazione. In altre parole, l'algoritmo di Huffman è uno schema studiato ed elaborato a lungo, la cui rilevanza non diminuisce fino ad oggi.

E grazie alla possibilità di ridurre le dimensioni del file,la loro trasmissione sulla rete o con altri mezzi diventa più facile, veloce e conveniente. Lavorando con l'algoritmo, puoi comprimere assolutamente qualsiasi informazione senza danneggiarne la struttura e la qualità, ma con il massimo effetto di ridurre il peso del file. In altre parole, la codifica di Huffman è stata e rimane il metodo più popolare e attuale per la compressione delle dimensioni dei file.