Exemple simple, tu veux compresser le nombre 100.
100=×ばつ22
Il te faut donc coder un 5 et trois 2 (en plus des informations sur la façon de les agencer), soit dans le meilleur des cas 3 bits pour le 5 et 2 bits pour chaque 2, soit 9 bits. Or, 8 bits suffisent pour coder 100.
De façon générale, un algorithme de compression sans pertes (compactage ?) doit se baser sur les propriétés des données à compresser. Par exemple, un fichier texte contient plus de e que de ®. Mais de façon générale, un tel algorithme est une bijection. L'ensemble d'arrivée (l'ensemble des programmes compactés) et l'ensemble de départ (l'ensemble des programmes non compactés) doivent faire la même taille. En moyenne, un programme compacté, s'il est constitué d'octets aléatoires, fera donc la même taille qu'un programme qui ne l'est pas. Simplement, comme les programmes ont certaines propriétés, on arrive à faire pencher la balance d'un côté plutôt que de l'autre.
[^] # Re: Un nouvel algo de compression ?
Posté par Jar Jar Binks . En réponse à la dépêche Un nombre premier exécutable ... illégal ?. Évalué à 2.
Exemple simple, tu veux compresser le nombre 100.
100=×ばつ22
Il te faut donc coder un 5 et trois 2 (en plus des informations sur la façon de les agencer), soit dans le meilleur des cas 3 bits pour le 5 et 2 bits pour chaque 2, soit 9 bits. Or, 8 bits suffisent pour coder 100.
De façon générale, un algorithme de compression sans pertes (compactage ?) doit se baser sur les propriétés des données à compresser. Par exemple, un fichier texte contient plus de e que de ®. Mais de façon générale, un tel algorithme est une bijection. L'ensemble d'arrivée (l'ensemble des programmes compactés) et l'ensemble de départ (l'ensemble des programmes non compactés) doivent faire la même taille. En moyenne, un programme compacté, s'il est constitué d'octets aléatoires, fera donc la même taille qu'un programme qui ne l'est pas. Simplement, comme les programmes ont certaines propriétés, on arrive à faire pencher la balance d'un côté plutôt que de l'autre.
Juste mes deux centimes d'euros.