Compression de grands chiffres, ordre de grandeur 256! (superieur à 500 digits)

Signaler
Messages postés
7
Date d'inscription
mercredi 14 mai 2003
Statut
Membre
Dernière intervention
22 octobre 2005
-
Messages postés
146
Date d'inscription
jeudi 22 avril 2004
Statut
Membre
Dernière intervention
8 mars 2008
-
Bonjour à tous,

Je cherche des idées de solutions pour compresser de tres grands nombres, je parle de nombres avec plus de 500 digits, par exemple 256!.

_Si je stocke "bettement" le chiffre sous sa forme decimale j'aurais 1 octet par digit, soit 507 octets.
_Si je stocke ce chiffre en binaire j'arrive à 211 octets.

Possibilité 1 je cherche a utiliser des algos de compressions, le problème c'est que si pars du stockage "bête", j'ai seulement 10 types de digits (0/1/2/3/4/5/6/7/8/9) et donc une forte répétitivité pour chaque digits, je peux donc m'orienter ver du Huffman ou du LZW, et là j'arrive à environ 50% de compression et donc je passe de 500o à 250o, c'est donc mauvais puisque je suis superieur à mon stockage en binaire!!

Possibilité 2 toujours avec les mêmes algos de compression je pars de mon stockage binaire de 211 octets et là c'est la misere car bien sur comme le binaire vient d'un nombre il y a tres peu de répétitivité dans les octets et du coup les algos ne donne rien.

J'ai vraiment besoin d'aide, si vous voulez aider, mais que vous n'avez rien suivis à mon explication, je me ferrais un plaisir de réexpliquer autrement.

Merci.

7 réponses

Messages postés
65
Date d'inscription
dimanche 27 juillet 2003
Statut
Membre
Dernière intervention
21 avril 2006

La zlib ne serait-elle pas suffisante ?
Messages postés
7
Date d'inscription
mercredi 14 mai 2003
Statut
Membre
Dernière intervention
22 octobre 2005

Merci Kortin, mais même si zlib permet un tres bon taux de compression ça ne maidera pas beaucoup, je vais essayer de reformuler un peu mon problème, en fait le fichier que je souhaite compresser et équivalent à une suite binaire de 1688 bits aleatoire de 0 ou de 1 (soit 211 octets)

Les problèmes sont que: le fichier est tres petit et a un tres faible taux de répétitivité.
Messages postés
146
Date d'inscription
jeudi 22 avril 2004
Statut
Membre
Dernière intervention
8 mars 2008
2
salut,

je pense que tu peux laisser tomber lzw, le mieux c'est d'utiliser huffman en optimisé a ton utilisation :

comme tu n'as que dix symboles possible pour chaque digit, je te conseille d'utiliser le meme principe qu'huffman

c'est a dire que le symbole le plus utilisé sera codé sur deux bits "00", le suivant sur "010" etc...

reporte toi à un tuto d'huffman poutr plus de précision.

déja ça era bien compressé, mais la plus grosse par a gagner se trouve dans l'en tete de la compression d'huffman...

en gros un simmple entete listant les dix symbole un par un en mode binaire te permet d'economiser de la place :

soit 4bits pour stocker chaque chiffre donc 10*4 = 40 bits soit 5 octect comme catalogue qui te permet de décompresser !



si tu piges pas ma facon de voir les choses, regarde bien la facon dont
est stocké l'en tete d'huffman et tu verras que c'est optimisable dans
ton cas d'utilisation...



@++
Messages postés
7
Date d'inscription
mercredi 14 mai 2003
Statut
Membre
Dernière intervention
22 octobre 2005

Merci MrdJack, ça fais plaisir de voir que quelqu'un a exactement compris mon probleme, et arrrive à la même optimisation que moi, je connais bien huffman et je suis d'accord avec toi pour l'entete de 5o.

MAIS là ou tu n'as pas suivis le soucis c'est que avec le meilleurs des huffman tu passe de ce que j'appel la possibilité 1 de 507 octet à environ une compression "entre" 180o et 250o, ce qui est tres bon,

MAIS moi je souhaite essayer de partir de la possibilité 2 le nombre de 507 digit est d'abord mis en bianire (en tant que nombre pas en tant que suite de chiffre) et là il prends d'éja plus que 211 octet. et c'est sur ce fihier de 211o que je souhaite faire une reduction de l'odre de 50% (je sais je suis gourmand)

Je vais essayé de faire un exemple complet de mon soucis et de le mettre quelque part
Messages postés
341
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
17 juin 2008
2
ton problème me parait insoluble: faire une réduction de 50% sur un
fichier de 211 octet est utopique, les compression marchent parce qu'il
y a répétitivité ou que le fichier est gros . d'ailleurs 211 octets ne
me paraissent pas trop sxauf si c'est un point très critique de ton
applciation . Précise pourquoi tu veux autant compresser ces nombres .

A m a u r y
Messages postés
7
Date d'inscription
mercredi 14 mai 2003
Statut
Membre
Dernière intervention
22 octobre 2005

Bonne question, pourqoui je veut compresser 211 octets, bah en fait j'ai plein de series de 211 octets à compresser, et là tu vas me dire qu'il faut les grouper !, et c'est surement vrai mais dans le principe ca m'arrange pas...
Bon bref merci pour les conseils, mais Amaury à raison compresser 211o seuls qui n'on pas ou peu de répétitivité c'est pas gagné! je vais reprendre mon algo differemment pour faire des groupes plus long.
Messages postés
146
Date d'inscription
jeudi 22 avril 2004
Statut
Membre
Dernière intervention
8 mars 2008
2
pourquoi pas décomposer en facteurs ?
je n'ai pas essayé mais ca pourrai etre une solution...