In particolare si costruisce la codifica di stringhe basandosi sulla frequenza relativa di ciascun carattere.
Vediamo un esempio considerando la stringa "Ciao mamma".
Lo svolgimento avviene partendo dalle foglie e raggiungendo la radice comunque.
Ad ogni passaggio si accoppiano le foglie di modo da ottenere un nuovo nodo di peso più basso possibile. Una volta raggiunta una radice comunque si parte da essa e si assegna per ogni coppia di archi un 1 e uno 0. Le sequenze di bit risultanti saranno la codifica ottimale per la compressione di quella stringa specifica.
In questo caso ad esempio una possibile codifica di Huffman (a seconda dell'ordine con cui si accoppiano nodi di pari peso e a seconda dell'assegnazione degli 1 e 0 agli archi potremo avere più codifiche) è quella sopra rappresentata e il risultato quindi sarebbe:
Ciao mamma -> 111-110-00-101-100-01-00-01-01-00
Quindi invece di 10 byte ne usiamo soltanto 3 (più i dati utili per ricostruire l'albero in decodifica)
Vediamo i passaggi intermedi:
E' importante notare come il codice ottenuto assegni meno bit ai caratteri più frequenti e di più a quelli meno presenti nella stringa. Notare che il codice ottenuto è univocamente decifrabile, non ci sono infatti parole che sono il prefisso di altre.
Una applicazione che usi questo tipo di approccio per comprimere dati dovrà basarsi o su frequenze dei caratteri precalcolate nel dominio dell'applicazione (e quindi disponibili a priori per comprimere e decomprimere) oppure sulle frequenze specifiche della stringa da comprimere (in questo caso la tabella di frequenza dovrà essere registrata assieme al testo compresso per consentire la decodifica).
Esistono diverse varianti dell'algoritmo di Huffman.
Nessun commento:
Posta un commento