compression avec caracteres alphanumerique

Le
Olivier Masson
Bonjour,

Connaissez-vous une implémentation en php d'une algo de compression
n'utilisant que les caractères [0-9a-zA-Z], sans entête ni crc (le but
étant de compresser des chaines de 200 à 500 caractères) ?


Merci.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Olivier Miakinen
Le #18469241
Bonjour,

Le 23/01/2009 19:37, Olivier Masson a écrit :

Connaissez-vous une implémentation en php d'une algo de compression
n'utilisant que les caractères [0-9a-zA-Z], sans entête ni crc (le but
étant de compresser des chaines de 200 à 500 caractères) ?



Tout d'abord : non, je n'en connais pas.

Cela dit, pourquoi limiter tes recherches à PHP pour un algorithme ? Tu
aurais beaucoup plus de chances d'avoir des réponses sur un groupe tel
que fr.comp.algorithmes, et quel que soit l'algo il sera alors facile de
le traduire en PHP.
Paul
Le #18471511
Olivier Miakinen a écrit :
Bonjour,

Le 23/01/2009 19:37, Olivier Masson a écrit :
Connaissez-vous une implémentation en php d'une algo de compression
n'utilisant que les caractères [0-9a-zA-Z], sans entête ni crc (le but
étant de compresser des chaines de 200 à 500 caractères) ?



Tout d'abord : non, je n'en connais pas.



Moi si : c'est UUencode, UUdecode. Idée de base (due à un étudiant en
stage, paraît-il) : si un caractère occupe un octet, et que la
transmission n'accepte que 7 bits, voire 6, alors codons 3 octets
successifs (24 bits) sur 4 fois 6 bits ; nous pouvons être alors sûrs de
transmettre sans déformation. Bien sûr cela ne "compresse" pas le
fichier initial ! Mais rien n'empêche de coder ainsi un fichier
préalablement compressé.
J'eqça.
Sylvain SF
Le #18471521
Olivier Masson a écrit :
Bonjour,

Connaissez-vous une implémentation en php d'une algo de compression
n'utilisant que les caractères [0-9a-zA-Z], sans entête ni crc (le but
étant de compresser des chaines de 200 à 500 caractères) ?



aucun algo de _compression_ n'a de bonne raison de se contraindre
à utiliser un tel jeu de caractères en sortie.
la réponse est donc, sauf ignorance, non.

par contre la sortie de n'importe algo de compression peut être
encodé en base64, si vous acceptez + / et = en plus du jeu cité.
base64 convertit 3 octets en 4 caractères donc le message grossira
d'un tiers mais s'il a été très fortement compressé cela peut être
gagnant.

Sylvain.
Olivier Masson
Le #18513901
Paul a écrit :

Moi si : c'est UUencode, UUdecode. Idée de base (due à un étudiant en
stage, paraît-il) : si un caractère occupe un octet, et que la
transmission n'accepte que 7 bits, voire 6, alors codons 3 octets
successifs (24 bits) sur 4 fois 6 bits ; nous pouvons être alors sûrs de
transmettre sans déformation. Bien sûr cela ne "compresse" pas le
fichier initial ! Mais rien n'empêche de coder ainsi un fichier
préalablement compressé.
J'eqça.



(ah, le courant est enfin revenu :))
Non, UU utilise des caractères imprimables, certes, mais pas seulement
dans l'intervalle que je peux utiliser.
Olivier Masson
Le #18513921
Sylvain SF a écrit :

aucun algo de _compression_ n'a de bonne raison de se contraindre
à utiliser un tel jeu de caractères en sortie.
la réponse est donc, sauf ignorance, non.

par contre la sortie de n'importe algo de compression peut être
encodé en base64, si vous acceptez + / et = en plus du jeu cité.
base64 convertit 3 octets en 4 caractères donc le message grossira
d'un tiers mais s'il a été très fortement compressé cela peut être
gagnant.

Sylvain.



Bonne idée ! Et super efficace *dans mon cas* puisque ma conversion
pourrie (utf8 -> entités -> on simplifie quelques motifs que l'on
trouve) utilise 261 caractères et gzcompress 9 + base64 n'en prend que 161 !

Hors de mon contexte particulier (le but était de faire passer du texte
en utf-8 dans un champs qui n'accepte que de l'alphanumérique), on
commence à gagner en général vers 350 caractères.

Le top, merci.
Olivier Masson
Le #18513931
Olivier Miakinen a écrit :

Tout d'abord : non, je n'en connais pas.

Cela dit, pourquoi limiter tes recherches à PHP pour un algorithme ? Tu
aurais beaucoup plus de chances d'avoir des réponses sur un groupe tel
que fr.comp.algorithmes, et quel que soit l'algo il sera alors facile de
le traduire en PHP.



Parce que je n'y ai pas pensé (enfin si, mais comme je suis souvent
bête, j'ai cherché un groupe sur la compression :))
Et puis j'avais un impératif de temps... que l'on relative quand une
tempête nous tombe sur le tronche.
Denis Beauregard
Le #18517581
Le 23 Jan 2009 18:37:46 GMT, Olivier Masson écrivait dans fr.comp.lang.php:

Bonjour,

Connaissez-vous une implémentation en php d'une algo de compression
n'utilisant que les caractères [0-9a-zA-Z], sans entête ni crc (le but
étant de compresser des chaines de 200 à 500 caractères) ?



Si on a du texte en français (ou sans doute n'importe quel en alphabet
latin et probablement d'autres similaires), un bon algorithme de
compression consiste à trier les caractères selon leur fréquence, puis
d'encoder ces caractères en n-tuplets.

Par exemple, le e devient 10 et l'espace, 11, les autres caractères
débutant par 0, et on a une série continue de 1 et de 0. Disons
qu'on a 001, 010, 000 et 011 pour 4 autres lettres, on obtient une
séquence comme 01010100101101010101010101011010010101010 que l'on
coupe en tranches de 6, pour un équivalent de tronquer en base 64.

Plus un caractère est moins fréquent, plus il occupe de bits.

On peut encoder au début de la chaîne les caractères dans l'ordre de
décompression (en base 64), à moins d'utiliser toujours la même
table de décompression pour toute la base (ce qui devrait être plus
efficace car on n'a plus à recalculer la fréquence dans chaque
chaîne).

Pour décoder, on reprendra à partir du début (il faut être synchro
pour décoder) et on décodera selon le nombre de bits par caractère.

Je pense qu'on doit trouver quelque part un bon de code pour
tester cet algorithme.

Évidemment, si c'est une image, l'algorithme ne donne rien. De
plus, en base 64, cela demande 64 caractères et non les 62 que tu
demandes...


Denis
Olivier Miakinen
Le #18518971
Le 28/01/2009 23:46, Denis Beauregard a écrit :

[...]

Évidemment, si c'est une image, l'algorithme ne donne rien. De
plus, en base 64, cela demande 64 caractères et non les 62 que tu
demandes...



Juste histoire de chipoter : en base 64, on a besoin de 65 caractères et
non 64, sans compter d'éventuels espaces et sauts de ligne si on veut
formater le résultat comme on fait d'habitude dans les courriels.

Cordialement,
--
Olivier Miakinen
Paul
Le #18521661
Olivier Miakinen a écrit :
Le 28/01/2009 23:46, Denis Beauregard a écrit :
[...]

Évidemment, si c'est une image, l'algorithme ne donne rien. De
plus, en base 64, cela demande 64 caractères et non les 62 que tu
demandes...



Juste histoire de chipoter : en base 64, on a besoin de 65 caractères et
non 64, sans compter d'éventuels espaces et sauts de ligne si on veut
formater le résultat comme on fait d'habitude dans les courriels.


Ah bon ? le prof de maths que je suis se réveille, là ! pour coder en
bas b, les "chiffres" sont au nombre de b (0 à b-1) restes possibles de
la division du nombre à coder par le nombre b.... Olivier, tu me f'ras 4
pages là dessus pour demain ?
Olivier Miakinen
Le #18523481
Le 29/01/2009 12:33, Paul m'a répondu :

Juste histoire de chipoter : en base 64, on a besoin de 65 caractères et
non 64, sans compter d'éventuels espaces et sauts de ligne si on veut
formater le résultat comme on fait d'habitude dans les courriels.



Ah bon ? le prof de maths que je suis se réveille, là !



;-)

pour coder en
base b, les "chiffres" sont au nombre de b (0 à b-1) restes possibles de
la division du nombre à coder par le nombre b...



Absolument d'accord. Donc 64 caractères pour 6 bits, plus un de padding
(le « = ») ce qui fait bien 65.

6.8. Base64 Content-Transfer-Encoding
[...]
A 65-character subset of US-ASCII is used, enabling 6 bits to be
represented per printable character. (The extra 65th character, "=",
is used to signify a special processing function.)

Olivier, tu me f'ras 4 pages là dessus pour demain ?



Je te laisse le soin de recopier 100 fois l'égalité suivante :
2^6 + 1 = 65
(ça fera bien 4 pages)

[ je propose un suivi en privé, car je ne sais pas où la suite de
cette discussion pourrait être en charte ]
Publicité
Poster une réponse
Anonyme