Programmazione.it v6.4
Ciao, per farti riconoscere devi fare il login. Non ti sei ancora iscritto? Che aspetti, registrati adesso!
Info Pubblicità Collabora Autori Sottoscrizioni Preferiti Bozze Scheda personale Privacy Archivio Libri Corsi per principianti Forum
Greenpeace
Breve corso sulla compressione dei file: l'algoritmo LZW(2/5)
Scritto da Leonida Castaldo il 16-07-2007 ore 09:06
Intel Cluster Studio XE
L’algoritmo di compressione LZW è l’algoritmo più importante della famiglia LZ. Combinando le sue potenzialità a quelle dell’algoritmo di Huffman, i risultati ottenibili sono sorprendenti. Analizzarlo unicamente dal punto di vista della praticità e dell’utilità non basta, il connubio perfetto tra eleganza e praticità lo rendono paragonabile a un’opera d’arte. E’ sorprendente come poche righe di codice siano sufficienti a rappresentare un concetto tanto sottile in modo quasi perfetto.

Nel precedente articolo ho introdotto l’algoritmo spiegando l’idea alla base e ho impostato un esempio di compressione che userò per descrivere passo passo il processo di codifica. Ho scelto di proposito una sequenza di caratteri che si ripetono con una certa frequenza, per poter mostrare le potenzialità dell’algoritmo in pochi passi; generalmente si notano effetti di una certa rilevanza per compressione di testi molto più lunghi di 100 caratteri.

Ricapitolando, il testo da comprimere è: PDPD@PD@PD@P e la codifica è di 12 bit per parola; il processo di codifica inizierà sfruttando i 256 caratteri (da 0 a 255) del codice ASCII, sicuramente la scelta migliore considerando la natura del file, quindi in fase di inizializzazione saranno definiti nel vocabolario i primi 256 simboli a ognuno dei quali sarà associato un codice, rigorosamente binario, da 0 a 255. Il processo di codifica dei primi tre passi è descritto nella seguente figura:

<center>[img]http://farm2.static.flickr.com/1230/788869141_c58a7ad984.jpg?v=0[/img]</center>

E’ necessario definire due buffer di supporto: strCorr, strPrs e una variabile lstChr; il loro significato sarà chiarito nel corso della descrizione. Il processo di codifica comincia prelevando la prima lettera della stringa di testo, quindi la lettera P, e posizionandola nel buffer strCorr (stringa corrente). Nel vocabolario viene cercato il carattere P che si trova nella locazione 80 e non viene quindi restituito alcun output.

Al passo successivo, viene prelevata la lettera D e posizionata in strCorr nella locazione adiacente a quella in cui è stata posizionata la lettera P. La stringa PD viene cercata nel vocabolario, ma ovviamente con scarsi risultati. L’ultimo carattere inserito, D nel nostro esempio, viene copiato in lstChr (ultimo carattere); la restante stringa, in questo caso rappresentata dall’unica lettera P, viene copiata in strPrs (stringa presente).

La stringa in strPrs viene cercata nel vocabolario e viene trovata nella locazione 80, l’indice viene restituito in output. Viene aggiunta al vocabolario la stringa memorizzata in strCorr(=PD) nella locazione successiva all’ultimo carattere, quindi nella locazione 256 (256->PD), infine viene soprascritto il buffer strCorr con il valore memorizzato nella variabile lstChr. strCorr conterrà, alla fine del processo, la lettera D.

Al terzo passo viene prelevato il carattere P dalla stringa di input e memorizzato in strCorr nella locazione adiacente alla stringa memorizzata. Nel buffer sarà ora presente la stringa DP. Non trovando alcuna corrispondenza nel vocabolario, viene ripetuto il procedimento descritto al passo precedente: viene copiato il carattere P in lstChr e D nel buffer strPrs; viene cercato strPrs nel vocabolario, l’indice della locazione occupata — in questo caso 68 — viene restituito in output; il contenuto del buffer strCorr(=DP) viene aggiunto al vocabolario memorizzandolo nella locazione 257 (257->DP); il buffer strCorr è soprascritto con il valore memorizzato in lstChr(=P).

I passi successivi sono significativi in quanto mostrano i primi risultati effettivi della compressione, nella terza parte dell’articolo completerò la descrizione del processo di codifica.
Manda ad un amico Aggiungi ai preferiti Sottoscrivi la discussione Stampa
Commenta
Precedente: iPhoney, come creare browser per iPhone!
Successiva: Corso su Ruby: costanti
Copyright Programmazione.it™ 1999-2013. Alcuni diritti riservati. Testata giornalistica iscritta col n. 569 presso il Tribunale di Milano in data 14/10/2002. Pagina generata in 1.354 secondi.