L'algoritmo di compressione (ZIP, JPEG, MP3)

Pensieri in codice. Idee dal mondo del software a cura di Valerio Galano. Buongiorno a tutti ragazzi e ben ritrovati per un nuovo episodio di Pensieri in codice, il podcast in cui parliamo di argomenti presi dal mondo del software, di internet e della programmazione. Prima di partire subito con l’argomento di oggi una piccola comunicazione di servizio. Il 12 ottobre 2019 si terrà a Milano il festival del podcasting e Pensieri in codice è candidato come miglior podcast emergente. I primi dieci classificati verranno annunciati sul palco del festival, quindi se vi va di aiutarmi nel contest fermate un secondo il podcast e collegatevi al link vota.pensierincodice.it, lo trovate anche in descrizione. Si aprirà un post Instagram e non dovrete fare altro che mettere un like. Vi ringrazio tutti per il supporto e ora procediamo con l’argomento del giorno. Come per l’episodio della settimana scorsa, anche oggi diamo il via ad una nuova rubrica che chiameremo Algoritmi e nella quale parleremo, indovinate un po’, di algoritmi. Negli episodi di questa rubrica andremo ad esaminare quali sono le logiche alla base dei più importanti algoritmi e proveremo a capire, almeno a grandi linee, come funzionano. Questo perché in generale siamo ben abituati a parlare dei progressi nel campo dell’hardware. Compriamo l’ultimo modello di smartphone che ha la fotocamera con più megapixel, il pc con il doppio della memoria del suo predecessore e così via. Però non pensiamo mai al fatto che nelle azioni che compiamo tutti i giorni un buon algoritmo è altrettanto, se non addirittura più importante, dell’hardware che utilizziamo. Pensate a cosa avete fatto ieri con il vostro smartphone o con il vostro pc. Magari avete trovato il percorso più breve per raggiungere la vostra destinazione o forse avete inviato il video del vostro cagnolino ad un parente distante molti chilometri o forse ancora avete individuato il documento che volevate leggere in un archivio di svariati miliardi di documenti. Tutto questo l’avete potuto fare grazie all’hardware di cui disponete, certo, ma anche grazie ad una serie di ingegnosi algoritmi che vi hanno permesso di trovare la distanza minore tra un insieme di punti o di comprimere e trasmettere file audio e video o ancora grazie ad algoritmi di indicizzazione dei motori di ricerca. Allo stesso modo sono tantissimi gli algoritmi che tutti i giorni, senza che nemmeno ce ne accorgiamo, ci semplificano continuamente la vita o in qualche caso ce la complicano, ma di questo parleremo in futuro. Per questo motivo io credo che sia importante conoscere, o almeno comprendere, come funzionano tutti i grandi algoritmi che nel corso della storia hanno contribuito a costruire il mondo così come noi oggi lo viviamo. Chiunque abbia già un’infarinatura di programmazione o di informatica in generale conoscerà già la definizione formale di algoritmo e cioè qualcosa del tipo un algoritmo è un insieme finito di passi sufficientemente semplici che se eseguiti nell’ordine permettono di trasformare un dato input in un dato output. Tuttavia in questa rubrica vorrei mettere in luce il fatto che un algoritmo, per come la vedo io, non è soltanto questo. Un algoritmo, secondo me, è la rappresentazione di un’idea. Una descrizione precisa ed elegante di una soluzione ad un dato problema. Di conseguenza potremmo definire un grande algoritmo come la più efficiente, la più elegante e, in generale, la migliore delle soluzioni che al momento conosciamo per problemi reali che affrontiamo ogni giorno. Tra gli argomenti che potenzialmente potranno entrare a far parte di questa rubrica ci saranno dunque algoritmi di utilizzo quotidiano come quelli di criptografia, di trasmissione, di ricerca, di ordinamento, di verifica della consistenza, varie tipologie di machine learning e molto molto altro. Nell’episodio di oggi parleremo dell’algoritmo di compressione, una funzionalità che magari crediamo di utilizzare di tanto in tanto ma che, come vedremo fra poco, ci accompagna praticamente ogni giorno senza che nemmeno ce ne rendiamo conto. Tutti i file che memorizziamo nei nostri dispositivi, che scambiamo ogni giorno e che archiviamo nel cloud, hanno una caratteristica che prende il nome di dimensione o peso a seconda dei contesti e che si esprime in byte e in relativi multipli come ad esempio il kilobyte o il kibibyte e, se non avete mai sentito parlare di kibibyte, vi consiglio di ascoltare l’episodio numero 12 dal titolo La storia del kibibyte. Questa dimensione rappresenta lo spazio che il file occupa nella memoria di archiviazione. Maggiore sarà la dimensione del file, minore sarà il numero di file che riusciremo ad archiviare nella memoria dei nostri dispositivi. Dal momento però che con il passare del tempo le memorie sono progressivamente divenute sempre più grandi e al tempo stesso sempre più economiche, noi non sentiamo effettivamente il bisogno di comprimere i file per ridurne la dimensione così come accadeva di norma fino a qualche anno fa. Nonostante ciò la compressione resta una parte fondamentale sia per la trasmissione che per l’archiviazione dei dati. Tutte le grandi piattaforme di streaming ad esempio utilizzano la compressione sui propri contenuti e questo diminuisce di gran lunga l’ampiezza di banda necessaria per noi per guardare un film o per ascoltare la musica. Lo stesso discorso vale per i servizi di sincronizzazione dei file come ad esempio Dropbox e simili, ma in più essi utilizzano la compressione anche per conservare i nostri dati e quindi per risparmiare sulle quantità di memoria di archiviazione necessarie. Le compagnie telefoniche anche comprimono la voce durante le chiamate per poter sfruttare maggiormente le linee e si potrebbe andare avanti per molto perché gli esempi sono tantissimi. Ma come funziona in effetti questa operazione che prende il nome di compressione? Innanzitutto partiamo col chiarire che la compressione può essere di due tipi quella senza perdita di informazione e quella con perdita di informazione. Per compressione senza perdita si intende quel tipo di compressione in cui il file compresso, se decompresso, ritorna a essere esattamente identico al file di partenza. Il formato più famoso di questo tipo di compressione prende il nome di formato zip. Un file può essere infatti zippato e dezippato più volte senza che le informazioni al suo interno vengano in alcun modo alterate. L’algoritmo del formato zip basa il suo funzionamento sul fatto che i file vengono memorizzati sotto forma di stringhe di testo ed applica a queste stringhe la combinazione di due operazioni. Badate bene, nella realtà l’algoritmo non lavora direttamente sul testo ma a basso livello sulla codifica del file. Noi però cerchiamo di semplificare perché ciò che ci interessa è il concetto alla base. Quindi prima di tutto dicevamo l’algoritmo individua le ripetizioni all’interno del testo. Se ad esempio trova la sequenza abc abc abc la sostituisce con la sequenza abc per 3 che sta a significare che la sequenza abc in origine era ripetuta tre volte. Come possiamo vedere con questo semplice espediente un testo di lunghezza 9 caratteri si è già ridotto a 5. Siamo quindi già quasi ad una dimensione pari a metà di quella del file originale anche se badate bene che è un esempio e sto semplificando estremamente. Il secondo passo che l’algoritmo applica è quello di cercare le ripetizioni sparse per il testo quindi non più quelle consecutive come nell’esempio precedente e le sostituisce con una rappresentazione abbreviata. Quindi se ad esempio nel testo dovesse essere presente sette volte la parola carota l’algoritmo potrebbe sostituire tutte e sette le occorrenze con il numero 1. Se trovasse 5 volte la parola sedano la sostituirebbe magari con il numero 2 e zucca che compare due volte verrebbe sostituita con il numero 3 e così via. Nel fare queste sostituzioni l’algoritmo produrrebbe anche una piccola tabella per tenere conto dei collegamenti tra la parola originale e l’abbreviazione e la inserirebbe all’interno del file zip risultante. Il risultato dell’applicazione di questi due passaggi sul file ne rappresenta una compressione senza perdita. Ne produce infatti una versione molto più piccola nella quale però sono contenute tutte le informazioni del file originale. Basterà quindi applicare i passaggi precedentemente descritti in ordine inverso per ripristinare il file di partenza. Diversa invece è la questione se si parla di algoritmi di compressione con perdita di informazione. In questo caso infatti la procedura prevede di produrre una versione compressa del file della quale non necessariamente è possibile ripristinare l’originale. Questo tipo di compressione non viene applicato a file di testo o in generale a tutti quei file in cui anche una sola virgola di differenza provocherebbe problemi in fase di utilizzo. La compressione con perdita si applica invece principalmente ai file multimediali come ad esempio le immagini, le tracce vocali o musicali, i film ecc. In questa tipologia di file infatti non è indispensabile che la versione compressa sia identica all’originale. È sufficiente invece che un’immagine o un suono compressi siano abbastanza simili all’originale da far sì che non se ne noti la differenza. Non è importante che il dato sia perfetto ma che sia sufficientemente fedele da impedire all’occhio o all’orecchio umano di avvertire la diminuzione di qualità. E dunque nella compressione con perdita esiste questo concetto della qualità e cioè una misura che esprime la quantità di informazioni conservate in fase di compressione. In pratica se la qualità del file è alta allora l’algoritmo di compressione avrà scartato pochi dati. Man mano che si spinge l’algoritmo a scartare più informazioni si riduce la dimensione del file compresso ma a discapito della qualità dell’immagine o del suono. Ma come funziona dunque questo algoritmo di compressione? Per capirlo concentriamoci innanzitutto sulla lavorazione delle immagini. Le immagini vengono rappresentate in informatica come insiemi di pixel cioè di piccolissimi quadrati colorati che messi uno di fianco all’altro vanno a comporre una foto o un disegno. In un normale televisore full hd ad esempio le immagini di film che stiamo guardando sono composte da 1920 colonne e 1080 righe di questi pixel. Abbiamo quindi in totale circa 2 milioni di pixel e cioè 2 megapixel. Sempre semplificando al massimo diciamo che la compressione di un’immagine del genere funziona più o meno in questo modo. Nel file compresso riportiamo i pixel del file di partenza prendendo una riga sì e una no e contemporaneamente una colonna sì e una no. In pratica una volta finito avremmo escluso la metà delle righe la metà delle colonne e quindi i tre quarti dei pixel. Pixel che sono di fatto andati persi nella compressione e da qui il nome di compressione con perdita. Il file risultante avrà quindi una dimensione di un quarto dell’originale. Va da sé che avendo perso il 75% delle informazioni se tentassimo di ripristinare il file originale otterremo un risultato abbastanza diverso. L’immagine probabilmente sarebbe comunque distinguibile ma non sarebbe affatto quella di partenza. Ora la procedura che abbiamo descritto non è quella reale ma un qualcosa di simile che ci è servito per comprendere il concetto di base. In un formato reale come ad esempio il jpeg che anche se viene utilizzato direttamente dai software è di fatto un formato compresso la tecnica prevede comunque la perdita di pixel ma la scelta di quali informazioni scartare viene effettuata in modo molto più complesso. Non è possibile illustrare in un podcast l’intero processo tuttavia possiamo dire che le porzioni di pixel su cui lavora l’algoritmo non sono righe e colonne quanto piuttosto dei quadrati la cui dimensione aumenta o diminuisce in base al grado di qualità che si vuole ottenere. Più grandi saranno i quadrati esaminati minore sarà la qualità dell’immagine compressa. L’algoritmo infatti selezionerà tra tutti i pixel del quadrato quelli il cui valore ritiene meno importante e semplicemente li eliminerà durante la compressione. Da quanto abbiamo appena detto si può quindi dedurre una cosa e cioè che tutte le scene dei film e delle serie tv in cui l’esperto della scientifica utilizza un non meglio definito software per incrementare la risoluzione dell’immagine della telecamera o di una macchina fotografica… beh sono cavolate non è possibile recuperare informazioni da file in cui le informazioni semplicemente non ci sono. Per concludere il discorso anche i file audio come gli mp3 sono in effetti formati compressi e utilizzano la stessa logica del formato jpeg in pratica suddividono l’audio in varie porzioni e ne eliminano le parti che ritengono non fondamentali. Anche in questo caso il risultato finale non sarà identico all’originale ma sarà sufficientemente simile da essere apprezzabile e occuperà molto meno spazio in memoria. E anche per oggi siamo giunti al termine dell’episodio. Io spero che questa nuova rubrica vi piaccia perché ho in serbo molti altri episodi. Come al solito vi ringrazio per aver ascoltato fin qui e vi chiedo di condividere il podcast e se vi va di unirvi al gruppo telegram che trovate in descrizione. Vi ricordo che potete seguirmi su instagram e ascoltare il podcast sulle principali piattaforme tra cui ad esempio spotify google podcast itunes e anche alexa. Vi basterà dire alexa apri pensieri in codice. E dunque per oggi è tutto io vi saluto e vi do appuntamento al prossimo