La Codifica di Huffman è un algoritmo di codifica dell’entropia usato per la compressione di dati, basato sul principio di trovare il sistema ottimale per codificare stringhe basato sulla frequenza relativa di ciascun carattere.
Albero di Huffman per la codifica della stringa “this is an example of a huffman tree“.
Il Teorema di Shannon ci dice che una stringa di caratteri può essere codificata utilizzando almeno un numero di bit pari a N * E dove N è il numero di caratteri di tale stringa ed E è l’entropia.
Tramite la Codifica di Huffman riusciamo ad ottenere una compressione quasi ottimale dei dati cioè pari al limite di Shannon con un eccesso di al più N bit.
Ecco il codice che ho scritto per implementare la tale codifica in C++:
Huffman.h download
Huffman.cpp download
Da qui è possibile scaricare i file già compilati eseguibili (a 64 bit):
download linux
download mac
Per scaricare i sorgenti e i binari già compilati tramite git:
git clone https://github.com/ShinDarth/Huffman-Encoding.git huffman
AzerothCore
ChromieCraft