Compressió de dades

Written by Edgar Gonzálezdijous, 29 juny 2006 09:55

Molts dels continguts que es transmeten a través d'Internet estan comprimits. Arxius de text, de música, de vídeo o de qualsevol altre tipus es comprimeixen per tal de reduir el seu tamany, facilitar el seu intercanvi a través de la xarxa o estalviar espai de disc. No obstant això, com és possible reduir la grandària d'un arxiu sense perdre el seu contingut? Uns quants trucs sobre teoria de la informació són els que ho fan possible.

Codi binari

En els nostres ordinadors només es processen senyals actives o apagades (de si o no). Tota la informació es representa mitjançant dos símbols, habitualment escrits 0 i 1, segons hi hagi corrent o no. Cadascun d'aquests símbols rep el nom de bit. La principal informació que maneguen els ordinadors són quantitats, i el codi binari permet una representació dels nombres similar a la que utilitzem les persones. Així, la sèrie 1, 2, 3, 4, 5... en binari és 1, 10, 11, 100, 101...

Codis per a lletres

Moltes aplicacions necessiten representar lletres a més de quantitats. En aquests casos, el que es fa és crear un codi a manera de diccionari que atribueix a cada lletra una cadena de símbols binaris, normalment d’un tamany fixe (anomenats codis uniformes). Depenent de l'alfabet a representar i de la tecnologia existent s'utilitza un codi o un altre, però el més utilitzat ha estat el codi ASCII per a l'alfabet anglès, ideat l'any 1963 i que codifica cada lletra com una seqüència de 7 bits. Actualment s'utilitzen extensions de l'ASCII amb caràcters com les lletres amb accent; i propostes com Unicode, que busca integrar totes les formes d'escriptura utilitzades en el món en un únic codi, permetent per exemple text en castellà, grec, japonès, hebreu i àrab en un mateix document.

Comprimint...

...text

Tenint un codi per a lletres podem plantejar-nos el problema de com comprimir un document de text. Realment, amb un codi que assigni una seqüència de tamany fixe a totes les lletres, l'única manera de reduir la longitud d'un text és utilitzar menys bits per lletra, però això redueix el nombre de lletres que es poden utilitzar (amb 7 bits es poden representar 128 caràcters, però amb 6 només 64, amb 5 només 32...). Un punt clau és adonar-nos que no totes les lletres són igual de freqüents, de manera que podríem crear un codi que assigni seqüències més curtes a les lletres més usades, i seqüències més llargues a les menys habituals. Amb un codi així, es pot esperar que la longitud total de tot un text serà més curta que la del mateix text usant un codi uniforme. Un exemple apareix a la figura de la dreta. En ella s'observa un alfabet amb només 4 lletres: A, B, C i D. La lletra A és 2 vegades més freqüent que la B i 4 vegades més freqüent que la C i la D; usant un codi uniforme de 2 bits la paraula AAAABBCD es codifica amb 16 bits mentre que usant un codi de longitud variable s'usen només 14. A aquest tipus de codi se l’anomena codi de Huffman, va ser inventat l'any 1952, i encara que existeixen altres tipus de codi que comprimeixen millor, aquest se segueix utilitzant en moltes aplicacions per la seva simplicitat.

...i altres arxius:

Tots els arxius d'un ordinador es poden considerar com documents de text en un alfabet imaginari. Evidentment, podem aplicar sobre ells mètodes com el de Huffman per reduir la seva grandària. No obstant això, alguns continguts destinats directament als humans, com imatges, so o vídeo, permeten una major compressió a canvi de perdre una mica d'informació, ja que el nostre cervell és capaç de recompondre la part perduda. Veiem alguns exemples:

Imatges

Imatges com fotografies, en les quals existeixen grans zones d'un mateix color, permeten sacrificar els detalls més petits i encara així mantenir el contingut principal. Mètodes de compressió que sacrifiquen informació n’hi ha molts, segons el tipus d'imatge, però potser el més comú és el JPEG per a fotografies, usat en la majoria de càmeres digitals. Altres mètodes com GIF o PNG resulten més adients per a fitxers que continguin gràfics.

So

La nostra oïda no és igual de sensible a totes les freqüències de so. El format de compressió de so més popular, l’MP3, aprofita aquest fet per a reduir la grandària dels fitxers. Prenent com a referencia aquest comportament de l'oïda, s'eliminen parts de les ones acústiques a les quals som poc sensibles per tal d’aconseguir una grandària d'arxiu menor.

Vídeo

Una altra capacitat del nostre cervell és la de distingir entre figures i fons. No és necessari guardar tota la imatge en cada fotograma d'un vídeo, ja que molt sovint en dos fotogrames consecutius el fons no haurà canviat gairebé i seran molt semblants. Si guardem tan sols els canvis entre imatges, podem reduir enormement la grandària dels arxius de vídeo, i aquesta idea és la que apliquen, entre d’altres, els estàndards de vídeo MPEG o ITU-T