———- This post repeats in english ——————-

Bonjour à tous !

Je viens de me souvenir d’un algorithme que j’ai inventé à la fac, je me permets de le partager avec vous car je trouve que c’est un bon exercice de l’esprit et j’ai l’espoir que vous le trouverez intéressant.

N’importe quel grand fan de compression de données se frotte à l’entropie (au sens de Claude Shannon), cette mesure de l’ordre et du désordre d’une information. Il s’agit d’une mesure fort intéressante qui permet de donner la limite théorique que l’on peut atteindre en moyenne pour compresser une donnée. Je me suis beaucoup intéressé à ces problèmes, mais c’était il y a un certain nombre d’années, vous pardonnerez l’imprécision de mon discours. Toutefois, j’ai quelque chose à vous mettre sous la dent qui à l’époque, me faisait penser que cette mesure était à remettre en question.

L’algorithme que je propose est un algorithme purement théorique, totalement inapplicable excepté par le biais d’un calculateur quantique. Je soupçonne par ailleurs qu’il soit tout à fait adapté à cette problématique, mais c’est un autre débat.

Je pense que tout le monde peut comprendre le principe que voici :

Algorithme de compression:

1. Calculer le hash d’une donnée de, disons, 4Go (nommée D) que l’on veut compresser.

2. Prendre toutes les combinaisons de données de 4Go, et pour chaque donnée, calculer le hash de cette donnée.

3. Avec tous les hashs calculés (nombre qui, je l’admets, dépasse peut être le nombre d’atomes dans l’univers), identifier le sous ensemble E de ceux qui sont égaux au hash de la donnée D.

4. Dans le sous ensemble E, trouver l’indice ‘idx’ de la donnée D. Noter cet indice.

5. La donnée compressée se résume à {taille(D), hash(D), idx}. Soit potentiellement 4 octets pour stocker la taille, 128 bits pour le hash, et un entier d’une taille variable.

A l’époque, je trouvais cette algorithme très puissant et intéressant… En quelque sortes, on transforme la complexité spatiale en complexité temporelle… Potentiellement, on peut ainsi compresser tous les textes écrits par l’humanité en quelques kilo octets… avec un peu de chance, car l’algorithme n’est pas rentable dans tous les cas (l’index de la collision pouvant atteindre la taille du message).

Pour décompresser, c’est assez… bien… disons… laborieux. Mais possible !

Algorithme de décompression:

1. En admettant qu’on ait {taille(D), hash(D), idx}

2. Générer tous les messages de taille taille(D), et pour chacun calculer le hash de cette donnée.

3. Si le hash est égal à hash(D), incrémenter count et tester si count = idx.

4. S’arrêter quand count est égal à idx, vous avez la donnée D originale.

Voila.

Ahh, les années fac 😉

———————– English ————————-

Hi all,

I just remember an algorithm I invented during my studies at the university, as I think it is a good mind game, I take the liberty to present it to you. I hope you will have fun reading what  follows.

Everyone who had to put hands in data compression has heard about Entropy, measure of the complexity of an information. I remember thinking on that theory hours and hours while going back home… Thanks to this theory, you can determine the mean compression ratio you can obtain on a given data, according to its complexity.

I had a lot a fun with those formulas, but it was a long time ago, so please excuse my inaccurate speech.

The algorithm I show bellow is purely theoretical, completely incalculable except by using a quantic super computer. By the way, I suspect this algorithm to fit exactly for this kind of problematic.

The algorithm is very easy to understand.

Compression algorithm:

1. Compute the hash value of data D sized of a certain size (let’s say 4Go) that we want to compress.

2. Compute each combination of data of size 4Go, and for each data keep its hash.

3. With all computed hash values (number, which I admit, can exceed the number of atoms in the universe), identify the subset E of data that has the same hash value than hash(D).

4. In the subset E, find the index ‘idx’ of the data D. Keep this index.

5. The compressed data in defined as {sizeof(D), hash(D), idx}. Potentially 8 bytes to store sizeof(D), 128 bits for the hash(D), and an integer of an arbitrary size.

At the time I invented this algorithm, It was making me dreaming. In some ways, you convert the spatial complexity into a temporal complexity… Potentially, you can compress all the humanity written documents into a small kilo byte !

With a little of luck, I admit, because you can easily understand that the index idx can be very huge. But hash functions are done keeping in mind you want a good collision distribution…

Decompression algorithm:

To decompress the data, well, it’s a lot of work for a computer, but it is possible:

1. Say we have {sizeof(D), hash(D), idx}

2. Generate all data of size sizeof(D), and for each one, compute the hash of this value.

3. If the hash equals hash(D), increment count and test if count = idx.

4. When count equals idx, you have the original D !

I will always remember those good thinking instants at the university !