La compression des données

La nuit est encore jeune. Le feu crépite dans l'âtre. La danse des flammes, la chaleur du logis, les muscles endoloris. Affalé dans un large fauteuil, le corps se repose pendant que l'esprit vagabonde. De quoi parlait-on tout à l'heure? Ah oui, la compression de données...

...en phase de rêve, le cerveau opère un tri...

Extraits:

• Rajouter un niveau ("Transformation des données") au pipeline de compression est une idée qui paraît bête, simple, intuitive... en quoi la transformation de Burrows-Wheeler est-elle remarquable ?

  Le problème est de trouver une transformation qui soit à la fois réversible et favorable à la compression. Trouver une transformation favorable à la compression n'est pas difficile: il suffit par exemple de trier les octets. Ce qui est difficile, c'est de pouvoir réaliser l'opération inverse.

  La compression de données, au final, est un indicateur de l'entropie des données au sens où l'entend David Ruelle :

  entropie = quantité de hasard

  Un fichier qui ne contient pas du tout de hasard, dont les éléments sont tous prévisibles à l'avance, sera beaucoup compactable. Par exemple un fichier rempli de zéros. La quantité d'information qu'il contient est nulle, le hasard inexistant, l'entropie minimale.

  Au contraire, un fichier zippé (déjà compacté avec PKZip) contient des octets apparemment aléatoires sans aucune relation les uns avec les autres. La quantité d'information y est maximale, presque par définition puisqu'il s'agit d'un fichier déjà compressé, donc dont on a a priori supprimé toutes les redondances. Il contient par ailleurs une dose de hasard maximale, soit une entropie maximale.

  La notion à dégager de ces exemples est la notion de structure. La structure du fichier rempli de zéros est la structure la plus parfaite qui soit, la plus ordonnée. A l'inverse, la structure du fichier zippé est inexistante : les octets aléatoires se suivent sans logique, c'est une structure chaotique. L'ordre et le chaos. Il semble qu'une fois de plus ces deux frères ennemis se retrouvent face-à-face... L'ordre favorise la compression, le chaos est incompressible.

  Il en résulte que la transformation à appliquer aux données pour favoriser leur compression est une transformation qui augmente leur degré d'ordre - ou qui diminue leur degré de stochasticité, c'est selon. En d'autres termes il s'agit de trouver une transformation qui diminue la quantité de hasard, ou encore qui diminue l'entropie....

  Ce qui est contraire à la seconde loi de la thermodynamique!

  C'est pourtant précisément ce que réalise la transformation de Burrows-Wheeler. Et c'est pour cela qu'elle est vraiment remarquable!

  (NB : d'accord, il doit y avoir une faille béante quelque part dans le raisonnement mais peu importe, ça donne une bonne idée du problème..)

  
  

  Oui, mais...

  Le hasard n'existe pas. Le hasard n'est que le nom générique sous lequel nous désignons tous les phénomènes que nous ne savons pas expliquer. Et comme le dirait mieux que moi Jean Guitton, pourquoi ce qui nous apparaît comme désordonné et aléatoire à un certain niveau d'analyse ou de conscience ne serait-il pas au contraire très ordonné à un niveau supérieur? Par exemple la suite des décimales de PI est un modèle éprouvé de données aléatoires (il y a des gens qui ont étudié ça en détails, établi des tonnes de statistiques, écrit des livres entiers sur le sujet). Pourtant on ne peut pas vraiment dire que PI est un modèle de chaos... c'est même au contraire le nombre clé autour duquel se bâtit la figure géométrique la plus parfaitement ordonnée : le cercle. Le chaos au milieu de l'ordre, l'ordre au coeur du chaos, la Licorne et le Logrus s'affrontent et s'unissent, s'enlacent et se déchirent... CHAOS EQUALS ORDER! Pourquoi donc utiliser deux mots désignant finalement la même chose?...la même chose...un hasard prévisible... Que devient l'entropie dans tout ça?

  Je ne l'ai pas sur le boût de la langue, plutôt sur le boût du synapse. Il y a quelque chose là-derrière.

  ...et dire qu'on était parti d'un pauvre archiveur...

  
  

• Peut-on modéliser une structure aléatoire?

  Une structure aléatoire comme un fichier ZIP contenant une quantité maximale d'information est a priori incompressible.

  Jusqu'à preuve du contraire.

  Des plaisantins ont déjà proclamé haut et fort qu'ils avaient réussi cet exploit - je pense notamment à WEB Technologies. Mais il n'y a jamais eu de suites, et ce n'étaient sans doute que du vent.

  Les derniers plaisantins en date ont même poussé le vice jusqu'à obtenir une licence pour leur "technique de compression de données aléatoires". Affaire à suivre, mais avec scepticisme.

  Pourtant... L'ordre est au coeur du chaos... Et si jamais...

  Les idées fusent, l'esprit s'égare, imagine des dizaines d'algorithmes différents qui ne donnent rien. L'exemple de PI donne de la matière sur laquelle cogiter. Les décimales de PI étant infinies, on pourrait sans doute y trouver une séquence reproduisant parfaitement n'importe quelle séquence de nombres aléatoires. Il suffirait de remplacer le programme à compresser par une paire Index/Longueur indiquant l'emplacement de la correspondance, comme si les décimales de PI étaient notre dictionnaire statique dans une compression de type Lempel-Ziv... Alléchante perspective, mais qui ne donne rien en pratique, bien entendu. D'abord il n'est pas dit que la séquence recherchée soit effectivement présente dans les décimales de PI. Ensuite, même si c'était le cas, le nombre de bits nécessaires au codage de l'index serait sans doute très supérieur à la taille de n'importe quel programme à compresser! Le problème de l'infini est surtout sémantique : on manipule le mot parce qu'il est commode pour décrire certaines choses, mais on ne se rendra jamais bien compte de ce qu'il signifie. A défaut on pourrait essayer de limiter la recherche à un nombre de décimales données, et essayer de trouver des correspondances entre elles et le programme à coder. Rien n'empêche également de multiplier les dictionnaires. PI, exp(1), etc... Bon, soit: il y a très peu de chances pour que cette approche débouche sur quoi que ce soit d'utilisable. On tourne en rond.

  Continuons à creuser, la nuit n'est pas très avancée et il faut bien que j'occupe cet esprit qui refuse l'inaction.

  
  

  Mandelbrot. L'ensemble M. Voilà un exemple absolument fascinant qui ne laisse aucun répit au rêveur torturé que j'essaye en vain d'arrêter d'être ! Le fait est là. A partir d'une simple, d'une minuscule équation que je reproduis ici:

  
  

  z(n+1) = z(n)^2 + C

  
  ...on génère un univers. Les images fractales se démocratisent. On les voit partout, même dans les endroits les plus inattendus - Dance Machine !!! Mais bien peu perçoivent leur force. Avec la petite équation que voilà, on peut générer une immense, une gigantesque, titanesque fresque qui couvrirait sans broncher la distance Terre-Lune, ou Terre-Saturne, voire le système solaire entier si le coeur vous en dit. En fait, la taille de l'image fractale générée est potentiellement infinie. Infinie! Revoilà l'infini qui pointe le boût de son nez : attention danger ! Infini? Ne pourrait-on pas trouver dans cet infini une petite portion d'image sympathique qui coderait parfaitement notre programme à compresser ? Non, non, c'est le même problème qu'avec les décimales de PI. L'aspect visuel en plus. L'ordre au coeur du chaos, le chaos au coeur de l'ordre. Sauf que l'ordre est ici visible. Pire : les motifs générés sont "jolis" !! Tous aux abris! Voilà qu'une équation complexe se met à générer du sentiment et de la beauté dans les esprits des ménagères de moins de 50 neurones! De quoi se poser de sacrées questions. A rapprocher du "scandale permanent" qu'est la musique chez David Ruelle. Si simple et si compliqué. Ordre, chaos... d'où viendra le lien définitif entre les deux?

Le feu est éteint, je me réveille péniblement...
Le chat dort.