backup del Post

Compressione dati fantastica

Un raccontino di fantascienza degli anni ’50, quando il concetto di computer faceva venire in mente enormi stanzoni pieni di valvole, racconta di un alieno che sbarcò sulla Terra nell’ambito di un programma di conoscenze exoculturali. Dopo qualche giorno annunciò che sarebbe tornato a casa, e che gli sarebbe piaciuto portare sul proprio pianeta, come simbolo del livello di conoscenza raggiunto dai terrestri, l’Enciclopedia Britannica. Nemmeno gli scrittori di fantascienza a quei tempi riuscivano a immaginare che un gigabyte di dati si può salvare in una schedina più piccola di un unghia, e così gli interlocutori dell’alieno si stupirono chiedendosi dove avrebbe caricato tutti i volumi. In tutta risposta, l’extraterrestre tirò fuori una barretta di metallo. «Mi basta codificare tutto il testo della Britannica in un enorme numero, metterci davanti uno zero virgola, e fare una tacca corrispondente su questa barretta lunga uno stmerp». Semplice, no?

La procedura è assolutamente corretta dal punto di vista logico, e in teoria dà il risultato richiesto; ma immagino vi sarà subito saltato agli occhi che non è per nulla fattibile in pratica. Immaginiamo che la Britannica dell’epoca contenesse un milione di parole, e che il suo testo si potesse salvare in quello che adesso definiremmo 12,5 megabyte, cioè 100 milioni di bit (nel racconto non è specificato il numero delle dita nelle mani dell’alieno, e quindi non possiamo inferire in che base numerica lavora; ma i conti non cambiano troppo in ogni caso, ed è più semplice lavorare con i bit). Il primo bit di questo numero ci dice se la tacca deve essere fatta nel primo mezzo stmerp o nel secondo; il secondo bit in quale metà della parte selezionata prima, e così via. All’ultimo bit dovremmo pertanto selezionare una delle due metà di un intervallo largo – si fa per dire – 1/2^100000000 stmerp. Se uno stmerp è circa lungo un metro, parliamo di circa 10^–30000000 metri. Tenendo conto che la lunghezza di Planck, la più piccola distanza che ha senso nella fisica quantistica, è pari a 1,6×10⁻³⁵ metri capirete anche voi che l’alieno ci ha voluto fare un bello scherzetto, e con ogni probabilità aveva davvero una microSD nascosta da qualche parte.

Mentre sto parlando di compressione dati, può anche valere la pena dedicare qualche parola ai famigerati “sistemi di compressione perfetti”, che possono rimpicciolire le dimensioni di un qualunque file: anche quelli che magari sono già stati compressi. Mi spiace darvi una brutta notizia, ma queste cose esistono solo nelle favole e nelle conferenze stampa taroccate. Tanto per specificare, sto parlando dei sistemi di compressione senza perdita, in inglese “lossless”, tali cioè che è possibile ottenere di nuovo il file originario a partire solo da quello compresso. Esistono infatti anche sistemi “lossy”, come JPEG e MP3, che sfruttano il fatto che il nostro occhio e il nostro orecchio possono essere ingannati e salvano così immagini e suoni solo simili a quelli originali; una specie di riassunto, insomma, da cui non si può ricavare il testo originale.

Perché non può esistere un sistema di compressione perfetto? La risposta è semplice, e richiede solo che ci mettiamo a contare il numero di file possibili di una certa lunghezza. Il conto è presto fatto: di file lunghi k bit ce ne sono 2^k, visto che ciascuno dei bit può valere zero oppure 1; quindi per ogni nuovo bit aggiunto si raddoppia il numero di file possibile. Visto che il numero totale di file lunghi al massimo k-1 bit è 2^k-1, notiamo subito che è impossibile ridurre la lunghezza di tutti i file lunghi k bit. E com’è allora che i zip file che facciamo sono molto più corti dei file originali? La risposta è semplice: non solo la stragrande maggioranza dei file teoricamente possibili non ha senso pratico, ma il modo in cui produciamo i nostri file (siano di testo oppure generati da un compilatore) usa costrutti ridondanti, e quindi lo zippatore ha buon gioco a compattare le informazioni.

Se volete vedere la cosa in altro modo, pensate alla distribuzione di carte in una partita a bridge. In questo caso è effettivamente possibile avere almeno in linea di principio tutte le distribuzioni di carte; e infatti uno si stupisce così tanto di avere ricevuto un gruppo di carte “che si possono descrivere in maniera più semplice dell’elencarle una ad una” che subito va a dirlo in giro: «Ragazzi! Mi hanno dato tutte e sole carte di picche!» Insomma le mani a bridge non si zippano; in questo caso la compressione non è effettivamente possibile!