Come Comprimere i Dati Usando la Codifica Huffman: 10 Passaggi

Sommario:

Come Comprimere i Dati Usando la Codifica Huffman: 10 Passaggi
Come Comprimere i Dati Usando la Codifica Huffman: 10 Passaggi

Video: Come Comprimere i Dati Usando la Codifica Huffman: 10 Passaggi

Video: Come Comprimere i Dati Usando la Codifica Huffman: 10 Passaggi
Video: Buongiorno pescheria! 2024, Marzo
Anonim

L'algoritmo di Huffman viene utilizzato per comprimere o codificare i dati. Normalmente, ogni carattere in un file di testo è memorizzato come otto bit (cifre, 0 o 1) che si associano a quel carattere usando una codifica chiamata ASCII. Un file codificato da Huffman rompe la rigida struttura a 8 bit in modo che i caratteri più comunemente usati siano memorizzati in pochi bit ('a' potrebbe essere "10" o "1000" anziché l'ASCII, che è "01100001"). I caratteri meno comuni, quindi, occuperanno spesso molto più di 8 bit ('z' potrebbe essere "00100011010"), ma poiché si verificano così raramente, la codifica di Huffman, nel complesso, crea un file molto più piccolo dell'originale.

Passi

Parte 1 di 2: codifica

Comprimi i dati usando la codifica Huffman Passaggio 1
Comprimi i dati usando la codifica Huffman Passaggio 1

Passaggio 1. Contare la frequenza di ciascun carattere nel file da codificare

Includi un carattere fittizio per contrassegnare la fine del file: questo sarà importante in seguito. Per ora, chiamalo EOF (fine del file) e contrassegnalo come avente una frequenza di 1.

Ad esempio, se vuoi codificare un file di testo che legge "ab ab cab", avresti 'a' con frequenza 3, 'b' con frequenza 3, ' ' (spazio) con frequenza 2, 'c' con frequenza 1 e EOF con frequenza 1

Comprimi i dati usando la codifica di Huffman Passaggio 2
Comprimi i dati usando la codifica di Huffman Passaggio 2

Passaggio 2. Archivia i caratteri come nodi dell'albero e inseriscili in una coda prioritaria

Costruirai un grande albero binario con ogni carattere come una foglia, quindi dovresti memorizzare i caratteri in un formato tale che possano diventare nodi dell'albero. Metti questi nodi in una coda di priorità con la frequenza di ogni carattere come priorità del suo nodo.

  • Un albero binario è un formato di dati in cui ogni dato è un nodo che può avere fino a un genitore e due figli. È spesso disegnato come un albero ramificato, da cui il nome.
  • Una coda è una raccolta di dati con un nome appropriato in cui la prima cosa che entra in coda è anche la prima cosa che esce (come aspettare in fila). In una coda di priorità, i dati vengono memorizzati in ordine di priorità, in modo che la prima cosa che esce sia la cosa più urgente, la cosa con la priorità più bassa, piuttosto che la prima cosa in coda.
  • Nell'esempio "ab ab cab", la tua coda prioritaria sarebbe simile a questa: {'c':1, EOF:1, ' ':2, 'a':3, 'b':3}
Comprimi i dati usando la codifica Huffman Passaggio 3
Comprimi i dati usando la codifica Huffman Passaggio 3

Passaggio 3. Inizia a costruire il tuo albero

Rimuovi (o elimina dalla coda) le due cose più urgenti dalla coda di priorità. Crea un nuovo nodo dell'albero come genitore di questi due nodi, memorizzando il primo nodo come figlio sinistro e il secondo come figlio destro. La priorità del nuovo nodo dovrebbe essere la somma delle priorità del suo figlio. Quindi accodare questo nuovo nodo nella coda di priorità.

La coda di priorità ora ha questo aspetto: {' ':2, nuovo nodo:2, 'a':3, 'b':3}

Comprimi i dati usando la codifica Huffman Passaggio 4
Comprimi i dati usando la codifica Huffman Passaggio 4

Passaggio 4. Finisci di costruire il tuo albero:

ripetere il passaggio precedente fino a quando non c'è solo un nodo nella coda. Nota che oltre ai nodi che hai creato per i personaggi e le loro frequenze, eliminerai anche la coda, trasformandoti in alberi e accodando nuovamente i nodi genitori, nodi che sono già essi stessi alberi.

  • Quando hai finito, l'ultimo nodo nella coda sarà la radice dell'albero di codifica, con tutti gli altri nodi che si diramano da esso.
  • I caratteri usati più frequentemente saranno le foglie più vicine alla cima dell'albero, mentre i caratteri usati raramente saranno posizionati alla base dell'albero, più lontano dalla radice.
Comprimi i dati usando la codifica Huffman Passaggio 5
Comprimi i dati usando la codifica Huffman Passaggio 5

Passaggio 5. Creare una mappa di codifica. Cammina attraverso l'albero per raggiungere ogni personaggio. Ogni volta che visiti il figlio sinistro di un nodo, questo è uno "0". Ogni volta che visiti il figlio destro di un nodo, è un "1". Quando arrivi a un personaggio, memorizza il carattere con la sequenza di 0 e 1 necessaria per arrivarci. Questa sequenza è ciò che il carattere verrà codificato come nel file compresso. Memorizza i personaggi e le loro sequenze in una mappa.

  • Ad esempio, inizia dalla radice. Visita il figlio sinistro della radice, quindi visita il figlio sinistro di quel nodo. Poiché il nodo in cui ti trovi ora non ha figli, hai raggiunto un personaggio. Questo è ' '. Dato che sei andato a sinistra due volte per arrivare qui, la codifica per ' ' è "00".
  • Per questo albero, la mappa sarà simile a questa: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}.
Comprimi i dati usando la codifica Huffman Passaggio 6
Comprimi i dati usando la codifica Huffman Passaggio 6

Passaggio 6. Nel file di output, includi la mappa di codifica come intestazione

Ciò consentirà la decodifica del file.

Comprimi i dati usando la codifica Huffman Passaggio 7
Comprimi i dati usando la codifica Huffman Passaggio 7

Passaggio 7. Codifica il file

Per ogni carattere nel file da codificare, scrivi la sequenza binaria che hai memorizzato nella mappa. Una volta terminata la codifica del file, assicurati di aggiungere l'EOF alla fine.

  • Per il file "ab ab cab", il file codificato sarà simile a questo: "1011001011000101011011".
  • I file sono memorizzati come byte (8 bit o 8 cifre binarie). Poiché l'algoritmo di codifica di Huffman non utilizza il formato a 8 bit, i file codificati spesso non avranno lunghezze multiple di 8. Le cifre rimanenti verranno riempite con 0. In questo caso, verranno aggiunti due 0 alla fine del file, che assomiglia a un altro spazio. Questo potrebbe essere un problema: come fa il decoder a sapere quando interrompere la lettura? Tuttavia, poiché abbiamo incluso un carattere di fine file, il decoder arriverà a questo e poi si fermerà, ignorando qualsiasi altra cosa sia stata aggiunta dopo.

Parte 2 di 2: decodifica

Comprimi i dati usando la codifica Huffman Passaggio 8
Comprimi i dati usando la codifica Huffman Passaggio 8

Passaggio 1. Leggi un file codificato da Huffman

Per prima cosa, leggi l'intestazione, che dovrebbe essere la mappa di codifica. Usalo per creare un albero di decodifica nello stesso modo in cui hai creato l'albero che hai usato per codificare il file. I due alberi dovrebbero essere identici.

Comprimi i dati usando la codifica Huffman Passaggio 9
Comprimi i dati usando la codifica Huffman Passaggio 9

Passaggio 2. Leggere il binario una cifra alla volta

Attraversa l'albero mentre leggi: se leggi uno '0', vai al figlio sinistro del nodo in cui ti trovi, e se leggi un '1', vai al figlio destro. Quando raggiungi una foglia (un nodo senza figli), sei arrivato a un personaggio. Scrivi il carattere nel file decodificato.

A causa del modo in cui i caratteri sono memorizzati nell'albero, i codici per ogni carattere hanno una proprietà prefisso, in modo che la codifica binaria di un carattere non possa mai verificarsi all'inizio della codifica di un altro carattere. La codifica per ogni carattere è totalmente unica. Questo rende la decodifica molto più semplice

Comprimi i dati usando la codifica di Huffman Passaggio 10
Comprimi i dati usando la codifica di Huffman Passaggio 10

Passaggio 3. Ripetere fino a raggiungere l'EOF

Congratulazioni! Hai decodificato il file.

Consigliato: