Home » Programmazione

Implementazione dell'algoritmo di Huffman in c/c++

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

By kingk (art. no 21)



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

Algoritmo di Huffman in C/C++

Tags: Huffman in C - Algoritmi base di compressione dati Huffman - Implementazione Huffman in C

Un implementazione efficace dell'algoritmo LZW in C/C++ by Ugo Cirmignani

Descrizione implementazione ed esempio dell'algoritmo LZW in C/C++

By kingk (art. no 18)



In questo articolo viene illustrato brevemente l'algoritmo LZW, vedremo le insidie ed i consigli per una buona implementazione dell'algoritmo ed una sua buona implementazione in C/C++. Oltre al codice dimostrativo troverete un piccolo software in C++ denominato 'FAC' dotato di interfaccia grafica questo software è capace di comprimere/decomprimere directory in vari formati tra cui LZW con il codice compreso in questo articolo, il software in questione utilizza un algoritmo di concatenamento file per comprimere intere directory in file unici.

Senza soffermarci troppo sulla storia di LZW passiamo a descrivere le caratteristiche principali dell'algoritmo:
-Algoritmo Loseless (nessuna perdita di informazioni con la compressione/decompressione dei files)
-Ottima velocità di compressione/decompressione
-Buon rapporto di compressione
-Principio di funzionamento basato su dizionario (infatti l'algoritmo è un evoluzione del primo noto algoritmo a dizionario: LZ77)
-Possibilità di comprimere dati in streaming senza conoscere i dati prima della compressione

LZW è attualmente utilizzato soprattutto nella compressione delle immagini dei più noti formati di immagini esistenti, è un algoritmo libero da brevetti da non molti anni per questo motivo la sua diffusione è ancora limitata.

L'algoritmo basa il suo funzionamento sul principio di utilizzare un dizionario che viene costruito man mano durante la lettura di un file/stream di dati.
Ma cosa significa utilizzare un dizionario per la compressione file?
Il principio di funzionamento è molto banale, consiste nel sostituire un insieme di simboli ricorrenti con simboli abbreviati nei dati di output.

Per fare un esempio di un algoritmo con dizionario possiamo immaginare di comprimere un SMS sostituendo le parole più utilizzate con dei numeri binari.
Ad esempio utilizzando 16bit potremmo disporre di ben 65535 parole nel nostro nuovo dizionario compresso, più che sufficienti per comporre un SMS.

Il risparmio di questo algoritmo immaginario in termini di dati sarebbe notevole, infatti ogni parola potrebbe occupare solo 2 simboli (in informatica ogni carattere di testo occupa 8bit), con una compressione del genere potremmo arrivare a comporre SMS con un numero di parole quintuplicato rispetto ad un SMS classico.

Sfortunatamente in informatica nella maggior parte dei casi bisogna lavorare con dei dati molto vari e non ricorsivi come delle semplici parole, trovare un algoritmo buono per molte casistiche non è un impresa da poco, ma è proprio quello che LZW garantisce.

Come funziona LZW?
L'algoritmo inizializza in memoria un dizionario di base composto da 256 simboli (tutti i valori che 1 byte può assumere).

L'algoritmo procede leggendo byte dopo byte tutti i dati in ingresso accodandoli tra loro in un buffer al fine di formare simboli finché tali simboli sono presenti nel dizionario e producendo nel caso contrario il valore della posizione occupata dall'ultimo simbolo riscontrato nel buffer come output. I simboli non riscontrati vengono inseriti nel dizionario in maniera dinamica.

Per comprendere meglio il processo prendiamo ad esempio una parola da comprimere formata da 11 caratteri: ABCABEFGHIL

Dopo la prima lettura il buffer in ingresso sarà formato da: A
Il carattere A è un simbolo presente nel dizionario dato che questo è stato inizializzato con tutti i 256 simboli ad 8 bit, se nella memoria di buffer è presente un simbolo riscontrabile nel dizionario l'algoritmo continua la lettura accodando i byte nuovi a quelli che formano il simbolo riscontrato nel buffer.
Nel secondo passaggio l'algoritmo legge B, ed il buffer diventa: AB

AB è un simbolo non presente nel dizionario dato che inizialmente è formato da simboli ad un carattere singolo, a questo punto l'algoritmo inserisce il nuovo simbolo mai riscontrato AB nella prima posizione disponibile nel dizionario ossia la posizione n 257 che conterrà quindi il simbolo AB.
Aggiunto questo simbolo l'algoritmo produrrà un output corrispondente alla posizione dell'ultimo simbolo riscontrato ossia il valore della posizione associato al carattere A precisamente: 65

L'algoritmo procede scartando il simbolo mandato in output dal buffer e accodando il nuovo byte da leggere all'ultimo letto, il buffer diventa cosi BC.
Il nuovo simbolo BC non è presente nel dizionario, l'algoritmo inserisce il nuovo simbolo BC nella posizione 258, come output restituisce sempre il valore della posizione dell'ultimo simbolo riscontrato in questo il valore 66 associato al simbolo B.

Il processo continua e il buffer diventa: CA ma anche il simbolo CA non è presente nel dizionario, l'algoritmo produce come output la posizione del simbolo C cioè : 67 e inserisce il nuovo simbolo CA nella posizione 259

Nel prossimo step il buffer diventa AB, AB è un simbolo presente nel dizionario, l'algoritmo non produce nessun output e continua con la lettura (la compressione ha cosi inizio).
Il buffer diventa quindi: ABE, questo simbolo non è presente nel dizionario in questo caso come output abbiamo 257 (il valore del simbolo AB) il nuovo simbolo inserito nel dizionario è: ABE con valore 260 ed il buffer diventa EF.

L'algoritmo procede in questo modo finché i dati in ingresso non terminano.

La decompressione avviene in modo del tutto analogo alla compressione, ma con qualche piccola differenza facilmente intuibile.

Dal punto di vista logico l'algoritmo è piuttosto semplice da comprendere, dal punto di vista pratico una sua implementazione presenta notevoli difficoltà tecniche:

1) L'uso di memoria deve essere ottimizzato all'interno del codice, bisogna trovare un sistema per memorizzare un dizionario molto vasto in poco spazio dato che è molto facile riempire la ram di un calcolatore con una cattiva implementazione di LZW.

2 ) La ricerca dei simboli nel dizionario deve essere ottimizzata altrimenti il tempo per comprimere dati può rendere l'algoritmo inutilizzabile

3 ) I simboli devono essere scritti in un formato con bit-size variabile a seconda delle dimensioni del dizionario durante la fase di compressione per massimizzare i benefici dell'algoritmo, i linguaggi di programmazione non consentono di scrivere dati in un numero di bit non multiplo di 8 con funzioni convenzionali.

4) Bisogna limitare le dimensioni del dizionario, in informatica la grandezza dei numeri non è illimitata

5) Bisogna resettare il dizionario quando questo diventa pieno o il rapporto di compressione diventa sconveniente, dato che durante la compressione con questo metodo il rapporto di compressione tende molto facilmente al degrado a seconda della porzione di dati da comprimere.

Ho trovato una soluzione per ognuno di questi punti nella mia implementazione dell'algoritmo presente in questo articolo, alcune soluzioni non sono state ottimizzate al 100% per questioni di tempo, ma tuttavia mi ritengo comunque molto soddisfatto di questa mia buona implementazione di LZW


Vediamo bene le soluzioni ai problemi citati:

1)Per limitare lo spazio occupato dal dizionario si può conservare in memoria solamente una lista di coppie di variabili per ogni simbolo del dizionario esattamente una coppia prefisso/ultimo carattere. Si può notare che ogni nuovo simbolo da inserire nel dizionario non è altro che un vecchio simbolo presente nel dizionario con un ultimo carattere in più. Basta quindi memorizzare il valore del vecchio simbolo e il carattere che forma il nuovo simbolo e non memorizzare il nuovo simbolo per intero.
Nel primo passo di memorizzazione dell'esempio precedente l'inserimento del simbolo AB nel dizionario diventa qualcosa del tipo: prefisso 65 carattere B

2)In molte implementazioni di LZW per risolvere i problemi dei tempi di ricerca dei simboli all'interno del dizionario si utilizza un algoritmo di Hash per la ricerca, ma una soluzione simile comporta però molti svantaggi: L'algoritmo di Hash è un ulteriore complicazione all'interno di un codice non molto semplice, è difficile scrivere uno di questi algoritmi in modo perfetto, il costo di un algoritmo del genere poi non è pari a 1 ma può aumentare a seconda del tipo di dizionario che l'algoritmo crea in modo casuale, inoltre questo comporta un necessario incremento della memoria da dedicare al salvataggio del dizionario molte porzioni di memoria verranno sprecate a svantaggio delle capacità massime di compressione. Ho risolto questo punto per l'implementazione di questo algoritmo con una soluzione davvero ottimale che garantisce ricerche ad un costo fisso di 1.
Una soluzione ottimale consiste nello sfruttare al massimo la struttura ipotizzata per memorizzare il dizionario.
Possiamo notare che ogni elemento prefisso-carattere della nostra struttura verrà utilizzato per formare altri simboli del tipo prefisso/carattere+carattere secondo, il numero massimo di simboli derivati non sarà mai superiore a 256 per via dei principi di funzionamento dell'algoritmo.
Si può aggiungere quindi un array di 256 puntatori per ogni coppia prefisso-carattere, questi puntatori punteranno alle coppie derivate da quelle di origine. L'indice di questi puntatori verranno utilizzati con il carattere secondo.
Si può immaginare l'importanza di questa soluzione nella stesura di un implementazione.

3)Per massimizzare gli effetti della compressione bisogna memorizzare i valori dell'output utilizzando solo lo spazio necessario per memorizzarli. Questo significa che nel momento in cui nel dizionario viene aggiunto un simbolo con posizione 257, il valore dovrà occupare solamente 9 Bit di memoria e non 16bit anche se 16bit è la dimensione massima del dizionario, questo ovviamente finché il simbolo più grande del dizionario non avrà bisogno di più bit per la memorizzazione.
Il bit-size dovrà crescere in maniera dinamica a seconda della dimensione temporanea del dizionario, in un implementazione a 16 bit ad esempio il bit-size utilizzato dovrà partire da una grandezza di 9 bit fino a diventare di 16 bit in modo sequenziale in base alle dimensioni del dizionario raggiunte in ogni punto della compressione.
Bisogna realizzare in qualche modo delle procedure per ottenere questo risultato, il metodo più semplice è quello di creare un buffer di bit e scrivere i byte solo quando il buffer diventa multiplo di 8.

4)Le dimensioni del dizionario devono essere definite, il miglior metodo è quello di dare un limite al dizionario in base ad un bit-size, in questo modo non ci saranno informazioni sprecate nell'output compresso. Questo significa che se ad esempio utilizziamo 14 bit il numero massimo di simboli nel dizionario sarà
(2^14) - 1 = 16383 simboli.




5)Per evitare che la compressione degradi una volta che il dizionario è pieno si possono adottare 2 strade:
a) Si resetta il dizionario per tornare alla situazione iniziale nella quale si dispone di 256 simboli, è consigliabile riservare un simbolo nel dizionario per indicare al decompressore che il dizionario a partire dal simbolo speciale è stato resettato
b) Si analizza il rapporto di compressione e si resetta il dizionario ogni qualvolta questo degrada, questa tecnica è più raffinata della prima ma non porta benefici molto rilevanti. Nell'implementazione allegata a questo articolo viene utilizzata la soluzione a.

Autore dell'articolo:
Ugo Cirmignani

LZW Implementation by Ugo Cirmignani

FAC (Fast Archive Creator)



Tags: LZW in C - Comprimere i dati in c - Algoritmo base di compressione dati LZW - Implementazione LZW in C - Realizzare software come winzip

Lavorare con i bit in C# .Net

Esempio di programmazione con i bit nell'implemetazione in C# dell'algoritmo Base64

By kingk (art. no 8)

Spesso capita di dover lavorare con i bit, specialmente quando si lavora con i protocolli di comunicazione.

Sfortunatamente nei linguaggi di programmazione ad alto livello a differenza dell'asm, spesso mancano le funzioni giuste per accedere direttamente ai valori dei bit e il dato minimo che si può leggere è il byte.

In questo articolo propongo una semplice classe per il linguaggio di programmazione C# .Net utile per accedere direttamente ai bit di una variabile di tipo byte. Per un ulteriore dimostrazione dell'utilità di questa classe ho implementato anche l'algoritmo Base64 sfruttando i metodi per i bit.

I metodi della classe consentono di :

-Leggere il valore di un bit da un byte

-Settare il valore di un bit in un byte

-Codificare e Decodificare in base64

Spero che questa classe (scaricabile come di consueto) torni utile a qualcuno a presto!

Autore: Ugo Cirmignani


BIT CLASS C#

Tags: Manipolare i bit - Come modificare bit e non byte in c#

Criptazione dati lato client/server tramite Javascript e Php

Una valida soluzione economica per implementare una criptazione dati lato client/server senza utilizzare una connessione ssl (in genere fornita ad un prezzo extra dai servizi di hosting)

By kingk (art. no 7)

Una valida soluzione economica per implementare una criptazione dati lato client/server senza utilizzare una connessione ssl (in genere fornita ad un prezzo extra).

L'algoritmo in questione è robusto e non diffuso, grazie a queste due caratteristiche possiamo affermare che un metodo di criptazione del genere può essere considerato sicuro.

Con questo algoritmo è possibile criptare i dati sia dal lato client (tramite una libreria in Javascript) che lato server (tramite una libreria in Php) grazie ad alcune semplicissime funzioni fornite dalle relative librerie.

Con queste librerie ad esempio è possibile rendere impossibile l'interpretazione dei dati che transitano nelle pagine web da parte di eventuali persone che possono spiare la comunicazione trovandosi nel mezzo del transito dei dati (ad esempio un provider potrebbe benissimo disporre di questi dati).

Un esempio pratico di queste librerie è un classico form che spedisce su un server remoto dei dati cifrati.
Tramite la libreria in Javascript è possibile effettuare una criptazione dei dati prima dell'invio delle informazioni su internet (ad esempio sfruttando l'evento Javascript OnSubmit dei form, o la tecnica di programmazione ajax).

Le funzioni chiave da utilizzare in entrambe le librerie (Javascript/Php) sono:

Stringa = X_Crypt_String(Stringa, Password, true ) / $Stringa = X_Crypt_String($Stringa, $Password, true )

Stringa = X_DeCrypt_String(Stringa, Password, true ) / $Stringa = X_DeCrypt_String($Stringa, $Password, true )

Gli argomenti sono : Input, Password, TRUE o FALSE (Per codificare i dati cifrati anche in base64)

Un esempio di un applicazione che sfrutta questa libreria è il nostro password manager online presente nella sezione tools.

Le librerie sono scaricabili gratuitamente dai seguenti link.

Autore Ugo Cirmignani

Librerie Crypter Javascript / Php

Tags: Come cifrare dei dati - Creare algoritmo criptazione dati - Criptazione dati tramite Javascript