La complexité des données est difficile à définir. Cependant, la théorie de la complexité de Kolmogorov définit une suite complexe de symboles comme une suite qui serait incompressible. En principe, cette complexité est impossible à diagnostiquer de manière absolue mais les méthodes pratiques de compression permettent de se faire une bonne idée de la complexité des suites. Ces méthodes peuvent être utilisées, non seulement pour gagner de l’espace sur son disque dur, mais également comme outils d’analyse de complexité des données.
S’il est une notion complexe à définir, c’est bien celle de complexité ! Tentons une définition de la complexité des données qui soit objective, robuste et qui ne soit pas autoréférentielle. Il est usuel d’opposer la « complexité » à la « simplicité ». Ainsi, sont complexes les données… qui ne sont pas simples ! Faisons évoluer cette phrase, digne de Lapalisse, suivant la pensée du philosophe Guillaume d’Ockham (XIVe siècle) : pluralitas non est ponenda sine necessitate ; pensée qui peut être traduite par « les entités ne doivent pas être multipliées sans nécessité ». De cette pensée est né le principe du rasoir d’Ockham : lorsque plusieurs descriptions peuvent modéliser exactement la même chose, la description la plus simple doit être choisie. Ce principe n’est bien entendu pas une règle absolue permettant de choisir la meilleure description, mais plutôt une règle expérimentale permettant de guider le bon sens lorsque des alternatives existent et que l’on désire étudier en priorité celle qui a plus de chance de nous conduire à la bonne solution.
Codage binaire et contenu brut en information
Les données que nous manipulons sont généralement représentées par des suites de caractères. Par exemple, le texte que vous lisez est codé sur l’alphabet latin augmenté des chiffres, des lettres accentuées... La suite des décimales de π est représentée par une suite (infinie) de chiffres. Les chaînes de nucléotides qui composent l'ADN (support de l'information génétique des organismes vivants) sont codées par des suites sur l’alphabet {A,C,G,T} ; ainsi, TGTCCCCAATTA décrit une séquence d’ADN. La suite 10010100101001100101 décrit la suite de 20 tirages binaires (par exemple pile = 0, face = 1), etc. Les suites de caractères sont bien des descriptions des données qu’elles encodent.
Toutefois, dans l’ordinateur, toutes ces suites sont recodées en une suite de bits (suite de symboles de l’alphabet binaire {0,1}). Notons que le bit est, par nature, la plus petite entité capable de coder une information. Pour évaluer le contenu brut en information d’une suite de caractères, il nous faut connaître le nombre de bits nécessaires à son codage, sans réelle transformation, sur {0,1}. Si une suite, de longueur n, est écrite sur un alphabet à m lettres, son contenu brut en information est n log(m)/log(2) bits.
Par exemple, la séquence d’ADN ci-dessus peut être codée en 111011010101010000111100 en convenant de coder chaque caractère sur 2 bits : A par 00, C par 01, G par 10 et T par 11. Son contenu brut en information est de 24 bits. Sachant que toute suite peut être recodée sur l’alphabet binaire, nous nous intéressons ici à la complexité des séquences binaires uniquement.
Compression, régularités et limites
La compression informatique sans perte (l’intégralité de l’information peut être reconstruite par décompression, notion à opposer à la compression avec perte mise en œuvre dans les formats tels que mp3, jpeg...) vise à calculer des descriptions plus courtes des mêmes données. Si une méthode de compression a pu réduire la taille de la description, la nouvelle description obtenue est une meilleure description dans le sens du rasoir d’Ockham. La compression sans perte peut être utilisée pour évaluer la complexité des suites binaires. La suite S = 000000000000000000000000000000 semble « simple » alors que la suite T = 011010011001011010010110011010 semble « complexe ». Dans l’absolu, ces deux suites de 30 bits ont pourtant exactement la même probabilité d’apparition : 1/230 (en supposant que la répartition des bits soit uniforme). Une méthode de compression exploite des redondances pour comprimer. Supposons que le type de redondances utilisé soit les répétitions consécutives d’un symbole. La séquence S se comprime en « 30×0 » (nous faisons ici abstraction du codage de « 30×0 » en binaire). Si une méthode de compression ne parvient pas à comprimer une séquence, on peut conclure que les redondances exploitées par la méthode ne sont pas présentes. La séquence peut être considérée comme « complexe » vis à vis de ce type de redondances. Cela ne signifie pas pour autant que la séquence ne puisse pas être comprimée à l’aide d’une autre méthode ! Mais il peut facilement être démontré que toutes les suites binaires ne sont pas compressibles ! En effet, un simple comptage du nombre de suites plus courtes que l bits montre qu’au moins une des 2l suites de l bits n’est pas compressible.
Complexité de Kolmogorov d’une suite
La théorie de la complexité de Kolmogorov (d’après le nom du mathématicien Andreï Kolmogorov), aussi appelée théorie algorithmique de l’information (voir le document sur la théorie de l'information), définit une suite complexe comme une suite qui ne possède pas de description plus courte. Ainsi, la suite S est « simple » puisqu’elle peut être décrite de manière très courte : « 30×0 », alors qu’il semble difficile, a priori, de trouver une plus courte description de la suite T. Une version comprimée d’une suite peut être vue comme un programme informatique qui reconstruit la suite (exemple : le programme « afficher 30 fois 0 », traduit en binaire). La complexité de Kolmogorov d’une suite x, notée K(x), est la longueur du plus petit programme qui engendre x. Ainsi, une suite est qualifiée de « complexe » si sa longueur est égale à sa complexité de Kolmogorov : il n’est pas possible d’en trouver une plus courte description. Malheureusement, la complexité de Kolmogorov d’une suite n’est pas calculable en général : il n’est pas possible de connaître la plus courte description de toute suite !
Approximation de la complexité de Kolmogorov par les méthodes de compression
Les méthodes de compression tentent donc d’approcher la complexité K(x), c’est-à-dire d’en donner une valeur supérieure, en exploitant au maximum les régularités présentes dans x. Si une version plus courte peut être trouvée, on peut conclure que les données possèdent certaines régularités (celles exploitées par la méthode). Dans le cas contraire, on ne peut pas conclure que les données sont complexes : d’autres régularités cachées pourraient être présentes. Ainsi, la suite T présentée ci-dessus semble a priori incompressible alors qu’elle est en fait très régulière. Il s’agit des 30 premiers bits de la suite de Thue-Morse, obtenue à partir de la suite « 0 » par itérations successives du programme : « remplacer les 0 par 01 et les 1 par 10 ». Elle n’est donc pas complexe au sens de la complexité de Kolmogorov.
Analyse de données par compression
Ainsi, des méthodes de compression peuvent être utilisées pour analyser des données et y repérer des régularités. Par exemple, nous avons développé, dans le Service d’Informatique Théorique de l’Université de Mons, le logiciel STAR (Search for Tandem Approximate Repeat) utilisable, via internet, par la communauté scientifique. Ce logiciel tente de comprimer une séquence d’ADN pour y localiser des répétitions en tandem approximatives d’une petite séquence donnée. Il s’agit de zones qui peuvent être impliquées dans certaines maladies génétiques telles que la maladie de Huntington (maladie d’ordre neurologique à évolution progressive). Les répétitions en tandem approximatives sont les régularités exploitées pour comprimer. Si l’algorithme parvient à comprimer une séquence, on conclut que de telles répétitions sont présentes.
Profondeur logique de Bennett
Une autre notion de complexité d’une suite est associée à la complexité de Kolmogorov. La profondeur logique de Bennett d’une suite est définie par le temps nécessaire à la construction de la suite par le plus court programme. Plus grand est ce temps, plus complexe est la suite.
Pour l’illustrer, prenons le cas précis du calcul des 106 premières décimales de π. La complexité de Kolmogorov de cette suite est très petite puisque π est défini de manière concise comme le rapport entre la circonférence d’un cercle et son diamètre. Il « suffit donc » de considérer le plus court programme qui calcule la suite des décimales de π (que l’on limite aux 106 premiers chiffres). Dans ce cas précis, le temps de calcul est très conséquent. Le fait que l’on choisisse le plus court programme est primordial car sans cela, le programme le plus rapide serait « imprimer -.....- » où -.....- est constitué des caractères de la suite. Cette nouvelle notion met bien en évidence la grande complexité de la suite des décimales de π car, bien qu’il existe des programmes courts pour calculer les décimales, ceux-ci calculent longtemps. Il en est de même pour les objets fractals, souvent faciles à décrire mais longs à calculer. La profondeur de Bennett est donc une nouvelle évaluation de la complexité d’une suite, intimement liée (par le fait que le plus court programme doit être considéré) à la complexité de Kolmogorov.
Mesure probabiliste de Levin
Dans la nature, les objets réguliers sont beaucoup plus présents que les objets complexes : les redondances liées aux symétries diverses et structures répétitives semblent gouverner ce monde. Nous savons que les suites correspondant aux descriptions d’objets réguliers sont mieux compressibles que celles correspondant aux objets complexes. La mesure de Levin m(x) établit la probabilité d’apparition d’une suite x selon la formule : m(x)=1/2K(x). Une suite très régulière x se voit ainsi attribuer une grande probabilité (car K(x) est petit) et une suite complexe une faible probabilité. Selon ce modèle probabiliste, un objet structuré est ainsi beaucoup plus probable qu’un objet complexe. Il s’agit là d’une vision du monde où les objets sont produits par des programmes ou des mécanismes assimilables simples (les descriptions comprimées). Même si cette vision n’est que grossièrement vraie, elle explique le succès des programmes de compression : bien que certaines données concrètes soient très complexes, et donc incompressibles, elles sont rares ! La majorité des données concrètes sont régulières et donc compressibles.
En conclusion, la complexité des suites est déterminée par leurs compressibilités. La compressibilité d’une suite est égale à sa complexité de Kolmogorov. Bien que celle-ci ne soit pas calculable, les méthodes de compression approchent cette complexité. Ces méthodes ne sont donc pas seulement utiles pour gagner de l’espace de stockage, mais également pour analyser la complexité des données. Toutefois, il faut aussi considérer la profondeur de Bennett, liée au temps nécessaire de reconstruction des données. Même si les données sont compressibles, si ce temps est important, les données sont complexes ! Enfin, la mesure de Levin permet d’établir que les données incompressibles sont aussi très rares en pratique.
Quelques références pour en savoir plus.
Une première version de ce document est parue dans le magazine « élément » de l'Université de Mons, n°05, en mars 2011.
Aucun commentaire:
Enregistrer un commentaire