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) ?
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.
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.
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
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.
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.
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
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 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.
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
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.
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.
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
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.
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.
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.
Olivier Masson
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.
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.
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.
Denis Beauregard
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
Le 23 Jan 2009 18:37:46 GMT, Olivier Masson <sisemen@laposte.net>
é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...
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 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
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.
É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
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 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 ?
É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 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.
<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.>
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 ]
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.
<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.>
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 ]
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.
<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.>
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 ]