Quelques Commentaires et Définitions concernant la Compression et la DéCompression
(Site WWW CMAP28 : cette page a été créée le 30/08/2015 et mise à jour le 16/05/2021 13:04:28 -CEST-)
Plan de ce document :
01-Simplification des sources C :
Les programmes C utilisés pour ces expériences ont été rédigés
en respectant des consignes strictes de rédaction
destinées à améliorer la lisibilité, la qualité, la maintenabilité
et l'évolutibilité des logiciels (c'est par exemple le cas du
programme générant une croix fractale).
Ces programmes contiennent donc un certain nombre d'éléments a priori inutiles
au moment de l'exécution (par exemple des tabulations, des parenthèses redondantes,...).
Ils ne peuvent donc prétendre être des programmes courts et encore moins les programmes les plus courts.
Pour évaluer leur longueur "utile", il est donc nécessaire de les simplifier. Cela consiste en particulier à :
- supprimer toutes les tabulations sémantiquement inutiles,
- supprimer les structures vides ("{}"),
- supprimer les parenthèses redondantes ("()"),
- compacter le nom des variables (trois caractères au maximum),
- regrouper les déclarations de même type,
- (...)
Cette simplification précède en général les compilations...
02-Définition des binaires non exécutables :
La simplification des programmes C (ou tout autre langage) ne résoud pas le problème de la recherche
des programmes courts, voire des programmes les plus courts. D'une part, pour un problème donné,
il peut évidemment exister des algorithmes meilleurs (dans le sens de la plus courte formulation) et/ou
des façons plus "économiques" de programmer un certain algorithme.
D'autre part, une difficulté surgit en particulier avec la représentation des chaînes aléatoires.
En effet, la théorie de la Complexité Algorithmique de Kolmogorov définit une telle chaîne
par le fait que le programme le plus court PPC qui la décrit a comme longueur (exprimées en bits) le nombre de bits N qu'elle contient,
plus une constante.
Longueur(PPC) = N + constante
Soit par exemple la chaîne aléatoire :
S=00101011100001001110011001001010001110100010000110101000110001100011010101111011111101000101101011100001100110010101000100010101...
Suivant la définition précédente, le programme C le plus court P1 serait (avant simplification...) :
main()
{
printf("00101011100001001110011001001010001110100010000110101000110001100011010101111011111101000101101011100001100110010101000100010101...");
}
Or malheureusement chaque bit de S est matérialisé ci-dessus à l'aide de l'un des deux caractères "0" ou "1",
représentés dans le code ASCI par huits bits (00110000 et 00110001 respectivement). La longueur (en bits) de P1 est donc :
Longueur(P1) = (8/1)xN + constante = 8xN + constante
P1 n'est donc pas PPC. Le regroupement des bits de S par paquets de quatre donnant un chiffre hexa-décimal :
S=0010 1011 1000 0100 1110 0110 0100 1010 0011 1010 0010 0001 1010 1000 1100 0110 0011 0101 0111 1011 1111 0100 0101 1010 1110 0001 1001 1001 0101 0001 0001 0101...
S= 2 b 8 4 e 6 4 a 3 a 2 1 a 8 c 6 3 5 7 b f 4 5 a e 1 9 9 5 1 1 5
S=2b84e64a3a21a8c6357bf45ae1995115...
donne le programme P2 :
main()
{
printf("2b84e64a3a21a8c6357bf45ae1995115...");
}
Chaque chiffre hexa-décimal étant lui-aussi matérialisé par huits bits, la longueur (en bits) de P2 est :
Longueur(P2) = (8/4)xN + constante = 2xN + constante
ce qui est mieux, mais malheureusement ne correspond pas à la définition de PPC...
Oublions donc l'utilisation de la fonction 'printf(...)' et réécrivons P2 sous la forme P3 :
main()
{
long int ChaineBitsAleatoires[]={0X2b84e64a3a21a8c6L,0X357bf45ae1995115L,...};
}
et cette fois-ci mesurons la longueur (en bits), non pas du source C de P3, mais du binaire
obtenu après compilation sans édition de liens (c'est-à-dire sans ajouter les inévitables
fonctions "système" nécessaires au bon fonctionnement d'un programme). Nous avons alors :
Longueur(P3) = N + constante
Ainsi, la longueur (en bits) du programme G2 est
suivant le nombre N de chiffres binaires de la chaîne aléatoire :
N = 1000000 bits Longueur(G2) = 126640 octets = 1000000 + 13120 bits
N = 872000 bits Longueur(G2) = 110640 octets = 872000 + 13120 bits
N = 744000 bits Longueur(G2) = 94640 octets = 744000 + 13120 bits
N = 616000 bits Longueur(G2) = 78640 octets = 616000 + 13120 bits
N = 488000 bits Longueur(G2) = 62640 octets = 488000 + 13120 bits
N = 360000 bits Longueur(G2) = 46640 octets = 360000 + 13120 bits
N = 232000 bits Longueur(G2) = 30640 octets = 232000 + 13120 bits
N = 104000 bits Longueur(G2) = 14640 octets = 104000 + 13120 bits
Longueur(G2) = N + 13120 bits
C'est donc la longueur du binaire après compilation sans édition de liens qui est la bonne
mesure de la longueur d'un programme, compatible avec la théorie de la Complexité Algorithmique de Kolmogorov.
03-Comptage des instructions arithmétiques effectivement exécutéees :
Afin de compter le nombre d'instructions arithmétiques (addition, soustraction, multiplication et division)
nécessaires à synthétiser une image, le dispositif suivant a été intégré
dans l'un des fichiers d'include commun et n'est activable que par une option
de compilation.
Chaque opérateur arithmétique élémentaire ('+', '-', '*' et '/') est alors remplacé par une fonction.
Ainsi, par exemple, l'addition entière se fera via la fonction 'ADD2(...)' ainsi définie :
long int compteur_ADD2=0;
long int ADD2(long int x,long int y)
{
compteur_ADD2++;
return(x+y);
}
Les compteurs associés à chaque fonction sont ensuite édités à la fin de l'exécution des programmes.
04-La complexité structurelle de Bennett (ou Logical Depth LD) :
La Complexité Structurelle de Bennett d'un objet est définie comme étant la durée d'exécution du plus petit
programme décrivant cet objet. Malheureusement, une durée d'exécution n'est pas une
mesure absolue. Pour rendre cette notion indépendante des contrainte matérielles
(fréquence d'horloge, technologie sous-jacente, charge des machines utilisées,...)
elle est remplacé par la mesure du nombre d'instructions exécutées par un programme.
Ce comptage se fait grace à la commande valgrind
disponible sous Linux. Celle-ci compte "tout simplement" le nombre d'accès au cache instructions du(des) processeur(s).
On fait alors l'hypothèse simplificatrice (mais réaliste) que toutes les instructions demandent le
même temps pour s'exécuter : le temps d'exécution d'un programme est alors proportionnel
au nombre d'instructions exécutées.
Une difficulté non résolue vient du fait qu'en théorie, la Complexité Structurelle de Bennett est définie
à l'aide d'une machine de Türing. Or ses "instructions" IT sont tout à fait élémentaires et non rien à voir
avec les instructions "machine" IM qu'exécutent les micro-processeurs. Existe-t-il alors une façon universelle de
passer d'un nombre de IT à un nombre de IM et réciproquement ? Il convient de noter que les choses se compliquent énormément
si l'on prend en compte (ce qui est une nécessité) le fait qu'une machine de Türing est strictement séquentielle, alors que les micro-processeurs
ont un fonctionnement de plus en plus parallèle ; ce parallélisme existe à de nombreux niveaux : en particulier plusieurs
instructions "machine" indépendantes peuvent s'exécuter simultanément, mais aussi chaque instruction "machine" est
décomposée en plusieurs "micro-instructions" parallélisables ! Alors est-ce si facile d'évaluer LD sur un ordinateur "réel" ?
Afin d'exclure toutes les instructions qui sont exécutées par un programme, mais qui ne font pas
partie de l'algorithme qu'il implémente (et en particulier toutes les fonctions dites système),
la solution suivante a été implémentée. Elle consiste à transférer tout ce que fait le programme principal
(le fameux 'main(...)' du C) dans une fonction appelée 'FonctionPrivee_sous_main(...)' définie
dans l'un des fichiers d'include commun :
void FonctionPrivee_sous_main()
{
TOUTES LES INSTRUCTIONS A EXECUTER
}
int main()
{
FonctionPrivee_sous_main();
}
A la fin de l'exécution, il suffit de demander à valgrind le nombre d'instructions
exécutées par la fonction 'FonctionPrivee_sous_main(...)' et par toutes celles que cette dernière a appelé
et ce de manière récursive...
05-Evaluation de la Complexité de Kolmogorov CK (ou K) :
Pour évaluer la Complexité de Kolmogorov CK (ou K) d'un "objet" lorsqu'aucun programme le décrivant ou l'engendrant n'est connu (et
donc a fortiori le plus petit programme...) une solution consiste à le comprimer de façon
réversible et à prendre la longueur du fichier résultant comme mesure de CK. Evidemment plusieurs algorithmes de
compression sont disponibles et c'est celui qui donne le meilleur taux qui doit être utilisé...
06-Evaluation de la Complexité de Bennett CB (ou Logical Depth LD) :
Pour évaluer la Complexité de Bennett CB (ou LD -Logical Depth-) d'un "objet" lorsqu'aucun programme le décrivant ou l'engendrant n'est connu (et
donc a fortiori le plus petit programme...) il convient d'utiliser le fichier compressé le plus
petit obtenu pour évaluer la Complexité de Kolmogorov. Le nombre d'instructions alors nécessaires à la décompression
sera utilisé comme mesure de CB.
Ce comptage se fait, lui aussi, grace à valgrind...
07-Définition des matrices K/LD :
Ces matrices visualisent les éventuelles corrélations existant entre les
classements 'K' (Complexité Algorithmique de Kolmogorov sur l'axe horizontal -orienté de gauche à droite-)
et 'LD' (Complexité Structurelle -ou Logical Depth- de Bennett sur l'axe vertical -orienté de bas en haut-).
Ainsi, par exemple, si le programme 'Pn' apparait
à l'intersection de la deuxième colonne -en partant de la gauche- et de la troisième ligne -en partant du bas- d'une telle matrice,
cela signifie qu'il est respectivement deuxième et troisième dans les classements 'K' et 'LD' correspondants.
08-Quelques problèmes :
1f 8b 08 00 5e 47 e9 55 00 03 ed c1 31 01 00 00 1f 8b 08 00 57 47 e9 55 00 03 ed c1 31 01 00 00
00 c2 a0 f5 4f 6d 08 5f a0 00 00 00 00 00 00 00 00 c2 a0 fe a9 67 08 5f a0 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 3e 03 1c ea 38 a7 00 00 10 00 00 00 3e 03 74 ac 6b 95 00 00 10 00 00
08.01.04-L'existence de comportements non homogènes (traiter différemment une
image NOIR
et une image BLANC par exemple, tant au niveau "spatial" que
"temporel").
08.01.05-La monodimensionnalité des compresseurs/décompresseurs standards (même
JPEG2000 ou encore PNG semblent présenter des comportements anormaux
concernant l'invariance déjà évoquée au paragraphe 8.1.1).
08.02-Des questions relatives aux outils spécifiques :
Ces expériences ont donc utilisé d'une part des
compresseurs/décompresseurs standards
(c'est-à-dire disponibles sur tout systeme -LINUX en particulier-) et d'autre part
quelques uns (simples -RLE en particulier-)
réalisés spécifiquement. Mais peut-on
comparer les performances de programmes écrits par des gens de formations et de
cultures différentes ? Je rappelle qu'en ce qui me concerne je demande à mes
programmes de fonctionner correctement (c'est la moindre des choses) sans mise
au point (si possible) et d'être lisibles et "beaux" : cela signifie qu'en général
je ne privilégie pas la performance.
Une autre question concerne la definition même des outils spécifiques réalisés
et en particulier celle du compresseur/décompresseur dit "neutre" : nous n'avons
pas vraiment su comment le définir (devait-il vraiment ne rien faire, ou encore
lire/écrire un fichier, ou encore lire/écrire un fichier avec déplacement du contenu
des buffers,... ?) de façon à ce que ses performances soient "compatibles" et
comparables avec celles des autres compresseurs/décompresseurs. Il y avait là
d'ailleurs un degré de liberté incompatible avec la méthode puique l'on pouvait
changer ses performances en changeant sa définition... D'ailleurs cette remarque
vaut aussi pour les autres et en particulier le compresseur/décompresseur dit
"optimal" : comment le programmer et que faire des différents "overheads" système
inhérents à sa programmation ?
08.03-Des problèmes omis :
08.03.01-Combien de bits par pixel ? Les compresseurs/décompresseurs (tous ?) travaillent
sur des "atomes" de 8 bits (octet). Mais le nombre de bits par pixel dans une image
peut être different (1 est une valeur fréquente, mais aussi 10, 12,...). Ainsi,
dans le cas de 1 bit par pixel, les compresseurs/décompresseurs vont traiter
les pixels par paquet de 8 ce qui conduira nécessairement à des artefacts
(par exemple, une ligne oblique blanche sur fond noir ne correspondra pas
à une suite de 1, mais en général à une alternance de nombreux octets différents).
08.03.02-N'oublions pas de plus, que le problème des images dites en vraies couleurs a été négligé.
08.03.03-Il conviendrait de faire des expériences relatives
à la nécessaire invariance des classements vis à vis de l'homothétie. Et d'ailleurs que faire
si l'on veut classer entre-elles des images de tailles et de formats differents ?
Ce sont là peut-être des questions à traiter dans un second temps, mais malgré
tout il peut être nécessaire de les intégrer dès le départ afin qu'elles ne
remettent pas tout en cause ultérieurement...
08.04-De la comparaison des performances :
Le classement des images suivant leur profondeur logique se fait en mesurant
les durées de décompression, ce qui nous amène à comparer les performances
de plusieurs programmes. Or je ne suis toujours par convaincu que l'on ait
le droit de le faire. Dans le cas de deux programmes P1 et P2, s'ils travaillent
sur les mêmes données (que l'algorithme de traitement soit le même ou pas...) cela
est possible à condition qu'ils aient été programmés de la "même façon", avec les
mêmes outils (compilateurs,...) et qu'ils soient figés (toute modification de
l'un d'eux peut aboutir à une "inversion" des performances). Mais si de plus
les données sont différentes, ce qui est notre cas (les données sont alors les
fichiers compressés) cette comparaison devient impossible...
08.05-L'impossible pérennisation des mesures de performance :
L'une des grosses difficultés que nous avons rencontrée fut celle de la mesure
de la durée de décompression. Elle fut résolue de façon stable grace à 'valgrind',
outil d'émulation de processeurs. Cela a permis d'effectuer des mesures pérennes,
mais malheusement à court terme ; en effet, les programmes, les compilateurs et les
processeurs évoluent au cours du temps en offrant des performances toujours meilleures
ce qui fait qu'un programme qui demande aujourd'hui N1 opérations pour s'exécuter
sur un certain processeur P1 en demandera N2 (N2 < N1 en général) demain (c'est vrai dès
aujourd'hui sur un processeur P2, mais alors on a seulement N2 # N1). Un autre
problème qui ne doit pas être négligé est celui des différents parallélismes qui
peuvent être "invisibles" lors des mesures de performances.
Les progrés constants accomplis en matière de micro-processurs posent eux-aussi de sérieux
problèmes : ainsi, par exemple, des algorithmes tels le "RLE" qui a priori
demandent de nombreuses opérations peuvent du jour au lendemain se voir réduits à une seule instruction.
Le LD calculé se verrait alors réduit considérablement, alors que le LD "théorique" n'aurait
évidemment pas changé !
Voici une expérience faite le 20150831 sur les deux machines différentes (aux niveaux matériels et logiciels)
"01" (=LACT19) et "04" (=CMAP28/porte-brancion) avec
l'image 
choisie arbitrairement. Malheureusement,
il y a beaucoup de fortes disparités. Voici les plus importantes :
01 : NombreDInstructionsDeCompression ("Neutre.01$vv$X") ............... = ............584.061
04 : NombreDInstructionsDeCompression ("Neutre.01$vv$X") ............... = ..........5.425.514
01 : NombreDInstructionsDeCompression ("lzma --best") .................. = ......3.291.078.710
04 : NombreDInstructionsDeCompression ("lzma --best") .................. = ......1.017.710.736
01 : NombreDDonneesLuesDeCompression ("Neutre.01$vv$X") ................ = ............114.649
04 : NombreDDonneesLuesDeCompression ("Neutre.01$vv$X") ................ = ..........1.095.933
01 : NombreDDonneesLuesDeCompression ("lzma --best") ................... = ........820.744.919
04 : NombreDDonneesLuesDeCompression ("lzma --best") ................... = ........337.761.292
01 : NombreDDonneesLuesDeCompression ("RunLengthEncoding.11$vv$X") ..... = ..........2.233.043
04 : NombreDDonneesLuesDeCompression ("RunLengthEncoding.11$vv$X") ..... = ..........8.523.516
01 : NombreDDonneesEcritesDeCompression ("Neutre.01$vv$X") ............. = .............78.653
04 : NombreDDonneesEcritesDeCompression ("Neutre.01$vv$X") ............. = ..........1.060.525
01 : NombreDDonneesEcritesDeCompression ("lzma --best") ................ = .........42.006.070
04 : NombreDDonneesEcritesDeCompression ("lzma --best") ................ = .........31.131.594
01 : LongueurDeLImageCompressee ("lzma --best") ........................ = ....3.699/1.048.576
04 : LongueurDeLImageCompressee ("lzma --best") ........................ = ....5.117/1.048.576
01 : NombreDInstructionsDeDeCompression ("Neutre.01$vv$X") ............. = ............581.660
04 : NombreDInstructionsDeDeCompression ("Neutre.01$vv$X") ............. = ..........5.422.896
01 : NombreDInstructionsDeDeCompression ("lzma --best") ................ = .........20.422.974
04 : NombreDInstructionsDeDeCompression ("lzma --best") ................ = .........11.186.788
01 : NombreDDonneesLuesDeDeCompression ("Neutre.01$vv$X") .............. = ............113.748
04 : NombreDDonneesLuesDeDeCompression ("Neutre.01$vv$X") .............. = ..........1.094.969
01 : NombreDDonneesLuesDeDeCompression ("lzma --best") ................. = ..........5.847.761
04 : NombreDDonneesLuesDeDeCompression ("lzma --best") ................. = ..........2.614.754
01 : NombreDDonneesLuesDeDeCompression ("RunLengthEncoding.11$vv$X") ... = ..........5.958.450
04 : NombreDDonneesLuesDeDeCompression ("RunLengthEncoding.11$vv$X") ... = ..........7.257.435
01 : NombreDDonneesEcritesDeDeCompression ("Neutre.01$vv$X") ........... = .............78.608
04 : NombreDDonneesEcritesDeDeCompression ("Neutre.01$vv$X") ........... = ..........1.060.614
01 : NombreDDonneesEcritesDeDeCompression ("lzma --best") .............. = ..........2.396.924
04 : NombreDDonneesEcritesDeDeCompression ("lzma --best") .............. = ..........1.086.793
Ces disparités concernent aussi bien un CDC "standard" ('lzma')
que deux des outils spécifiques ("Neutre" et "RLE"). Evidemment, certaines mesures ne
ne sont pas utiles ici (par exemple les nombres de données lues et écrites),
mais malgré tout, elles montrent que les comportements de programmes identiques
(apparemment...) peuvent différer considérablement d'une machine à l'autre.
Une chose très étrange concerne les outils spécifiques, puisqu'en ce qui les
concerne ce sont les mêmes sources qui sont utilisspécifiquess sur
les deux machines, de même que les options de compilation. Alors d'où
viennent les disparités ?
En ce qui concerne "Neutre" on a vraiment le sentiment qu'il ne fait rien
sur la machine "01" contrairement à "04". C'est bien le cas car, en effet, l'optimiseur de "01"
supprime une bonne partie du code se rendant compte qu'il
s'agit d'un simple déplacement d'un buffer A vers un buffer B et il rend
donc A et B equivalents, mais il n'en est rien sur "04" alors que
ce sont exactement les mêmes options de compilation qui sont utilisées !
Mais évidemment, les deux systèmes ne sont pas au même niveau,
"01" étant certainement et paradoxalement plus ancienne que "04"...
Pour "RLE", on ne peut rien dire de précis...
Pour ce qui est de "lzma", la machine "01" semble faire "plus de choses"
que la machine "04" ce qui dans un sens peut sembler logique puisqu'un
portable ("01") possède moins de ressources physiques qu'un serveur de
calcul ("04"), mais qui dans un autre sens pose de nouveau des problèmes
de portabilité et de pérennité.
08.06-La nécessaire reconnaissance des contenus :
Ainsi, ce sont les compresseurs/décompresseurs utilisés qui sont les véritables
responsables du blocage actuel. Je crois que l'on ne
peut pas faire l'économie de la reconnaissance du contenu d'une image si l'on
veut la bien compresser (c'est d'ailleurs pour cela que j'avais commencé des
expériences de segmentation en zones homogènes au niveau des textures). Je veux
dire par là qu'il ne m'est pas évident qu'un même compresseur puisse traiter
correctement tous les cas possibles : je ne crois pas à un compressuer universel.
Peut-être qu'identifier le contenu d'une image pourrait faciliter sa compression.
Mais cela voudrait peut-être dire alors plusieurs outils de compression différents
ce qui nous ramènerait alors à un problème déjà évoqué.
Le premier (et principal ?) problème à résoudre est donc pour moi celui de la compression...
08.07-Des expériences à réaliser :
08.07.01-Même si encore une fois je ne conteste absolument pas la définition mathématique
de la profondeur logique, je crois (et je l'ai déjà écrit) qu'il conviendrait de
choisir un ensemble de quelques images représentatives et de demander au public de
les classer. Cela serait évidemment très subjectif, mais il serait intéressant de voir
si alors émergerait nettement UN classement ou bien si chacun aurait le sien...
08.07.02-D'autre part concernant la performance des programmes, il pourrait être utile de
proposer la programmation d'un certain algorithme non trivial (faisant du calcul,
mais pas uniquement) à plusieurs groupes d'étudiants (déjà bien avancés dans leurs
études) pour voir la distribution des performances (et si les mesures étaient très
dispersées, cela serait inquiétant en ce qui concerne nos expériences...).
08.07.03-Tout cela pourrait être aussi l'objet d'un appel (sous forme de concours ?) aux
lecteurs de PLS...
08.08-Les images ex-aequo :
Il peut arriver que certaines images donnent certaines mesures égales. C'est par exemple
le cas de cette image 
et de celle-ci 
qui
donnent respectivement à la date du 20150820 :
LongueurDuSourceSimplifie................. = ......247
LongueurDuBinaireNonExecutable............ = ....1.824
NombreDInstructionsArithmetiquesDeSynthese = 4.199.426
LongueurDuSourceSimplifie................. = ......247
LongueurDuBinaireNonExecutable............ = ....1.824
NombreDInstructionsArithmetiquesDeSynthese = 4.199.426
Cela implique donc qu'elles aient, suivant les définitions,
même K et même LD. Cela est paradoxal dans la mesure où elles paraissent
très différentes.
En réalité leurs programmations sont strictement identiques : en chaque point {x,y},
la première calcule x+y quand
la seconde calcule x*y.
Etant donné de plus qu'elles font toutes les deux ce calcul pour chaque point une
fois et une seule, on peut affirmer que les deux programmes C,
une fois simplifiés, sont les plus petits possibles.
Il est donc vrai que ces deux images possèdent le même K.
Le même raisonnement semblerait montrer ces deux images possèdent le même LD,
puisque leurs deux programmes contiennent (et exécutent donc) le même nombre d'instructions. Mais en réalité,
ici, c'est la durée des calculs qui intervient. Si une multiplication prend un peu plus de temps qu'une addition
(ce qui semble logique...), alors, l'image qui fait des multiplications
(en calculant x*y) possède un LD supérieur (égal donc au temps de calcul) à celui
de l'image qui elle fait des additions (en calculant x+y)
et ainsi, "les choses rentrent dans l'ordre"...
On rappelle au passage que l'on fait l'hypothèse que toutes les instructions
demandent le même temps pour s'exécuter et qu'ainsi la durée d'exécution d'un programme
est proportionnelle au nombre d'instructions exécutées.
08.09-Les images de type plan de bits :
Dans une image type plan de bits, chaque point est codé
à l'aide d'un seul bit. Elle ne contient donc que deux symboles {0,1}.
Si elle est communiquée à un compresseur "standard", ce dernier ne verra
évidemment pas une suite de bits, mais une suite d'octets résultant du
regroupement des bits par paquets de huit (c'est-à-dire des octets).
A partir de ce moment-là, l'image possédera en général plus
de deux symboles (256 au maximum).
Le résultat de la compression ensuite effectuée ne correspondra pas du tout à
ce qu'il aurait été si le compresseur avait travaillé avec comme unité
le bit et non pas l'octet.
Cette difficulté peut être surmontée : il suffit de convertir au préalable
les images type plan de bits en images dans lesquelles
les points sont codés à l'aide d'un octet, celles-ci n'utilisant
donc que deux symboles (par exemple {0,255}...). On notera que, bien que cette conversion
multiplie évidemment par huit la longueur de l'image initiale, sa version compressé
sera plus petite que si elle n'avait pas été convertie !
08.10-Mono- contre bi-dimensionnel :
Les images sont des objets di-mensionnels alors que la plupart des outils de
compression sont des outils mono-dimensionnels. Voici une expérience faite
sur des "objets" mono-dimensionnels : il s'agit des 100.000 premières
décimales (codées en ASCII) de cinq constantes mathématiques (leur partie entière,
le point décimal ainsi que les caractères de changement de ligne ont été
éliminés) :
- Le nombre de Champernowne :
bzip2 --best ==> K=31320 LD=17642787
lzma --best ==> K= 5672 LD=12939225
xz -9 ==> K= 4656 LD=11253566
- e :
bzip2 --best ==> K=43184 LD=17392484
lzma --best ==> K=43658 LD=22578952
xz -9 ==> K=43732 LD=22847886
- Le nombre d'or :
bzip2 --best ==> K=43139 LD=17393298
lzma --best ==> K=43632 LD=22590057
xz -9 ==> K=43692 LD=22844156
- pi :
bzip2 --best ==> K=43153 LD=17390750
lzma --best ==> K=43639 LD=22599111
xz -9 ==> K=43732 LD=22856645
- Racine de 2 :
bzip2 --best ==> K=43144 LD=17378427
lzma --best ==> K=43633 LD=22588446
xz -9 ==> K=43688 LD=22844519
09-Quelques pistes :
- Renoncer à utiliser les compresseurs/décompresseurs standards,
puisque :
- leurs programmations ne sont pas homogènes (équipes différentes),
- leurs performances peuvent varier "brutalement" lors de mises à jour des systèmes ou de changements d'ordinateurs,
- leurs comportements sont parfois incohérents,
- etc...
- Cela implique de programmer au moins un compresseur/décompresseur en :
- suivant mes règles très strictes de programmation,
- utilisant un seul programmeur,
- y intégrant les outils de mesures utiles via des compteurs spécifiques
aux opérations utiles (arithmétiques, logiques, itérations,...),
ces compteurs étant ensuite pondérés et combinés pour donner une mesure de temps fiable et pérenne.
Il serait même possible d'envisager une structure hiérarchique de tels compteurs. Ainsi, par exemple :
ADD2(x,y) --> ((x)+(y))
MUL2(x,y) --> ((x)*(y))
AXPB(a,x,b) --> ADD2(MUL2(a,x),b)
avec un compteur associé à chacun de ces trois opérateurs.
Cela a été implémenté à titre expérimental dans le programme
"RUN-LENGTH ENCODING 12 (RLE12)"
et de façon opérationnelle dans le programme
"MAISON (CDCM1)".
- notant que le programme "RUN-LENGTH ENCODING 11 (RLE11)"
est trop simpliste et ne voit que des régularités très limitées.
Mais alors, comment définir le compresseur/décompresseur à réaliser et les régularités
qu'il verra (et donc celles qu'il ne verra pas et dont la liste exhaustive n'existe pas...) ?
- envisageant plusieurs possibilités de parcours des images :
- séquentiel ligne,
- séquentiel colonne,
- Peano (mais attention alors aux dimensions et aux formats des images),
- etc...
ce qui permettrait, par exemple, des "expériences" mono- et bi-dimensionnelles...
- etc...
- Renoncer à utiliser 'valgrind' puisque les mesures correspondantes sont locales à
chaque système utilisé et qu'alors les classements eux-mêmes peuvent donc être
relatifs à une machine. Seules les mesures effectuées en interne pas notre(nos)
compresseur(s)/décompresseur(s) seront utilisées.
- Un interpréteur C pourrait être utile, mais pour l'être vraiment
il devrait être général et il aurait donc la complexité d'un compilateur,
ce qui n'est donc pas envisageable. L'idée précédente consistant à implémenter
des compteurs est donc de loin beaucoup plus simple,
mais évidemment et malheureusement, elle ne peut s'appliquer qu'aux programmes rédigés par nous-mêmes...
- Le compresseur "NEUTRE", s'il reste utile, doit être
inspiré de "RUN-LENGTH ENCODING 11 (RLE11)"
au niveau de sa programmation.
- Seules des images codant chaque pixel sur un octet seront prises en compte.
- Tenter de segmenter préalablement les images afin de pouvoir ensuite traiter
séparemment des zones ne contenant que des textures statistiquement identiques.
On notera au passage que les deux segmentations utiliséees jusqu'ici
(par la transformée en ondelettes et
grâce à ses plans de bits)
ne fonctionnent pas comme on le souhaiterait car les segmentations ainsi réalisées
reposent finalement sur la luminance et non pas sur la texture.
- Les mesures de K et LD n'incluant aucune subjectivité, les idées de tests
et de concours destinés à "avoir l'avis du public" sont donc à proscrire...
10-Quelques expériences instructives :
Ces expériences portent sur la série d'images suivante :
OBJC.B3A__1_______.11 K=.804088 * LD=1789389747 |--*
OBJC.B3E__1_______.11 K=.799045 * LD=1776846482 |-*
OBJC.B3F__1_______.11 K=.810942 * LD=1776596058 |-*
OBJC.B3G__1_______.11 K=.821938 |* LD=1771624686 |*
OBJC.B3H__1_______.11 K=.809240 * LD=1751128723 *
OBJC.B3I__1_______.11 K=.847082 |--* LD=1756323793 *
OBJC.B3J__1_______.11 K=.869365 |----* LD=1760316575 *
OBJC.B3K__1_______.11 K=.936026 |---------* LD=1800685937 |---*
OBJC.B3L__1_______.11 K=.958678 |----------* LD=1800969284 |---*
OBJC.B3M__1_______.11 K=.998215 |-------------* LD=1818660023 |-----*
OBJC.B3N__1_______.11 K=1016867 |--------------* LD=1817037478 |-----*
OBJC.B3O__1_______.11 K=1021879 |---------------* LD=1805692039 |----*
OBJC.B3P__1_______.11 K=1028775 |---------------* LD=1794936540 |---*
OBJC.B3Q__1_______.11 K=1056061 |-----------------* LD=1796199639 |---*
OBJC.B3R__1_______.11 K=1038618 |----------------* LD=1756676202 *
OBJC.B3S__1_______.11 K=1101469 |---------------------* LD=1778228051 |-*
OBJC.B3T__1_______.11 K=2165098 |---------------------------------------------------------------------------------------------------* LD=2824457374 |---------------------------------------------------------------------------------------------------*
10.02-Mesures avec 'PNG' (CDC=04) seul avec segmentation à l'aide de la dimension fractale locale, sans suppression des zones NOIR masquées :
OBJC.B3A__1_______.11 K=.715174 * LD=.155116538 |--------------------------------------------------*
OBJC.B3E__1_______.11 K=.716650 * LD=.154743776 |-------------------------------------------------*
OBJC.B3F__1_______.11 K=.724219 |* LD=.154423286 |-------------------------------------------------*
OBJC.B3G__1_______.11 K=.732334 |-* LD=.154129705 |------------------------------------------------*
OBJC.B3H__1_______.11 K=.727402 |* LD=.153679807 |-----------------------------------------------*
OBJC.B3I__1_______.11 K=.790946 |----------* LD=.155161434 |--------------------------------------------------*
OBJC.B3J__1_______.11 K=.811555 |-------------* LD=.155437155 |---------------------------------------------------*
OBJC.B3K__1_______.11 K=.875592 |----------------------* LD=.156999748 |------------------------------------------------------*
OBJC.B3L__1_______.11 K=.878583 |-----------------------* LD=.156972901 |------------------------------------------------------*
OBJC.B3M__1_______.11 K=.925977 |------------------------------* LD=.157907057 |--------------------------------------------------------*
OBJC.B3N__1_______.11 K=.936193 |-------------------------------* LD=.158728480 |----------------------------------------------------------*
OBJC.B3O__1_______.11 K=.938197 |--------------------------------* LD=.158805282 |----------------------------------------------------------*
OBJC.B3P__1_______.11 K=.933220 |-------------------------------* LD=.149661311 |---------------------------------------*
OBJC.B3Q__1_______.11 K=.951179 |----------------------------------* LD=.140411925 |-------------------*
OBJC.B3R__1_______.11 K=.943391 |--------------------------------* LD=.140272288 |-------------------*
OBJC.B3S__1_______.11 K=1005532 |------------------------------------------* LD=.130674978 *
OBJC.B3T__1_______.11 K=1388031 |---------------------------------------------------------------------------------------------------* LD=.178091488 |---------------------------------------------------------------------------------------------------*
10.03-Comparaison des performances relatives à la mesure de 'K' entre 'bzip2' (CDC=01) et 'RLE11' (CDC=0C) avec segmentation à l'aide de la dimension fractale locale et suppression des zones NOIR masquées :
'bzip2' 'RLE11'
OBJC.B3A__1_______.11 K=.525469 * K=.885371 *
OBJC.B3E__1_______.11 K=.554616 * K=.885346 *
OBJC.B3F__1_______.11 K=.580057 |----* K=.885296 *
OBJC.B3G__1_______.11 K=.608560 |---------* K=.884955 *
OBJC.B3H__1_______.11 K=.622165 |------------* K=.884951 *
OBJC.B3I__1_______.11 K=.689122 |-------------------------* K=.884950 *
OBJC.B3J__1_______.11 K=.715282 |-------------------------------* K=.893532 |----*
OBJC.B3K__1_______.11 K=.782967 |--------------------------------------------* K=.893532 |----*
OBJC.B3L__1_______.11 K=.795537 |-----------------------------------------------* K=.893526 |----*
OBJC.B3M__1_______.11 K=.849292 |----------------------------------------------------------* K=.937021 |------------------------------*
OBJC.B3N__1_______.11 K=.876124 |---------------------------------------------------------------* K=.937041 |------------------------------*
OBJC.B3O__1_______.11 K=.895712 |-------------------------------------------------------------------* K=.936803 |------------------------------*
OBJC.B3P__1_______.11 K=.908421 |---------------------------------------------------------------------* K=.936704 |------------------------------*
OBJC.B3Q__1_______.11 K=.934075 |---------------------------------------------------------------------------* K=.939802 |--------------------------------*
OBJC.B3R__1_______.11 K=.938791 |---------------------------------------------------------------------------* K=.939697 |--------------------------------*
OBJC.B3S__1_______.11 K=1003400 |----------------------------------------------------------------------------------------* K=1003956 |-----------------------------------------------------------------------*
OBJC.B3T__1_______.11 K=1053655 |---------------------------------------------------------------------------------------------------* K=1048576 |---------------------------------------------------------------------------------------------------*
Ainsi, les performances de 'RLE11' ne sont pas ridicules et de
moins en moins au fur et à mesure que la part d'aléatoire
augmente, jusqu'à être meilleur sur la dernière image
(on notera au passage que cela correspond à un aplatissement de l'histogramme
et donc à un passage de la non-équiparition à l'équiparition).
De plus le K mesuré par 'bzip2' est monotone croissant, alors que
le K mesuré par 'RLE11' varie (croît ou décroît) de façon assez peu logique
lorsque le taux d'aléatoire augmente (cela vient peut-être de la segmentation). On notera
aussi que les images 'B3J' et 'B3K' donnent le même K !
Des expériences faites avec un codeur de Huffman montrent que :
- Avec 128 symboles différents, les codes binaires occupent jusqu'à 8 bits,
- La longueur d'un code binaire est une fonction décroissante de la fréquence du caractère correspondant,
- Lorsque les fréquences sont égales (à epsilon près), les codes binaires ont la même longueur (à 1 bit près).
ce qui laisse supposer que :
- Avec 256 symboles différents, les codes binaires occuperaient jusqu'à 9 bits,
- Si les fréquences sont voisines, alors les codes binaires auront 8 ou 9 bits.
Et c'est ce "8 ou 9 bits" qui expliquerait que le K mesuré par 'bzip2' (=1053655) dépasse 1048576 (=1024x1024),
en notant que :
1 < 1053655/1048576 < 9/8
et ce sans oublier l'arbre de décodage lui-même qui doit occuper plusieurs
centaines d'octets.
Si cela fonctionne beaucoup mieux avec des images synthétiques (telle celle-ci 
),
c'est certainement parce que le réordonnancement des octets avant un RLE que font les CDCs "standards" sont efficaces
et regroupent de nombreux octets identiques, ce qui masque le mauvais codage de Huffman qui suit ce RLE (lorsque
il y a une quasi-équiparition des niveaux)...
Rappelons au passage que les compresseurs
ont été programmés historiquement pour compresser des textes où
d'une part les 256 niveaux ne sont pas tous utilisés (loin s'en faut !) et où ceux qui le
sont n'ont pas la même probabilité d'occurence. Une image n'est
pas un texte...
Ainsi, pour des images à 256 niveaux de gris,
'RLE11' n'est pas un mauvais compresseur, surtout s'il y a quasi-équiparition des niveaux...
11-Quelques histogrammes :
Ces expériences portent sur les séries d'images suivantes :
