Discussion :

[Tommy31]

Bonjour,

je cherche à déterminer quel serait le meilleur algorithme de compression de chaîne de caractères, sachant que le ratio de compression prime sur l'usage des resources (mémoire, temps).

Pour situer le problème, je cherche à réduire la taille d'un paramètre véhiculé dans une URL. Je ne vais pas détailler le bien fondé de la raison de faire ainsi plutot qu'autrement, surtout qu'il émane plus d'un principe philosophique qu'autre chose.

Les hypothèses sont :
1) En entrée : caractères imprimables, taille de 10 à 50000 caractères, beaucoup de motifs semblables (le type de chaîne ressemble à du SQL pour vous faire une idée)
3) en sortie : une chaîne de caractère (URL compatible).

J'ai besoin d'un fort taux de compression pour limiter les risques de rejet des navigateurs (http://www.boutell.com/newfaq/misc/urllength.html)

Pour l'instant, je procède ainsi :
1) conversion chaîne en tableau de bytes
2) compression Gzip
3) base 64 encodage du résultat

ce qui me permet de passer d'une taille de 17286 à 1796 par exemple. Ca parraît pas mail, mais peut-être existe-t-il un meilleur algo que gzip pour ce domaine bien précis.

Merci

[pseudocode]

Pour situer le problème, je cherche à réduire la taille d'un paramètre véhiculé dans une URL. Je ne vais pas détailler le bien fondé de la raison de faire ainsi plutot qu'autrement, surtout qu'il émane plus d'un principe philosophique qu'autre chose.

Il y a aussi un principe philosophique qui dit qu'en HTTP on utilise la méthode POST pour passer des paramètres de grande taille.

caractères imprimables, taille de 10 à 50000 caractères, beaucoup de motifs semblables (le type de chaîne ressemble à du SQL pour vous faire une idée)

Si les mot-clés de ton langage sont fixés (comme en SQL), tu peux créer un dictionnaire (^S=select, ^W=where, ...). Si en plus la grammaire est fixe, tu peux créer des raccourcis pour des séquences (^X1,2,3 = Select 1 from 2 where 3).

Sinon, dans le cas général je pense que ta méthode "serialization+compression+base64" est ce que tu pourras faire de mieux.

[Jimmy_]

Bonjour,

Gzip est basé sur une combinaison du fameux LZW et d'un codage de Huffman.
Si les éléments possible dans tes url est faible un codage de huffman seul va te permettre de réduire drastiquement la taille de tes urls.
A condition bien sûr d'utiliser un dictionnaire fixe.

Par contre Huffman n’élimine pas les redondances comme LZW.

A tester.

[souviron34]

Une idée comme ça :

Les hypothèses sont :
1) En entrée : caractères imprimables, taille de 10 à 50000 caractères, beaucoup de motifs semblables (le type de chaîne ressemble à du SQL pour vous faire une idée)
3) en sortie : une chaîne de caractère (URL compatible).

J'ai besoin d'un fort taux de compression pour limiter les risques de rejet des navigateurs (http://www.boutell.com/newfaq/misc/urllength.html)
i

Pourquoi déjà ne pas faire un recensement des motifs et déjà faire un truc un peu comme GIF : une table indexée.

Ensuite, appliquer par exemple gzip..

Tu devrais pouvoir obtenir un taux encore plus fort que celui que tu as actuellement, non ?

[Jimmy_]

Sinon GIF utilise l'algo LZW à la base.
Il est conçu pour éliminer les redondances.

Pour une URL où il y a souvent assez peu de redondance, cela ne semble pas être la bonne solution.

[souviron34]

Sinon GIF utilise l'algo LZW à la base.
Il est conçu pour éliminer les redondances.

Pour une URL où il y a souvent assez peu de redondance, cela ne semble pas être la bonne solution.

faut peut-être lire avant de poster :

beaucoup de motifs semblables