Il y a longtemps, j'ai lu un article de journal dans lequel un professeur avait déclaré qu'il serait possible à l'avenir de compresser des données en deux bits (ou quelque chose du genre).
Ceci n’est bien sûr pas correct (et il se pourrait que ma mémoire de ce qu’il a dit n’est pas exacte). Naturellement, il ne serait pas pratique de compresser une chaîne de 0 et de 1 en deux bits, car (même si cela était techniquement possible), trop de types de chaînes différents finiraient par être compressés en deux bits identiques (car nous n'avons que '01 'et' 10 'à choisir).
Quoi qu'il en soit, cela m'a amené à réfléchir à la possibilité de compresser une chaîne de longueur arbitraire de 0 et de 1 selon un schéma. Pour ce type de chaîne, existe-t-il une relation connue entre la longueur de la chaîne (le rapport entre 0 et 1 importe peu) et la compression maximale?
En d'autres termes, existe-t-il un moyen de déterminer quelle est la longueur minimale (la plus petite possible) à laquelle une chaîne de 0 et de 1 peut être compressée?
(Ici, je suis intéressé par la compression mathématique maximale, et non par ce qui est techniquement possible.)
la source
Réponses:
La complexité de Kolmogorov est une approche pour formaliser cela mathématiquement. Malheureusement, calculer la complexité de Kolmogorov d'une chaîne est un problème non calculable. Voir aussi: Approximation de la complexité de Kolmogorov .
Il est possible d'obtenir de meilleurs résultats si vous analysez la source de la chaîne plutôt que la chaîne elle-même . En d'autres termes, la source peut souvent être modélisée comme un processus probabiliste, qui choisit de manière aléatoire une chaîne de caractères, en fonction d'une distribution donnée. L'entropie de cette distribution vous indique alors la meilleure compression mathématiquement possible (jusqu'à une petite constante additive).
Sur l'impossibilité d'une compression parfaite, vous pourriez également être intéressé par ce qui suit.
la source
Pour toute chaîne donnée, il existe un schéma de compression qui le compresse en chaîne vide. Par conséquent, il n’est pas utile de demander dans quelle mesure une seule chaîne peut être compressée, mais plutôt dans quelle mesure une collection (ou distribution ) de chaînes peut être compressée, en moyenne. En général, étant donné une collection de chaînes, tout schéma de compression nécessite au moins bits ou plus pour coder une chaîne de la collection dans le pire des cas.log 2 NN log2N
En outre, dans de nombreux cas, nous ne nous soucions pas de la reconstruction exacte . C'est ce qu'on appelle la compression avec perte , et c'est comment la musique et les vidéos sont compressées. Dans ce cas, la limite inférieure indiquée ci-dessus ne tient pas, mais vous pouvez trouver d'autres limites inférieures.
la source
Voici un schéma simple capable de compresser des chaînes de bits arbitraires sans perte, avec le plus petit résultat obtenu: un bit:
SI la chaîne correspond de manière identique à l'enregistrement de la 9ème symphonie de Beethoven, quatrième mouvement, au format AAC stocké sur le disque dur de mon ordinateur, la sortie est alors un bit 0.
SI la chaîne est autre chose, alors la sortie est un seul bit '1' suivi d'une copie identique de la chaîne d'origine.
Ce schéma réduit une entrée possible à un bit exactement et augmente la longueur de chaque entrée. Il existe un principe général: si un algorithme de compression peut mapper n’importe quelle chaîne d’entrée sur une chaîne compressée et qu’un algorithme de décompression correspondant mappe toute chaîne compressée sur la chaîne d’origine, et que l’algorithme de compression mappe toute entrée sur une chaîne plus courte, il doit mapper des chaînes d'entrée à des chaînes plus longues.
la source
Pour chaque schéma de compression que vous pouvez créer, il est possible de produire des données qui ne seront pas compressibles. Ainsi, même si votre schéma de compression est très efficace avec certains types de données, il ne sera jamais compressé systématiquement selon un certain rapport.
La manière de produire un exemple de données non compressibles pour un algorithme de compression particulier est simple: prenez n'importe quel type de données et passez-les à plusieurs reprises dans l'algorithme de compression jusqu'à ce que la taille ne diminue plus.
Ainsi, la compressibilité d'une chaîne de bits n'est pas vraiment fonction de la longueur de la chaîne, mais de sa complexité par rapport à l'algorithme de compression.
la source
Il existe un algorithme intéressant et complètement différent utilisé par les systèmes de sauvegarde d’entreprise. L'idée est que si vous avez une entreprise avec 10 000 ordinateurs, beaucoup de ces ordinateurs contiendront beaucoup de fichiers identiques. Par exemple, un courrier électronique envoyé à tous les membres de l'entreprise peut se retrouver sous la forme d'un fichier identique sur chaque disque dur.
Donc, un système de sauvegarde essayant de sauvegarder un fichier doit évidemment essayer de compresser le fichier pour économiser de l'espace, mais le système de sauvegarde vérifie d'abord si un fichier absolument identique est déjà enregistré! Ainsi, au lieu de sauvegarder quoi que ce soit , le système de sauvegarde ne fait tout simplement que rappeler par exemple que vous avez le numéro de fichier 1 487 578 sur le système de sauvegarde de votre disque dur.
Ceci est particulièrement efficace, par exemple, lorsque 10 000 utilisateurs ont tous le même système d'exploitation et les mêmes applications installées. Pour les utilisateurs individuels, ce n'est pas très utile du tout.
la source