Huffman in C

Programmazione » Huffman in C
01/01/1970 - 21

Esempio dell'algoritmo di Huffman in C/C++

---

In questo articolo viene rilasciato un esempio di implementazione dell'algoritmo di Huffman in C/C++.
Non verrà spiegato invece come funziona l'algoritmo (dato che in rete esistono molte informazioni al riguardo).
Per farla breve comunque il concetto di questo algoritmo è quello di sostituire i simboli più ricorrenti all'interno di un file con dei simboli con valore binario ridotto. I simboli binari per la sostituzione si ottengono creando una struttura dati ad albero particolare: albero di Huffman.
Questo algoritmo è attualmente utilizzato nei più noti software di compressione dati, combinato con altri algoritmi basati sul dizionario (come LZ77).

Questo codice non è particolarmente ottimizzato, tuttavia le prestazioni sono comunque interessanti in termini di velocità.

A differenza di altre implementazioni in questa, l'albero viene memorizzato con un sistema piuttosto efficace che consiste semplicemente in una lista ordinata di simboli all'inizio del file compresso.

Per testare questa implementazione dell'algoritmo di Huffman si può utilizzare lo stesso software con interfaccia grafica proposto nell'articolo riguardante l'implementazione in C/C++ di LZW

Autore: Ugo Cirmignani

---