This post repeats in english.

——————————-

Avant propos: ceci est un essai basé sur des réflexions faites le midi, entre 12h et 12h15, dans le metro, dans mon sommeil, etc… Merci d’en prendre compte à la lecture…

Je reviens sur cet algorithme que j’ai proposé dans un article précédent: ‘cheating with entropy’ (http://crearty.fr/djarwood/blog/?p=30). Il m’a beaucoup fait réfléchir.

Il n’est pas si évident de donner une interprétation du résultat. En effet, comment une information à forte entropie peut-elle être largement compressée alors que, selon la théorie de l’information de Claude Shannon, son entropie prétendrait le contraire ? Cette décorrélation entre complexité et taux de compression est plutôt surprenante.

Revenons un peu sur l’algorithme. Nous établissons une fonction de hachage qui donne une signature du message. La fonction est choisie de telle façon à ce que l’indice de collision du message X à compresser soit raisonnablement petit. Deux choses déterminent la taille du message compressé: la taille de l’indice, et la taille du code de la fonction de hachage.

La question qui se pose est: est-il possible de compresser toute sorte de message avec cet algorithme ? Et dans le cas où le procédé ne ferait pas gagner de place, que dire de ce message, que dire du sens de son entropie ? Selon moi, c’est une piste intéressante.

L’algorithme, bien qu’inapplicable, reste intéressant dans la mesure où il met en lumière le fait qu’il serait nécessaire d’apporter la rectification suivante à la théorie de l’information de Claude Shannon.

On ne peut pas limiter l’étude de l’information à la seule mesure de l’entropie car celle-ci ne fait pas la distinction entre la complexité qui règne au sein d’une donnée complexe et une autre information purement aléatoire, qui est, certes, complexe.

L’information, selon moi, aurait ainsi deux caractéristiques: son ‘sens’ (ou son intelligibilité, dans le sens où une personne, par le biais de son intelligence peut comprendre quelque chose de cette information) et sa ‘complexité’.

Sa complexité est donnée par la formule de l’entropie de Shannon, et son ‘sens’ serait donné par la plus petite taille d’index de collision que l’on peut obtenir avec mon algorithme. Si l’entropie donne la complexité d’une information, le ‘sens’ est une mesure, de l’intelligibilité d’une information, et rejoint d’une certaine manière l’idée de complexité de Kolmogorov, soit la taille du plus petit programme qui peut engendrer la donnée x.

Ce qu’il est intéressant de constater, c’est qu’il existe des données dont la valeur du ‘sens’ dépasse la taille de la donnée en elle-même. Cette donnée, donc ce nombre, a une caractéristique qu’il serait intéressant de distinguer; selon moi, ces nombres ne peuvent qu’être purement aléatoires, dénués d’origine déterministe. Enfin, je dirais que ces nombres seraient, quoique l’on en fasse, dénués de ‘sens’, mais surtout, incompressibles.

J’en déduit donc ma définition du hasard:

« Une information est dite aléatoire si la taille de son ‘sens’ est supérieur ou égal à sa propre taille. »

Définitions additionnelles:

Soit une information x avec un ‘sens’ S.

* Dans un espace donné, une information x véritablement aléatoire ne peut être localisée avec précision qu’avec une autre information (differente) de taille supérieure à celle de x.

* Si S est supérieur à la taille de x, alors on est certain que la donnée n’a aucun sens et qu’elle ne peut avoir qu’une origine purement aléatoire. Exemple: un nombre généré avec un générateur aléatoire quantique, ou bien ce même nombre encrypté avec n’importe quel algorithme.

* Si S est inférieur à la taille de x, alors la donnée a été générée par un phénomène déterministe et peut avoir une signification ou bien est une agrégation d’informations qui ont du sens. Exemple: le code de l’ADN humain représenté en binaire, une musique en format MP3, un nombre généré par un générateur pseudo aléatoire, un fichier texte encrypté, etc…

* Le gain d’un message compressé est fortement corrélé au non voisinage d’un nombre purement aléatoire. Ainsi, il n’est pas rentable de dire que « la donnée aléatoire est au n-ième rang après tel message très compressible ».

Enfin et pour conclure, je dirais qu’il n’existe, au voisinage de l’infini, qu’une infime partie de nombres qui ont du ‘sens’, et dans une certaine mesure, c’est peut être ça la limite de l’infini.

Merci d’avoir lu ceci jusqu’au bout !

——————————-

English:

Foreword: This is an essay based on notes I wrote some days between twelve o’clock and quarter past twelve, in the subway, while sleeping, etc. Please keep this in mind when reading what follows…

I return to this algorithm I proposed on a previous post ‘cheating with entropy’ (http://crearty.fr/djarwood/blog/?p=30), I have been thinking about this for days.

It is not that obvious to give a right interpretation of the result. Indeed, how an information with an high entropy can widely be compressed whereas, according to Claude Shannon’s information theory, its entropy pretends the opposite? This decorelation between complexity and compression ratio of an information is suprising.

Let’s come back a little to the algorithm. We establish a hashing function which gives a signature of a message X to compress. The hashing function is chosen so that the collision index is reasonably small. Two things give the size of the final compressed message: the index’s size, and the size of the hash function’s code.

The question is: is it possible (theoretically) to compress all kind of messages with this algorithm? And if in the case the process doesn’t makes us gain space, what can we say of the message X? What is the meaning of its entropy? To me, this is an interesting question.

The algorithm, although not applicable, stays interesting because it shows that there might be a rectification to bring to Claude Shannon’s information’s theory.

We can not limit the study of information to the simple measure of entropy because this one doesn’t make a distinction between complexity within an information and another information, purely random, which is, certainly, complex.

Information, to me, has two characteristics: its ‘meaning’ (or intelligibility, in the sense that someone can understand this information) AND its ‘complexity’.

‘Complexity’ is given by Claude Shannon’s entropy formula, and its ‘meaning’ would be given by the smallest collision index’s size provided by my algorithm. If the entropy gives the complexity of an information, the ‘meaning’ is a measure of the intelligibility of an information. It joins somehow the idea of Kolmogorov’s complexity, which is the smallest program’s size which can generate the data X.

The most interesting thing we can note is that it exist data having a ‘meaning’s size greater than the size of the data X. This data, or number, have a characteristic we can distinguish; according to me, those numbers can only be purely random, without any deterministic origins. Those numbers would be, whatever we do, meaningless, and overall, incompressible.

Thus, I deduce my own definition of randomness:

« An information is random if the size of its ‘meaning’ is greater or equal its own size »

Additional definitions:

Given an information X, with a ‘meaning’ S.

* In a given space, an information X truly random can only be localized with precision with another different information sized greater than X.

* If S’s size is greater than X one, then we can be certain that the data has no meaning, and can only be randomly generated. Exemple: a number randomly generated with a quantic generator, or this number encrypted by any encryption algorithm.

* If S’s size is smaller than X one, then the data has been generated by a deterministic phenomenon, and has a meaning or is an aggregation of information having meanings. Example: a human’s DNA represented in binary form, a music in MP3 format, a pseudo random number, an encrypted text file, etc.

* The gain of a compressed message is correlated with the neighborhood of a purely random number. Thus, you can’t gain space by saying: « The random information is the nth one after a very compressible Y message ».

To conclude, I would say that on infinite’s neighborhood, there is a fractional count of numbers having a ‘meaning’, and that is, in certain way, the limit of the infinite.

Thank you for reading this essay !