Compression Ultime !
Posté le 02/02/2016 00:34
Salut les Casionautes
!
Aujourd'hui votre mission si vous l'acceptez est de réussir à
compresser au
maximum les
matrice M et N (elle font 4*20 et comportent des valeurs entre 0 et 9)[/i].
Matrice M
Cliquer pour enrouler
0, 2, 2, 2, 5, 5, 6, 6, 9, 8, 7, 7, 7, 7, 7, 7, 0, 1, 2, 1
7, 7, 7, 8, 8, 9, 6, 5, 2, 1, 0 ,3, 3, 5, 4, 4, 7, 4, 5, 2
0, 5, 8, 8 ,8 ,8, 8, 8, 8, 8, 8, 8, 1, 0, 0, 2, 0, 0 ,4, 6
4, 5, 8, 9, 5 ,6, 5, 4, 2, 1, 4, 5, 3, 6, 5, 8, 1, 2, 6, 6
Matrice N
Cliquer pour enrouler
0, 1, 2, 3, 4, 5, 6 ,7, 8, 9, 0 ,1, 2 ,3 ,4, 5, 6, 7 ,8, 9
9, 8, 7, 6, 5, 4 ,3, 2, 1, 0, 9, 8, 7, 5, 4, 3, 2, 1, 0, 6
0, 0, 1, 1, 2, 2, 3, 3, 4 ,5, 6 ,8, 9, 5, 4 ,8, 5, 2, 3, 1
9, 1, 5, 4 ,8, 9, 5, 8, 4, 0, 4, 4, 0, 0, 0, 1, 5, 6, 9, 5
Une fois ceci fait, vous devez également créer le
décompresseur dans un autre programme qui
stockera les valeurs dans la
matrice A, bien entendu, votre décompresseur devra gérer les 2 matrices
.
Le code compressé des matrices devra être mis dans un sous-programme qui sera appelé par votre décompresseur, pour que je puisse facilement évaluer la taille en octets du code compressé
La taille en octets du décompresseur n'est pas limitée, il peut être énorme ce ne sera pas pris en compte 
!
La vitesse de décompression n'est pas prise en compte, votre programme peut mettre une heure à tout décompresser ce n'est pas grave, du moment que ça fonctionne.
Puis vous m'envoyez votre code, et de mon côté je vérifie les performances avec un programme qui se déroule comme suit :
Lancement du programme "Mat.M-N" qui initialisera la première fois la matrice M (commune à tous les participants).
Lancement de votre programme qui stockera les valeurs dans la matrice A.
Lancement du programme "Comparer" qui comparera les 2 matrices pour voir si elles sont identiques
.
Puis je recommence en initialisant la matrice N
.
Voilà, le concepteur du meilleur code compressé se verra décerner le titre de "
Compressor"
, sur ce, que le meilleur gagne
!
Citer : Posté le 02/02/2016 14:34 | #
On peut faire rentrer les deux matrices en 40 caractères donc une solution finale de 64 octets (24+40*1 pour une Str) est envisageable.
Tu n'as pas précisé si le poids des algorithmes rentrait en compte ou si c'était juste le poids des matrices compressées qui importait.
La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
Citer : Posté le 02/02/2016 18:13 | #
Ah oui pardon je modifie ce qoir dans le post principal ^^' , effectivement quand je demande à avoir 2 programmes séparé, un pour le code compressé et un pour le décompresseur, c'est pour avoir directement les octets du code
Oui après ces matries sont pas trop grandes
Citer : Posté le 02/02/2016 19:41 | #
Ok. J'ai fais quelques tests en TD de physique aujourd'hui. La matrice 21×7 sur laquelle je travaille est générée aléatoirement au début du programme selon la formule Int (10×(Ran# ^x -> Mat A[L, C]. On a donc un prédominance de 0 suivant la valeur de x (dans mes tests, x ∈ {3, 5, 7}).
J'ai compressé les données comme suit :
1) Indexage dans une liste (List 1) de la matrice (ce qui permettra de lier des symboles récurrents sur deux lignes).
2) Groupement par séries de symboles dans deux listes (liste 2 : symbole, liste 3 : nombre d'occurences), avec une limite de 28 occurrences d'affilés.
3) Compression dans une string. Si le nombre d'occurrence du caractère est supérieur ou égal à 3, on met une lettre représentant le nombre d'occurrences (A = 3, …, Z = 28, d'où la limite de 28 caractères par groupe, mais c'est facilement amélioré) puis le caractère. Sinon y'a que le caractère.
4) Affichage du ratio de compression : 100 × (1 - StrLen(Str 1) ÷ Dim List 1)
En moyenne, pour x = 3 je tourne à 20-25% de compression, x = 5 je monte à 25-35%, x = 7 à 35-50%. Mais pour une map créée à la main, donc avec des lignes de tiles (un mur par exemple), j'ai compressé à 80% !
Je vais continuer mes tests
Citer : Posté le 02/02/2016 20:05 | #
Ah tiens j'avais pas pensé à mettre les coefficients de récurrence dans une autre liste teh
80% c'est assez énorme
Citer : Posté le 02/02/2016 22:43 | #
Disons que quand la map ressemble à ceci, ça compresse vraiment fort :
1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1
1 1 1 0 0 0 2 2 0 1 1 1 2 0 0 0 0 0 1 0 1
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 3 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Soit 21×5 = 105 valeurs
Ça donne (sans les espaces oncalc) :
W1 C0 1 C0 B1 B0 B1 A0 2 2 0 A1 2 C0 1 0 A1 K0 1 1 2 3 V1
Soit 35 caractères, donc un ration de compression de 66%. Et encore, c'est une petite map avec pas tant de vide ou de longs murs que ça.