Les Newsletters Interstices
    Niveau intermédiaire
    Niveau 2 : Intermédiaire

    Complexité des données et compression informatique

    Données
    Culture & Société
    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.

    Andreï Kolmogorov. Source : Wikipedia

    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.

    Représentation de l’ADN par une double hélice.

    Image : © UNC-CH Center for Bioinformatics

    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.

    Source : Flickr / © gomartin

    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.

    Newsletter

    Recevez chaque mois une sélection d'articles

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Olivier Delgrange

    Chercheur au Service d’Informatique Théorique de la Faculté des Sciences de l'Université de Mons (UMONS) en Belgique.
    Voir le profil