{"id":2334,"date":"2010-09-24T02:30:16","date_gmt":"2010-09-24T00:30:16","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2334"},"modified":"2022-10-10T19:01:39","modified_gmt":"2022-10-10T17:01:39","slug":"compressione-dati-fantastica","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2010\/09\/24\/compressione-dati-fantastica\/","title":{"rendered":"Compressione dati fantastica"},"content":{"rendered":"<p>Un raccontino di fantascienza degli anni &#8217;50, quando il concetto di computer faceva venire in mente enormi stanzoni pieni di valvole, racconta di un alieno che sbarc\u00f2 sulla Terra nell&#8217;ambito di un programma di conoscenze exoculturali. Dopo qualche giorno annunci\u00f2 che sarebbe tornato a casa, e che gli sarebbe piaciuto portare sul proprio pianeta, come simbolo del livello di conoscenza raggiunto dai terrestri, l&#8217;Enciclopedia Britannica. Nemmeno gli scrittori di fantascienza a quei tempi riuscivano a immaginare che un gigabyte di dati si pu\u00f2 salvare in una schedina pi\u00f9 piccola di un unghia, e cos\u00ec gli interlocutori dell&#8217;alieno si stupirono chiedendosi dove avrebbe caricato tutti i volumi. In tutta risposta, l&#8217;extraterrestre tir\u00f2 fuori una barretta di metallo. &laquo;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&raquo;. Semplice, no?<\/p>\n<p><!--more-->La procedura \u00e8 assolutamente corretta dal punto di vista logico, e in teoria d\u00e0 il risultato richiesto; ma immagino vi sar\u00e0 subito saltato agli occhi che non \u00e8 per nulla fattibile in pratica. Immaginiamo che la Britannica dell&#8217;epoca contenesse un milione di parole, e che il suo testo si potesse salvare in quello che adesso definiremmo 12,5 megabyte, cio\u00e8 100 milioni di bit (nel racconto non \u00e8 specificato il numero delle dita nelle mani dell&#8217;alieno, e quindi non possiamo inferire in che base numerica lavora; ma i conti non cambiano troppo in ogni caso, ed \u00e8 pi\u00f9 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\u00e0 della parte selezionata prima, e cos\u00ec via. All&#8217;ultimo bit dovremmo pertanto selezionare una delle due met\u00e0 di un intervallo largo &ndash; si fa per dire &ndash; 1\/2<sup>100000000<\/sup> stmerp. Se uno stmerp \u00e8 circa lungo un metro, parliamo di circa 10<sup>&ndash;30000000<\/sup> metri. Tenendo conto che la <a href=\"http:\/\/it.wikipedia.org\/wiki\/Lunghezza_di_Planck\">lunghezza di Planck<\/a>, la pi\u00f9 piccola distanza che ha senso nella fisica quantistica, \u00e8 pari a 1,6&times;10<sup>&minus;35<\/sup> metri capirete anche voi che l&#8217;alieno ci ha voluto fare un bello scherzetto, e con ogni probabilit\u00e0 aveva davvero una microSD nascosta da qualche parte.<\/p>\n<p>Mentre sto parlando di compressione dati, pu\u00f2 anche valere la pena dedicare qualche parola ai famigerati &ldquo;sistemi di compressione perfetti&rdquo;, che possono rimpicciolire le dimensioni di un qualunque file: anche quelli che magari sono gi\u00e0 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 &ldquo;lossless&rdquo;, tali cio\u00e8 che \u00e8 possibile ottenere di nuovo il file originario a partire solo da quello compresso. Esistono infatti anche sistemi &ldquo;lossy&rdquo;, come JPEG e MP3, che sfruttano il fatto che il nostro occhio e il nostro orecchio possono essere ingannati e salvano cos\u00ec immagini e suoni solo simili a quelli originali; una specie di riassunto, insomma, da cui non si pu\u00f2 ricavare il testo originale.<\/p>\n<p>Perch\u00e9 non pu\u00f2 esistere un sistema di compressione perfetto? La risposta \u00e8 semplice, e richiede solo che ci mettiamo a contare il numero di file possibili di una certa lunghezza. Il conto \u00e8 presto fatto: di file lunghi <i>k<\/i> bit ce ne sono 2<sup><i>k<\/i><\/sup>, visto che ciascuno dei bit pu\u00f2 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 <i>k<\/i>-1 bit \u00e8 2<sup><i>k<\/i><\/sup>-1, notiamo subito che \u00e8 impossibile ridurre la lunghezza di <b>tutti<\/b> i file lunghi <i>k<\/i> bit. E com&#8217;\u00e8 allora che i zip file che facciamo sono molto pi\u00f9 corti dei file originali? La risposta \u00e8 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. <\/p>\n<p>Se volete vedere la cosa in altro modo, pensate alla distribuzione di carte in una partita a bridge. In questo caso \u00e8 effettivamente possibile avere almeno in linea di principio tutte le distribuzioni di carte; e infatti uno si stupisce cos\u00ec tanto di avere ricevuto un gruppo di carte &ldquo;che si possono descrivere in maniera pi\u00f9 semplice dell&#8217;elencarle una ad una&rdquo; che subito va a dirlo in giro: &laquo;Ragazzi! Mi hanno dato tutte e sole carte di picche!&raquo; Insomma le mani a bridge non si zippano; in questo caso la compressione non \u00e8 effettivamente possibile!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Un raccontino di fantascienza degli anni &#8217;50, quando il concetto di computer faceva venire in mente enormi stanzoni pieni di [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2334","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-BE","jetpack-related-posts":[{"id":1389,"url":"https:\/\/xmau.com\/ilpost\/2018\/12\/25\/quizzini-per-natale-2018\/","url_meta":{"origin":2334,"position":0},"title":"Quizzini per Natale 2018","author":".mau.","date":"25\/12\/2018","format":false,"excerpt":"Che Natale sarebbe senza i quizzini del Post? Le risposte tra una settimana. Gli ultimi due sono pi\u00f9 difficili, magari poi poster\u00f2 un aiutino ;-) 1. Non essere ottusi Considerate tutti gli insiemi I di cento numeri interi positivi distinti con la seguente propriet\u00e0: dati tre qualunque elementi a, b\u2026","rel":"","context":"In \"quizzini\"","block_context":{"text":"quizzini","link":"https:\/\/xmau.com\/ilpost\/tag\/quizzini\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2018\/12\/q361a.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2610,"url":"https:\/\/xmau.com\/ilpost\/2013\/05\/17\/325-anni-non-uno-di-meno\/","url_meta":{"origin":2334,"position":1},"title":"325 anni, non uno di meno","author":".mau.","date":"17\/05\/2013","format":false,"excerpt":"Somiglianze e differenze tra due sentenze per il terremoto dell'Aquila","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"Scosse sismiche a Onna (dal sito INGV, http:\/\/www.mi.ingv.it\/eq\/090406\/storia.html)","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/05\/DBMI08_onna_small.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/05\/DBMI08_onna_small.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/05\/DBMI08_onna_small.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":199,"url":"https:\/\/xmau.com\/ilpost\/2012\/11\/26\/il-paradosso-di-braess\/","url_meta":{"origin":2334,"position":2},"title":"Il paradosso di Braess","author":".mau.","date":"26\/11\/2012","format":false,"excerpt":"Aggiungere nuove connessioni a una rete in certi casi pu\u00f2 portare a peggiorare le sue prestazioni. Sembra incredibile, ma \u00e8 una conseguenza matematica dell'ipotesi che ognuno sia egoista.","rel":"","context":"In \"paradossi\"","block_context":{"text":"paradossi","link":"https:\/\/xmau.com\/ilpost\/tag\/paradossi\/"},"img":{"alt_text":"[il paradosso di Braess]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=525%2C300 1.5x"},"classes":[]},{"id":634,"url":"https:\/\/xmau.com\/ilpost\/2013\/04\/22\/geometria-a-macchinetta\/","url_meta":{"origin":2334,"position":3},"title":"Geometria a macchinetta","author":".mau.","date":"22\/04\/2013","format":false,"excerpt":"Preparare esercizi per i libri di matematica non \u00e8 un lavoro divertente: ma questo non significa che non li si possa fare con un minimo di accortezza.","rel":"","context":"In \"didattica\"","block_context":{"text":"didattica","link":"https:\/\/xmau.com\/ilpost\/tag\/didattica\/"},"img":{"alt_text":"figureimpossibili","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2015\/10\/figureimpossibili.jpg?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2015\/10\/figureimpossibili.jpg?resize=350%2C200 1x, https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2015\/10\/figureimpossibili.jpg?resize=525%2C300 1.5x"},"classes":[]},{"id":404,"url":"https:\/\/xmau.com\/ilpost\/2010\/10\/08\/il-quinto-postulato-di-euclide\/","url_meta":{"origin":2334,"position":4},"title":"Il quinto postulato di Euclide","author":".mau.","date":"08\/10\/2010","format":false,"excerpt":"Quello delle geometrie non euclidee \u00e8 un tema che non pu\u00f2 mancare in un blog di divulgazione matematica; il difficile \u00e8 riuscire a dire qualcosa di diverso dal solito. Cominciamo a vedere la storia dei tentativi di dimostrazione.","rel":"","context":"In \"geometria\"","block_context":{"text":"geometria","link":"https:\/\/xmau.com\/ilpost\/tag\/geometria\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":501,"url":"https:\/\/xmau.com\/ilpost\/2015\/01\/09\/il-computer-che-gioca-a-poker-pillole\/","url_meta":{"origin":2334,"position":5},"title":"il computer che vince a poker [Pillole]","author":".mau.","date":"09\/01\/2015","format":false,"excerpt":"Per la prima volta un computer gioca in modo ottimale a un gioco a informazione non completa","rel":"","context":"In \"algoritmi\"","block_context":{"text":"algoritmi","link":"https:\/\/xmau.com\/ilpost\/tag\/algoritmi\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2334","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2334"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2334\/revisions"}],"predecessor-version":[{"id":2335,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2334\/revisions\/2335"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2334"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2334"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2334"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}