GLI ALGORITMI DI COMPRESSIONE 3 Gli algoritmi di compressione Le immagini , di solito, occupano molto spazio . Con la tecnologia analogica le fotografie venivano impresse sulla pellicola, stampate su carta e conservate in grossi album . Oggi le fotografie digitali spesso vengono scattate senza il fine di essere conservate, ma quando ciò avviene, soprattutto per salvare formati ad alta risoluzione , occorre dedicare parecchio spazio per la loro memorizzazione. La tecnologia digitale ha un grande vantaggio rispetto a quella analogica: ha la possibilità di comprimere i dati , cioè di ridurre il numero di bit che immagazzinano l’informazione all’interno di un file. La compressione dei dati avviene per mezzo di opportuni    (implementati da software applicativi o direttamente dal sistema operativo) che elaborano i file e consentono di passare da un insieme di bit a un . ▶ algoritmi di compressione insieme di bit ridotto Una volta compressi, i dati non sono più disponibili direttamente ma, per poterli utilizzare, occorre prima . La decompressione degli archivi di dati è solitamente più frequente della loro compressione, per questo motivo molti sono fortemente , cioè impiegano un tempo, una quantità di memoria e una capacità di calcolo per la compressione decisamente superiori a quelli richiesti per la decompressione. decomprimerli algoritmi asimmetrici Le tecniche di compressione e decompressione dei dati, in generale, necessitano di una discreta che può diventare anche molto elevata se le due operazioni devono essere eseguite in tempo reale. Il salvataggio in memoria viene spesso dall’applicazione degli algoritmi di compressione e decompressione, ma il vantaggio derivante dalla occupato dai file può diventare anche molto consistente. potenza di calcolo rallentato diminuzione dello spazio Ovviamente si può scegliere di . In questo caso il processore non deve effettuare alcun calcolo per la codifica e la decodifica dei dati e quindi, il salvataggio del file risulta , anche se viene occupata più memoria. non comprimere i file più veloce   /  algoritmo  algorithm attenzione   Durante la compressione dei file parte degli 0 e degli 1 viene persa, ma l’ informazione   associata ai bit può essere   totalmente mantenuta   oppure   in parte persa   in base all’algoritmo di compressione utilizzato. Il rapporto tra la dimensione dei dati iniziali e la dimensione dei dati compressi prende il nome di rapporto di compressione e fornisce una misura della compressione effettuata. esempio attenzione   Non tutti gli algoritmi di compressione comprimono in egual misura e, spesso, la qualità del risultato dipende anche dai dati che devono essere compressi. Il può essere espresso: rapporto di compressione con un numero ottenuto come rapporto tra la dimensione dei dati iniziali e la dimensione dei dati compressi (nell’esempio precedente il 4); riferendolo a 1 unità di dati compressi (espressa nell’unità di misura considerata, nell’esempio 4 : 1, in MB); indicando per quale numero occorre moltiplicare la dimensione dei dati compressi per ottenere la dimensione dei dati originali (nell’esempio 4×); indicando il risparmio di spazio ottenuto espresso in percentuale da 0% a 100% o come numero che varia tra 0 e 1 utilizzando la formula: percentuale di compressione = 1 -    dimensione dei dati compressi dimensione dei dati non compressi ⁄ Nell’esempio 1 – (5 : 20) = 1 – (1 : 4) = 1 – 0,25 = 0,75 = 75% di compressione. Se i dati compressi avessero dimensione identica ai dati iniziali, il rapporto fornirebbe 1 e quindi la compressione risulterebbe pari a 0. Al contrario se la compressione fosse ideale, i dati compressi avrebbero dimensione 0 (nella realtà è impossibile) e il rapporto sarebbe 0, pertanto la compressione risulterebbe pari al 100%. Gli algoritmi di compressione si dividono in due categorie:   e  . senza perdita con perdita attenzione   Quanto più alta la capacità di compressione ottenuta, tanto maggiore è la compressione ottenuta. Lo sapevi che In informatica un   algoritmo   è una sequenza di istruzioni che descrivono il procedimento che risolve un problema. Il termine   algoritmo   deriva dal nome del matematico persiano   al-Khwarizmi , vissuto nell’800, considerato uno dei primi ad aver fatto riferimento a questo concetto.  >> pagina 100  Gli algoritmi senza perdita Le tecniche di compressione senza  ▶ perdita ( lossless ) non perdono i dati iniziali a seguito della compressione. In altre parole, al momento della decompressione, questi algoritmi ottengono . Le tecniche lossless vengono impiegate in tutte le applicazioni che non ammettono perdita di informazione neanche parziale: compressione di file di testo, listati di programmi, tabelle numeriche, archivi di database ecc. esattamente l’informazione originale Tra i più noti esempi di algoritmi di compressione senza perdita ci sono: ( ): le (ripetizioni) presenti all’interno di una sequenza per l’informazione in maniera più . Codifica RLE Run-Length Encoding sfrutta ridondanze codificare compatta esempio X X X X X X X X X X X X X X X  codifica RLE  7 X 1 8 X Y ▶ ▶ Y Specificando quante volte si ripete ciascun carattere, questa tecnica riduce il numero di bit all’interno del file. Nell’esempio considerato, il numero di caratteri viene ridotto da 16 a 6. Tuttavia l’ , neanche parzialmente. Al momento della decompressione, la codifica compressa sarà interpretata e recuperata integralmente. informazione iniziale non viene persa L’algoritmo RLE è facile da implementare e quando il file da comprimere contiene , ma non è molto efficace quando le sequenze sono corte. funziona bene lunghe sequenze uguali   / perdita loss : assegna alle e un numero per le . Codifica di Huffman codici più corti sequenze più probabili maggiore di bit sequenze meno frequenti esempio Consideriamo la sequenza:   A BBBCCCDD EEEEEEEEE F L’algoritmo di Huffman conta il numero di caratteri diversi (6 cioè A, B, C, D, E, F), poi conta quante volte si ripete ciascun carattere: A B C D E F 1 3 3 2 9 1 Infine stabilisce quanti bit utilizzare per codificare ciascun carattere, assegnando un numero di bit inferiore ai caratteri che si ripetono più frequentemente (E) e un numero di bit maggiore ai caratteri che si ripetono meno frequentemente (A e F). L’algoritmo di Huffman   quando il file da comprimere contiene   e ha lo svantaggio che, in casi particolarmente sfortunati, il file compresso potrebbe risultare più grande dell’originale. funziona meglio sequenze senza ripetizioni ( ): è la : all’interno della sequenza originale, vengono individuate delle sotto-sequenze che si ripetono più volte. Codifica LZW Lempel, Ziv, Welch codifica con dizionario esempio Consideriamo la frase: I  esi abitano a  a Genov Genov sequenza ripetuta due volte L’algoritmo genera un dizionario all’interno del quale la sequenza   viene associata a un carattere speciale che la rappresenti, per esempio  . Genov à La sequenza originale viene quindi modificata, diventando più corta: I  esi abitano a  a à à Normalmente il numero di caratteri totali della sequenza più il numero di caratteri salvati nel dizionario è inferiore al numero di caratteri del testo iniziale. L’algoritmo LZW è piuttosto semplice da implementare e può essere applicato a qualsiasi tipo di dato (testo, immagini, audio ecc.). Ha un   non alto a causa della sua genericità, che non trae particolari vantaggi dalle caratteristiche dei dati che devono essere compressi.   quando le  , ma   e quindi non possono essere codificate nel dizionario. rapporto di compressione Funziona male sotto-sequenze sono simili non identiche attenzione   Il carattere speciale deve essere scelto fra quelli che si trovano al di fuori dell’alfabeto utilizzato nel documento. Gli algoritmi di compressione senza perdita non garantiscono che qualunque sequenza, una volta compressa, possa diminuire effettivamente la sua dimensione. Inoltre lo stesso algoritmo lossless potrebbe funzionare molto bene su alcuni file e non su altri. Quanto si riesce a comprimere senza perdita di informazione? Esiste un   che non può essere superato, che si chiama  : è possibile comprimere senza perdita di informazione, avvicinandosi quanto più possibile a questo limite, ma non è possibile superarlo perché per comprimere ulteriormente dovrebbe necessariamente essere persa dell’informazione. limite teorico entropia dell’informazione attenzione   Applicando differenti algoritmi di compressione lossless diversi a un file già compresso senza perdita potrebbe essere possibile ridurre ulteriormente la dimensione del file, ma di poco, senza miglioramenti effettivamente apprezzabili.  >> pagina 102 Gli algoritmi con perdita Le tecniche di compressione con perdita ( lossy ) eliminano parte dell’informazione iniziale, a fronte di una piccola riduzione della qualità del file, che però risulta impercettibile. Al momento della decompressione, questi algoritmi mantengono solo l’informazione significativa e perdono per sempre i particolari . Gli algoritmi di compressione con perdita vengono solitamente utilizzati per ridurre la dimensione dei (immagini, video, audio ecc.) che generalmente occupano molto spazio in e non possono essere agevolmente. Quando il grado di dei dati aumenta, la quantità di informazione è maggiore; lo occupato in memoria diminuisce, ma la del file peggiora, talvolta anche . file multimediali memoria trasmessi compressione persa spazio qualità percettibilmente Per intuire il funzionamento dei sistemi di compressione con perdita, possiamo fare riferimento a un esempio già usato per la compressione lossless. esempio X X X X X X X X X X X X X X X Y Supponendo che l’unica Y presente possa essere irrilevante rispetto all’informazione originale, è possibile trascurarla, descrivendo la sequenza come . 16 X Lo sapevi che La compressione serve a occupare meno memoria, ma anche per ridurre la banda di trasmissione dei dati. Molti social network e App di messaggistica (per esempio Whatsapp, Facebook, Instagram ecc.) comprimono le immagini (con perdita) prima di inviarle. Per condividere immagini a piena risoluzione ricordati di usare le e-mail, le memorie di massa o il cloud. prova tu   Vero o falso Gli algoritmi lossless non perdono l’informazione iniziale.     V F Gli algoritmi lossy eliminano tutta l’informazione iniziale.     V F Gli algoritmi lossy eliminano parte dell’informazione iniziale.     V F I formati standard delle immagini Il formato di un file stabilisce le specifiche regole con cui le informazioni devono essere memorizzate all’interno del file, andando quindi a dare uno specifico senso e un’univoca interpretazione alle sequenze di 0 e 1 in esso contenute. Le vengono codificate usando standard. Fra quelli i più usati sono: immagini raster formati di file lossless : non è compresso ed è velocemente accessibile, occupa molto spazio; BITMAP : usa l’algoritmo RLE, supporta il multipagina e il canale alfa; TIFF : usa l’algoritmo LZW, consente di generare le gif animate; GIF : evoluzione migliorata del formato GIF, usato per la grafica e il web; PNG : memorizza i dati catturati dal sensore della fotocamera ad alta risoluzione. RAW Fra quelli , il più noto è il (che usa l’omonimo algoritmo JPEG), utilizzato per fotocamere, smartphone e web. lossy JPEG Anche le vengono codificate usando dei formati di file standard. Quelli più noti sono i formati SVG, CDR, AI ed EPS. immagini vettoriali   Approfondimento – I formati standard delle immagini