La informació digital es pot comprimir i enviar per internet o guardar de manera que ocupi i “pesi” menys. Després, quan volem recuperar-la, només hem de descomprimir-la com si traguéssim l’esponja que guardem ben premuda en una caixeta. Els algorismes de compressió són ben corrents, avui en dia. Quan mirem fotos en format .jpg o .jpeg estem veient imatges comprimides, i quan mirem vídeos de YouTube estem utilitzant versions molt compactes, de menor qualitat que els originals. Però els sistemes de compressió de les fotos i vídeos eliminen informació. A partir d’una imatge comprimida en .jpg mai podrem recuperar la qualitat original. Quan reduïm i simplifiquem, perdem informació, com quan resumim un llibre. Estem retallant trossos i quedant-nos amb el més significatiu. Els anglesos diuen que en aquests casos, estem fent una compressió “lossy“. Hi ha altres algorismes, en canvi, que saben comprimir sense perdre informació. Son els algorismes “lossless“, en terminologia anglosaxona. En aquest cas podem parlar d’informació elàstica. La comprimim i la fem petita per a guardar-la o enviar-la. Però en qualsevol moment podem descomprimir-la i recuperar-la amb tots els seus detalls originals. És el que fem quan comprimim un o més fitxers i els deixem, per exemple, en format .zip o en formats com el que podeu veure a la nota del final. És fonamental que aquests sistemes puguin recuperar els documents originals sense pèrdua d’informació, perquè en cas contrari degradarien els nostres texts i no ens servirien de res.
Sabíeu que, en menys d’un minut i amb les eines clàssiques de compressió de fitxers que tenim a tots els ordinadors, podem calcular la probabilitat que un text hagi estat parcialment copiat d’un altre? Ho podem fer gràcies a Kolmogorov, que ens va ensenyar que la informació no sols és elàstica sinó que, analitzant la seva elasticitat, podem mesurar si és molt o poc complexa.
Andrei Kolmogorov va néixer a Tambov l’any 1903. Va estudiar a la Universitat Estatal de Moscou i ben aviat va proposar la seva teoria de la complexitat algorísmica. La idea és ben senzilla: de manera intuïtiva, Kolmogorov ens diu que una determinada informació és senzilla o poc complexa si es pot explicar amb poques paraules, i que en canvi té una complexitat elevada si és difícil d’explicar-la. Mireu els dos requadres de la imatge. El de l’esquerra es pot descriure dient que representa “quatre per quatre quadrats vermells”. En canvi, per descriure de manera precisa el de la dreta i explicar el dibuix que formen els quadrats vermells i grocs, calen molt més de cinc paraules. En d’altres paraules: la complexitat de Kolmogorov del requadre de l’esquerra és més baixa que la del de la dreta. A les primeres pàgines d’aquest article trobareu més exemples del mateix.
Si tinguéssim el millor sistema possible de compressió elàstica (sense pèrdua d’informació), es fàcil veure que el seu grau de compressió ens donaria la complexitat de Kolmogorov de qualsevol document, imatge o vídeo. Això és així perquè no hi ha millor manera de comprimir el requadre de l’esquerra de la imatge que escriure, en algun llenguatge compacte, “quatre per quatre quadrats vermells”. El problema és que no coneixem ni podem disposar d’aquest ideal “millor sistema possible” de compressió elàstica, i això fa difícil el càlcul precís del grau de complexitat dels nostres texts, imatges i documents. Però sí que podem calcular una mesura aproximada d’aquesta complexitat de Kolmogorov si tenim un sistema de compressió prou bo, i en molts casos, això ja ens pot servir. Investigadors com Leanne Seaward, Stan Matwin i molts altres utilitzen bons sistemes de compressió elàstica com per exemple l’algorisme Lempel–Ziv–Welch (vegeu la nota al final) per mesurar la complexitat de texts i per detectar plagis i còpies entre documents. El seu mètode es basa en calcular el que ells anomenen la distància de compressió normalitzada (NCD, vegeu la nota al final) entre els dos texts que estem analitzant.
I com es calcula aquesta màgica “distància de compressió normalitzada” que ens diu si un text és còpia de l’altre o no? L’únic que cal fer és comprimir el primer text, comprimir el segon text, i comprimir el text conjunt que obtenim per concatenació dels dos primers. Ens apuntem la mida, en octets o bytes, de cada un dels tres fitxers comprimits, i només hem de fer una resta i una divisió per a obtenir un indicador que ens diu el grau de semblança entre els dos texts i ens explica si som davant d’un cas de còpia o no. L’explicació intuïtiva es basa en que cada autor té el seu estil. Un bon sistema de compressió, en els casos de còpia sempre aconseguirà un millor resultat i un fitxer comprimit del fitxer concatenat que ocuparà menys bytes, perquè detectarà que les pautes d’autor del primer text es repeteixen el el segon, i aquestes darreres les podrà “explicar” en base a les que ja ha trobat en el primer text. Com ens va dir Kolmogorov, és més fàcil explicar (i comprimir) dos texts amb el mateix estil que dos texts diferents.
He de reconèixer que em captiva el fet que camps ben diversos es connectin i acabin donant fruits sovint inesperats. Qui ens havia de dir, fa uns anys, que les idees de Kolmogorov i els mètodes de compressió que utilitzem quan volem enviar fitxers grans per correu electrònic, ens podrien servir per detectar còpies. De fet, la idea és ben senzilla i fàcil d’usar. Tant, que alguns professors del meu departament de la UPC ja l’estan aplicant amb èxit…
Per cert, Ferran Requejo diu que el rescat de bancs privats, l’empobriment de la població i les pràctiques de corrupció constitueixen una presa de pèl sistèmica. Diu també que l’economia financera, que va causar la crisi, segueix dominant molt més enllà del pes de l’economia productiva.
—–
NOTA: L’algorisme Lempel–Ziv–Welch, anomenat també LZW, va ser proposat per Abraham Lempel, Jacob Ziv i Terry Welch entre els anys 1978 i 1984. S’utilitza en Linux i en el format .gif per imatges digitals, i és elàstic perquè comprimeix sense perdre informació. L’algorisme original de 1984 codifica una seqüència d’octets (bytes o conjunts de 8 bits) tot transformant-la en una seqüència de grups (que anomenarem codis) de 12 bits. El conjunt de totes les 4096 possibles combinacions d’aquests 12 bits conformen el diccionari de compressió, que es va generant a mesura que es llegeix la seqüència d’octets que volem comprimir i que després guiarà el procés de recuperació o descompressió. Imaginem que volem comprimir el text “Jean Daniel diu que cal anar a la força de la raó, més que a la raó de la força”. Inicialment, preparem el diccionari de manera que les seves 256 primeres entrades siguin el codi de totes les lletres i signes de puntuació. Ho podem fer perquè cada caràcter d’un text es codifica en un octet i perquè el nombre de possibles octets diferents és 256. Ara, la regla LZW de compressió és aquesta: en cada moment, agafem la màxima seqüència de caràcters consecutius a partir d’on ens trobem, de manera que el següent caràcter donaria lloc a una seqüència que no tenim al diccionari. El codi d’aquesta màxima seqüència (sense el caràcter final) s’afegeix al text comprimit i aquesta màxima seqüencia (ara, amb el caràcter final) s’inclou com una nova entrada en el diccionari. En el nostre cas, és fàcil veure que el text comprimit començarà amb els codis individuals de les lletres “J”, “e”, “a”, “n”, “_”, “D” (indico l’espai en blanc com “_”). Però a la vegada haurà afegit noves entrades al diccionari per a les seqüències “Je”, “ea”, “an”, “n_”, “_D” i “Da”, de manera que a partir d’ara ja podrà avançar de dos en dos en algun cas i donar el codi comprimit de “an” (que ja el troba al diccionari) mentre inclou la nova entrada “ani”. És fàcil veure que el diccionari aviat acabarà tenint entrades per paraules com “que” i trossos com “la força” o “la raó”. L’algorisme LZW és eficient perquè el seu diccionari acaba incorporant més de 3000 termes i frases que es repeteixen al llarg del text i que identifica. D’aquesta manera, l’algorisme de compressió s’adapta a l’estil de l’autor.
El càlcul de la distància de compressió normalitzada NCD entre dos texts X, Y és ben senzill. Només cal comprimir cada un dels dos texts per separat, i després comprimir el text XY, que es forma per concatenació de X i Y. Si les mides dels tres fitxers comprimits (en bytes) són CX, CY i CXY respectivament i si diem M al màxim dels dos valors CX i CY i m al seu mínim, el valor de la distància de compressió normalitzada NCD és el resultat de calcular l’expressió (CXY-m)/M. Si aquest valor de la distància NCD és petit, és que els texts X i Y són semblants en l’essencial. Si és gran, és que són independents.
