Discussion :

[SCalc]

Bonjour,

quelqu'un connaitrait-il un "bon" algorithme de compression de fichiers texte (en francais) courts (~ 5 Ko). Sur ce genre de petits fichiers, gzip/winzip ne compresse que d'un facteur 2 (alors que ca atteint 90% sur des gros fichiers texte). bzip2 ne fait guere mieux (55%).

Merci

Jerome

[progfou]

Le meilleur à ma connaissance, c'est Huffman (enfin, sa variante) utilisé entre autres dans le fameux winzip et co.
Winrar ne fait pas mieux ?
As-tu possibilité de fournir le fichier texte ?

Edit: Il y a une borne théorique au taux de compression qui peut être atteint, c'est l'entropie.
Si tu la calcules sur le fichier, tu sauras combien tu peux espérer si tout est parfait dans le meilleur des mondes ^^.

[fumidu]

Je ne suis pas un spécialiste, donc prends ce que je dis avec des pincettes...

En gros, c'est normal que sur des petits fichiers textes le taux de compression soit inférieur : Ces algos sont basés sur des dictionnaires. Or, en prenant un texte 10 fois plus long, on ne multiplie pas le nombre de mots par 10, mais par moins que ça. La taille du dictionnaire à coder est donc toujours plus ou moins la même. Ainsi, à l'extrême, un texte avec une seule occurrence de chaque mot ne sera pas compressible car la taille du dictionnaire sera la même que celle du fichier original. Plus chaque mot apparait souvent, plus il est facile de compresser le texte, et donc un gros texte aura un taux de compression plus élevé. (Attention, cela fonctionne avec un fichier de texte. Un fichier vidéo de la même taille ne pourra quasiment pas être compressé sans perte car les données se répètent beaucoup moins).

Bref, tout ça pour dire que je doute qu'il existe un meilleur algo que zip pour le texte, à moins que tes fichiers soient très particuliers.

Si c'est possible dans ton cas, essaye de compresser plusieurs fichiers texte ensemble, le texte de base étant plus grand, tu devrais avoir un meilleur taux de compression global.

[Rakken]

Après, tu peux tenter les autres...

En vrac : 7-ZIP, A, ACE, ARC, ARJ, B64, BH, BZ2, BZA, CAB, CPIO, DEB, ENC, GCA, GZ, GZA, HA, JAR, LHA, LIB, LZH, MBF, MIM, PAK, PK3, RAR, RPM, TAR, TAZ, TBZ, TGZ, TZ, UUE, WAR, XXE, YZ1, Z, ZIP, ZOO

Par contre, je ne suis effectivement pas convaicu que tu trouveras mieux. Plus ton fichier est petit, moins tu as matière à compresser.

[SCalc]

Bonjour,

merci a tous pour vos réponses

Il y a une borne théorique au taux de compression qui peut être atteint, c'est l'entropie.
Si tu la calcules sur le fichier, tu sauras combien tu peux espérer si tout est parfait dans le meilleur des mondes ^^.

Est-ce qu'il y a un outil pour calculer ca ? Si gzip fait deja presque aussi bien que le maximum, ce n'est plus la peine que je cherche...

Jérôme

[progfou]

C'est assez simple à calculer :
http://perso.univ-lr.fr/pcourtel/esp...h2/page2-1.htm

La formule est ici :

[Jean-Marc.Bourguet]

On peut calculer cela dans un modele donne. Mais le choix du compresseur est en quelque sorte un choix de modele.

Par exemple Huffmann est presque parfait dans le modele utilise, et le codage arithmetique gagne la derniere fraction de bit. Mais si tu passes a un autre algo (un ordre superieur, par dictionnaire,...) tu peux faire mieux pour autant que tes donnees s'y prete.

Pour des petits fichiers textes, si tu implementes ton compresseur toi-meme et que tu as une bonne idee du contenu probable, une idee qui n'est pas implementee dans les compresseurs generiques est un algo a dictionnaire avec un dictionnaire precharge.

Edit: crosspost avec progfou, il donne le maximun theorique dans le cadre du modele pour lequel Huffman est presque parfait.

[PRomu@ld]

tu peux faire mieux pour autant que tes donnees s'y prete.

C'est typiquement le cas de données redondantes, il y a pour celà la méthode RLE. Qui consiste à mettre pour des répétitions d'un certain nombre de caractères le nombre de répétition suivit du caractère répété.

Par exemple AAAAAAAAAA sera encoré en 10A, ce qui est sans doute très proche de l'optimalité.

quelqu'un connaitrait-il un "bon" algorithme de compression de fichiers texte (en francais) courts (~ 5 Ko). Sur ce genre de petits fichiers, gzip/winzip ne compresse que d'un facteur 2 (alors que ca atteint 90% sur des gros fichiers texte). bzip2 ne fait guere mieux (55%).

Le problème des algos basé sur Huffman sur les petits fichiers est que l'on stocke soit la table de huffman soit l'arbre de huffman dans le fichier. Ceci entraine donc une augmentation de l'espace nécéssaire, c'est pourquoi tu obtiens un faible taux de compression sur des petits fichiers.

Mais d'ailleurs pourquoi compresser de si petits fichiers ?

[SCalc]

Bon, j'ai trouvé paq8g à l'adresse http://cs.fit.edu/~mmahoney/compression/#paq8

auquel j'ai rajouté le dictionnaire français disponible ici: http://www.ii.uni.wroc.pl/~inikep/research/dicts/

Résultats:

fichier brut: 4997 octets
winzip: 2490
paq8g: 1544 !

Il me reste à voir si je sais décompresser ces fichiers dans mon application. J'ai besoin de compresser ces petits fichiers parce que j'en ai plein (et je ne veux pas les concaténer parce que je ne peux lire que des petits fichiers)

Jérôme

[PulkoMandy]

Il devrait aussi être possible de compresser les fichiers tout en les gardant séparés, mais avec un dictionnaire commun. Par contre là tu es bon pour coder toi même le compresseur et le décompresseur...
Ça marchera en particulier si tes fichiers se ressemblent (mots en commun).
Tu peux alors atteindre la mêm compression que sil es fichiers étaient concaténés, mais en les gardant séparés