Méthodes de compression - Page 2

OK merci.

Par contre juste une question de nioob:

J'ai une matrice de pointeurs de ce genre void *ptr[x][y]; et je voudrais lui allouer moi même la mémoire qu'il faut, soit x*y*sizeof (void*); comment je dois faire avec malloc, je n'arrive pas aussi à allouer de la mémoire même sur une simple matrice: unsigned short lst[x][y];

Merci d'avance.

Aussi, il est plus interessant d'utiliser new et delete pour créer un espace de stockage ou malloc et free?

je n'arrive pas aussi à allouer de la mémoire même sur une simple matrice: unsigned short lst[x][y];

Euh, c'est de taille fixe ça Tu veux dire unsigned short *lst[x][y] ?

Aussi, il est plus interessant d'utiliser new et delete pour créer un espace de stockage ou malloc et free?

Tu fais du C++ ? Je croyais que tu voulais le faire pour calc aussi...
Pour ta question, il n'y a aucun intérêt à utiliser new/delete si c'est pour le faire sur un 'int[n]' (mais en principe tu n'as pas le droit de mélanger malloc/free et new/delete dans un prog C++, donc si tu utilises des containers C++ du genre vector ou string, il faut que tu utilises new/delete)

Une question à propos de new et delete :
Ce sont bien deux opérateurs du C++ ?
Cela signifie qu'ils ne sont pas définis dans la libc++ (enfin, je ne sais pas comment elle s'appelle) ?
Mais pourtant les opérations d'allocation/désallocation de mémoire sont dépendantes du système, non ?
Cela signifie que si on veut porter g++ vers un autre système, il n'y aura pas seulement la libc++ à porter, mais aussi l'intérieur du compilateur ? Je me doute bien que de toute façon, il y aurait des petits changement à faire pour porter un compilo vers une autre système, mais pas aussi importants que ceux nécessités par l'implantation de new et delete.

Euh, c'est de taille fixe ça Tu veux dire unsigned short *lst[x][y] ?

Bah en fait oui mais je ne veux pas que le compilateur créer cette espace, je veux m'en occuper.

Tu fais du C++ ? Je croyais que tu voulais le faire pour calc aussi... Pour ta question, il n'y a aucun intérêt à utiliser new/delete si c'est pour le faire sur un 'int[n]' (mais en principe tu n'as pas le droit de mélanger malloc/free et new/delete dans un prog C++, donc si tu utilises des containers C++ du genre vector ou string, il faut que tu utilises new/delete)

Je ne savais pas, je vais alors utiliser malloc et free.

Sasume :
Une question à propos de new et delete :
Ce sont bien deux opérateurs du C++ ?
Cela signifie qu'ils ne sont pas définis dans la libc++ (enfin, je ne sais pas comment elle s'appelle) ?
Mais pourtant les opérations d'allocation/désallocation de mémoire sont dépendantes du système, non ? Cela signifie que si on veut porter g++ vers un autre système, il n'y aura pas seulement la libc++ à porter, mais aussi l'intérieur du compilateur ? Je me doute bien que de toute façon, il y aurait des petits changement à faire pour porter un compilo vers une autre système, mais pas aussi importants que ceux nécessités par l'implantation de new et delete.

Ce sont des opérateurs dans le sens où il y a un support de new/delete dans le compilo (à cause de la syntaxe "bizarre" qui ne ressemble pas du tout à une fonction). Mais c'est la libc++ qui définit ce que font ces opérateurs (par une surcharge d'opérateur, comme pour << ou >> pour les streams; la seule différence étant qu'il n'y a aucun type pour lequel new/delete est défini par défaut, contrairement à <</>> qui est déjà défini pour des entiers).

Bah en fait oui mais je ne veux pas que le compilateur créer cette espace, je veux m'en occuper.

Je comprends pas
Tu veux créer une matrice 2D toi-même, ou tu veux créer toi-même le contenu des case de la matrice 2D ?

Allouer moi même la mémoire necessaire.

Passe par des matrices 1D, alors, c'est plus simple...

Pollux
: Ce sont des opérateurs dans le sens où il y a un support de new/delete dans le compilo (à cause de la syntaxe "bizarre" qui ne ressemble pas du tout à une fonction). Mais c'est la libc++ qui définit ce que font ces opérateurs (par une surcharge d'opérateur, comme pour << ou >> pour les streams; la seule différence étant qu'il n'y a aucun type pour lequel new/delete est défini par défaut, contrairement à <</>> qui est déjà défini pour des entiers).

Ah merci, je comprends mieux
Ton explication est parfaite.

Passe par des matrices 1D, alors, c'est plus simple...

Euh je voudrais quand même savoir comment faire.

Tu as une nouveauté du C99 dont on a parlé au moins 42^42 fois ici qui te permet de faire ça (et j'ai la flemme de réexpliquer ). Mais peu de compilos C++ (à part GCC, et encore c pas tout à fait sûr) gèrent ça, donc c pas forcément une super idée...

lol ok je vois mieux, donc j'ai vais rester comme ça avec mes tables de hachage ou trouver une autre solution...

Ou sinon, utilise boost qui a des types "matrice" prédéfini. Ou si tu n'as pas besoin d'une efficacité énorme, le vector<vector<short> > marche bien... (la taille de chaque ligne sera stockée indépendamment)

OK je vais déjà corriger mes bugs et voir si mes tables de hachages me conviennent.

geogeo :
J'ai une matrice de pointeurs de ce genre void *ptr[x][y]; et je voudrais lui allouer moi même la mémoire qu'il faut, soit x*y*sizeof (void*); comment je dois faire avec malloc, je n'arrive pas aussi à allouer de la mémoire même sur une simple matrice: unsigned short lst[x][y];

En C99:
unsigned short (*lst)[y]=malloc(x*y*sizeof(short));
unsigned void *((*ptr)[y])=malloc(x*y*sizeof(void*));

Aussi, il est plus interessant d'utiliser new et delete pour créer un espace de stockage ou malloc et free?

Comme tu veux.

Pollux
: (mais en principe tu n'as pas le droit de mélanger malloc/free et new/delete dans un prog C++, donc si tu utilises des containers C++ du genre vector ou string, il faut que tu utilises new/delete)

Tu peux très bien les utiliser dans le même programme (sinon, les programmes combinés C-C++ ne marcheraient pas). Ce que tu n'as pas le droit de faire, c'est d'utiliser une fonction différente pour allouer et pour libérer.

Sasume :
Une question à propos de new et delete :
Ce sont bien deux opérateurs du C++ ?
Cela signifie qu'ils ne sont pas définis dans la libc++ (enfin, je ne sais pas comment elle s'appelle) ?
Mais pourtant les opérations d'allocation/désallocation de mémoire sont dépendantes du système, non ? Cela signifie que si on veut porter g++ vers un autre système, il n'y aura pas seulement la libc++ à porter, mais aussi l'intérieur du compilateur ? Je me doute bien que de toute façon, il y aurait des petits changement à faire pour porter un compilo vers une autre système, mais pas aussi importants que ceux nécessités par l'implantation de new et delete.

Ce sont des opérateurs, mais définis dans la librairie C++ à travers le principe de l'overloading, et ils délèguent le vrai travail au système, généralement à la librairie C. C'est pour ça qu'avec certaines implémentations, tu peux mélanger new et free, par exemple (alors que ce n'est pas du tout garanti).

Pollux
: Mais peu de compilos C++ (à part GCC, et encore c pas tout à fait sûr) gèrent ça, donc c pas forcément une super idée...

g++ gère le VLAs en C++. http://gcc.gnu.org/onlinedocs/gcc-3.3.2/gcc/Variable-Length.html#Variable%20Length

Variable-length automatic arrays are allowed in ISO C99, and as an extension GCC accepts them in C89 mode [remarque: il s'agit évidemment du gnu89 et pas du c89 strict] and in C++
.

Utilise les VLAs, c'est beaucoup plus efficace que les alternatives en C++.

OK merci pour ses infos.

Tu peux très bien les utiliser dans le même programme (sinon, les programmes combinés C-C++ ne marcheraient pas). Ce que tu n'as pas le droit de faire, c'est d'utiliser une fonction différente pour allouer et pour libérer.

Non, évidemment on ne peut pas faire new puid free. Mais on m'avait dit précisément qu'on avait pas le droit de mélanger new/delete et malloc/free (ce qui m'avait franchement étonné). Je ne sais pas exactement pkoi, peut-être que c'est juste une question de fragmentation du heap. En tout cas je n'en vois effectivement aucune trace dans le standard ISO...

g++ gère le VLAs en C++. http://gcc.gnu.org/onlinedocs/gcc-3.3.2/gcc/Variable-Length.html#Variable%20Length

Oui. Mais il n'y a comme je le disais que g++ qui le supporte (ou _quasiment_, peut-être que Intel C++ le supporte aussi), et ce n'est pas _toujours_ une bonne idée d'utiliser g++ (personnellement, je n'aime ni ses temps de compilation astronomiques, surtout en C++, ni son manque de features de débuggage, même si je m'arrange tjs pour être compatible avec).

j'ai un petit soucie, j'ai réalisé la méthode de compression LZW, ça fonctionne à merveille sauf que je trouve la compression lente même avec mes tables qui regroupe une liste des élements du dictionnaire commencant par la même lettre. Y aurait-il un moyen d'accélérer la recherche dans le dictionnaire?

J'ai aussi entendu parlé de Huffman progressif, pas besoin de stocker une table au début du fichier et comment ça focntionne car aucune infos sur ce sujet. Le JPEG utilise le Huffman progressif ou semi-adaptatif?

geogeo :
j'ai un petit soucie, j'ai réalisé la méthode de compression LZW, ça fonctionne à merveille sauf que je trouve la compression lente même avec mes tables qui regroupe une liste des élements du dictionnaire commencant par la même lettre. Y aurait-il un moyen d'accélérer la recherche dans le dictionnaire?

J'ai aussi entendu parlé de Huffman progressif, pas besoin de stocker une table au début du fichier et comment ça focntionne car aucune infos sur ce sujet. Le JPEG utilise le Huffman progressif ou semi-adaptatif?

progressif = reconstruction de l'arbre à chaque coup, c'est tout, il n'y a rien à rajouter. Regarde le bouquin que je t'ai conseillé, tout est inscrit dedans.

Ah ouai ok je vois merci.

Voilà j'ai réflechie à un algorithme de compression type RLE mais amélioré qui possède un bit témois indiquant ce qui suit et un simple caractère ou une répétition de caractères.

Le bit est à 0 si simple caractère, à 1 si répétition de caractères.

Dans le cas où ce bit est à zéro, on écrit sur 8 bit le caractère.
Dans le cas où le bit est à un on écrit sur 4 bits le nombres de répétition et sur 8 bits le caractère répété.

Voyez-vous une façon d'améliorer ça ou un RLE plus puissant au niveau des fichiers de données et non d'images?

Une dernière chose, pour faire du LZ77+Huffman, le fichier est traité en 2 passes? Une pour créer l'arbre de huffman et le codifier et l'autre pour le comprimer en LZ77?

Si ça interesse quelqu'un?

http://perso.wanadoo.fr/tisofts/divers/ComDOS.zip

C'est un programme ligne de commandes MS-DOS donc il faut utiliser l'invite de commandes de windows.

Mettez votre fichier à compresser dans le dossier où ce trouve le programme, le fichier doit faire 8 caractères max.

/c pour compresser + methode par exemple /LZW
/u pour décompresser pas besoin de spécifier de méthode

Si vous avez rentrez un fichier en argument lors de la compression un fichier avec l'extension tpe sera réalisé sinon ce sera le deuxième fichier que vous avez rentrez en argument.

L'ordre des arguments n'a pas d'importance.

Les méthodes LZW, LZ77 et RLE2 peuvent être paramétrés:

Pour LZW il accepte seulement l'argument /DICO_SIZE=x
LZ77 argument /WINDOW_SIZE=x et /BUFFER_SIZE=x
RLE2 argument /OCCUR_BITS=x

Bon tests et n'hésitez pas à me repporter tout bugs.

Bon, j'ai essayé avec le standard C++ (PDF décompressé) :

~ $ ls -l cps* | sort
-rw-r--r--    1 Paul     Aucun      659805 Feb 27 00:57 cps.rar
-rw-r--r--    1 Paul     Aucun      729001 Feb 27 00:53 cps.pdf.bz2
-rw-r--r--    1 Paul     Aucun     1060492 Feb 27 00:57 cps.zip
-rw-r--r--    1 Paul     Aucun     1089194 Feb 27 00:53 cps.pdf.gz
-rw-r--r--    1 Paul     Aucun     1573408 Feb 27 00:55 cps.lz77 *
-rw-r--r--    1 Paul     Aucun     2295943 Feb 27 00:54 cps.lzw  *
-rw-r--r--    1 Paul     Aucun     3676479 Feb 27 00:55 cps.huff *
-rw-r--r--    1 Paul     Aucun     5791840 Feb 27 00:56 cps.tpe  *
-rw-r--r--    1 Paul     Aucun     6024624 Feb 27 00:53 cps.pdf   << ORIGINAL
-rw-r--r--    1 Paul     Aucun     6155183 Feb 27 00:55 cps.rle2 *
-rw-r--r--    1 Paul     Aucun    10608445 Feb 27 00:55 cps.rle  *

Y a encore quelques progrès à faire (1.5x la taille du zip pour la meilleure compression, >2x la taille du RAR)

En passant, il manque http://www.7-zip.org dans ta comparaison. (C'est libre (LGPL) et gratuit (sauf si tu veux du tech support ou tout simplement être gentil , auquel cas c'est $20), contrairement au RAR, mais Win32-only malheureusement. Bref, le bzip2 ne risque pas de disparaître d'aussitôt.)

Tiens, il y a un SDK LZMA (décompression seulement) en C ANSI maintenant. Le compresseur est encore en C++ Win32 malheureusement. (À première vue, il avait l'air abordable pour un portage, à deuxième vue pas vraiment. La source incluse n'est pas complète, il faut plein de fichiers de la source de 7-Zip.) Je sens qu'il y aura bientôt un décompresseur *nix.

OK merci de toutes ses infos.

Pollux> C'est normal que j'arrive pas à des taux de compression comparable à winzip car je ne combine pas LZ77+Huffman... Mais bon mon compresseur c'est juste pour comparer les méthodes... Puis y aussi les réglages du dictionnaire...

Juste une petite note sur ça :

Tu peux très bien les utiliser dans le même programme (sinon, les programmes combinés C-C++ ne marcheraient pas). Ce que tu n'as pas le droit de faire, c'est d'utiliser une fonction différente pour allouer et pour libérer.

C'est vrai, mais c'est bien bien lourd en pratique. En général, il est plus simple de convertir.

Par exemple, j'ai des classes de chargement de textures depuis différents formats, certaines étant entièrement C++ (le tga notamment s'implémente bien, sans lib externe), d'autres utilisant des librairies c++ (libpng et libjpeg entre autres). J'utilise le polymorhpisme, toutes mes classes de chargement héritant d'une seule qui a ses fonctions en virtuelles pure.
Jusque là tout va bien. Là où ça se gâte, c'est si tu commences à faire des passages d'ownership sur les textures. Comment le nouveau propriétaire sait s'il doit utiliser free ou delete ?

Les bibliothèques bien contruites (libjpeg, libpng, zlib, libbz2, parmi celles que j'ai utilisé récemment(ben oui, le tga c'est un peu gros, alors je fait du tga.gz )) te fournissent toujours un moyen de remplacer malloc par une fonction custom (donc une fonction à toi qui fait un new ). Ca a l'air plus rébarbatif, mais au moins ça évite des erreurs bizarres plus tard.

En fait ce n'est pas une interdiction absolue, mais il semblerait que ce genre de mélange introduise une grosse fragmentation du heap... (j'imagine que new/delete gère mieux les petits blocs et donc, idéalement, utilise une méthode différente de celle de malloc)

Non, idéalement, malloc gère les petits blocs tout aussi bien que new.
Mais évidemment tout dépend du système d'exploitation et de la librairie C.

Aurez-vous une idée comment ce passe la compression de Huffman dans la compression LZH?
Car je viens de combiner LZ77+Huffman et j'obtient des taux identique qu'avec LZ77 tout seul.
Je lie le fichier, j'établis les fréquences de répétitions du caractères. Je crée l'arbre, je compresse en LZ77, au lieu d'écrire un simple caractère sur 8 bits j'écrit ce caractère avec le code de Huffman.

Je crée l'arbre, je compresse en LZ77

Euh, c'est pas franchement le meilleur ordre, puisque tu vas appliquer Huff aux caractères qui _sortent_ de LZ77, pas aux caractères qui entrent dedans