compression avec caracteres alphanumerique

[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.

[Olivier Miakinen]

Bonjour,

Post by Olivier Masson
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]

Post by Olivier Masson
Bonjour,

Post by Olivier Masson
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.

[Olivier Masson]

Post by Paul
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]

Post by Olivier Miakinen
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.

[Sylvain SF]

Post by 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) ?

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]

Post by Sylvain SF
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.

[Denis Beauregard]

Post by 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) ?

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]

Post by Denis Beauregard
[...]
É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,

[Paul]

Post by Olivier Miakinen

Post by Denis Beauregard
[...]
É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]

Post by Paul

Post by Olivier Miakinen
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à !

;-)

Post by Paul
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.

<cit. http://www.ietf.org/rfc/rfc2045.txt>
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.)
</cit.>

Post by Paul
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 ]

[Sylvain SF]

Post by Paul

Post by Olivier Miakinen

Post by Denis Beauregard
[...]
É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 ?

en moins de 4 pages, la "base 64" utilise 64 symboles codants *plus*
le caractère '=' de mise en forme.
un flux (non un codage) base64 requiert généralement 65 car., c'était,
je pense, le point d'Olivier.

Sylvain.