La complexité de l’information d’un point de vue informatique
la complexité de l'information
Les informations peuvent se distinguer selon leur complexité pour le lecteur. Certaines sont simples à comprendre, d’autres plus complexes dans leur appréhension.
Différents travaux ont montré des résultats qui se complètent et permettent d’apporter un éclairage sur l’effet de la complexité.
LA COMPLEXITE DE L’INFORMATION
c'est quoi ?
En s’inspirant de la théorie des probabilités, des statistiques et de la thermodynamique, Shannon introduit le concept d’entropie dans la théorie de l’information (ou théorie de l’information de Shannon). L’idée est de mesurer l’incertitude d’un message transmis. Moins un message est fréquent, plus il faut d’efforts pour le transmettre. L’entropie s’interprète alors comme une mesure du nombre de bits nécessaires pour coder l’information à envoyer.
Shannon adopte clairement un point de vue observationnel (statistique) de l’information et de son contenu.
Même si le point de vue de Shannon resta longtemps le standard de quantification de l’information, une autre idée commença à émerger, la description de l’information comme mesure de complexité. En effet, le lien entre la richesse des informations contenues dans un objet et sa description semble intuitif.
Plus un objet est complexe (i.e. riche en information), plus son explication sera longue. Par la suite, il a été démontré la relation entre la notion de simplicité d’un objet et le petit nombre de symboles pour le décrire.
Cette nouvelle conception de l’information a été initiée par les différents travaux d’Andreï Nikolaïevitch Kolmogorov, Ray Solomonoff et Gregory Chaitin. Ces travaux ont permis le développement d’une nouvelle théorie de l’information, la théorie algorithmique de l’information (AIT).
Pour mettre en œuvre cette théorie, Kolmogorov en 1965 (article), s’est intéressé à la façon dont l’information est générée. Cette nouvelle idée de l’information est communément appelée complexité de Kolmogorov.
La complexité de Kolmogorov est la taille du plus petit programme (algorithme écrit dans un langage de programmation donné) qui génère l’objet (information).
comment mesurer
cette complexité
Comme évoqué précédemment, l’entropie peut fournir une indication de la complexité d’une information, en renvoyant le nombre de bits requis pour coder cette information. Pour mieux comprendre ce concept, prenons un exemple simple, voici deux chaînes de caractères possédants chacune 10 symboles :
S1 : “cqzabrdiok” et S2 : “aaabcddddd”
Avant de pouvoir calculer l’entropie de S1, il faut définir la fréquence d’apparition de chaque symbole, ici 1/10 car tous les symboles de la chaine sont différents, soit :
H(S1) = 10 * (-1/10*log2(1/10)) = 3.32 bits pour chaque symbole de la chaine S1
Enfin pour avoir le nombre de bits requis pour l’ensemble du message (S1), il suffit de multiplier la valeur obtenue par le nombre de symbole du message, soit 33.2 bits.
A noter que si l’on voulait coder ce message il nous faudrait donc 34 bits.
Pour la chaine S2, on définit la fréquence d’apparition de chaque symbole, a = 3/10, b = 1/10, c = 1/10 et d = 5/10.
Le calcul de l’entropie de S2 est le suivant :
H(S2) = (-(3/10*log2(3/10))) +2*(-(1/10*log2(1/10))) +(-(5/10*log2(5/10))) = 1.69 bits pour chaque symbole de la chaine S2, soit 16.9 bits pour la totalité de S2.
On peut donc conclure que la S1 est plus complexe que la chaine S2. Cela s’explique par les répétitions de symbole que l’on peut trouver dans S2, contrairement à S1 qui n’en possède aucunes.
La complexité de Kolmogorov quant à elle n’est pas calculable, mais elle est approchable à l’aide d’algorithme de compression. Pour expliquer ce calcul, prenons un autre exemple, voici 2 fichiers :
Après la compression des fichiers A, on peut constater que le fichier ne prend plus que 2 Go d’espace contrairement au 4 Go au départ. Même constat pour le fichier B sa taille après compression n’est plus que de 800 Mo.
A partir de ces nouvelles informations, on peut calculer, ce que l’on appelle un ratio de compression (à droite de l’image) :
RdC = taille originale du fichier / taille compressée du fichier
On peut donc légitimement en déduire que le fichier A est moins complexe que le fichier B car son ratio de compression est plus important.
