Bonjour tout le monde,
 
Dans le cadre d'un projet de fin d'études je dois réaliser un programme C qui permet la compression et l'archivage de données (comme tar et gzip). Parmis les algorithmes de compression, je me suis bien entendu tourner vers un algorithme de compression sans pertes (compressions de fichiers de données). Pour cela j'hésite entre l'algo d'Huffman et le LZW. Mon problème est que j'ai du mal à trouver une implémentation d'un de ces deux algorithmes pour la compression niveau bit. En effet, la plupart des docs sur ces algos sont en rapport avec des fichiers textes, et mise à part la manipulation des fichiers en binaire (via fopen et les paramètres "wb" et "rb" ) je ne vois pas comment construire un dictionnaire ou un arbre avec des mots binaires.
 
J'aimerais donc savoir si quelqu'un a un exemple d'implémentation afin que je comprenne le fonctionnement à ce niveau.
 
Merci d'avance.

regarde 7zip, il est open source

Ok merci je vais aller jeter un oeil

Ou la zlib, libbzip2, ...

zlib pour le LZW, et tu pourras passer un Huffman derriere (car juste faire un LZW pour un projet de synthèse ca va etre un peu leger ^^ )

Ok merci mais le principe est de ne pas utiliser de librairies auxiliaires pour la compression, je dois moi même me retapper l'algo

RLE ?

M'est avis que t'as pas bien compris les algos ou qu'ils etaient mal expliqués, car c'est bien avec des mots binaires (ie des suites finies d'octets) que tu bosses.
A+,

 
sur une image en niveau de gris c'est pas si mal comme compression (enfin faut pas trop de nuances ) Et c'est simple a mettre en place ^^
Mais evidement, faut utiliser autre chose derriere :x

ah bin moi je disais ca paske ca se torche rapidement, sinon effectivement, ca vaut pas trop grand chose

Bah le jpeg, c'est surtout du RLE qui est utilisé pour faire la compression (la partie huffman ou arithmétique, c'est juste pour frimer devant les filles).

Tiens c est marrant exactement le projet qu on a faire dans mon ecole (mais en premiere année et en 1 mois).

Lam's => Dans mon cours on parle de compression par bloc, ya peut etre les deux? on a pas vu en details le format jpg =/

le jpeg compresse par block de 8x8
je sais pas si c'est la reponse a la question mais c'en est une

Le jpeg, c'est :  
- on prend des blocs de 8x8
 
- on les transforme en espèce de fréquence via la DCT, donc on garde un bloc de 8x8, où la valeur en haut à gauche représente la valeur moyenne du bloc (appellé DC), et les autres valeurs représentent les fréquences de la plus basse à la plus haute (AC).
 
- on quantize (c'est la qu'on perd de l'info), en divisant les hautes fréquences par 10 par exemple, et les basses par 2 par exemple: ça permet d'arrondir les hautes fréquences en ne définissant que 25 niveaux différents, alors qu'on en a 128 différents pour les basses. En effet, les hautes fréquences sont moins "utiles". Il est à noter que comme déjà les hautes fréquences ne valaient pas grand chose, le fait de les diviser par 10 en a mis un sacré paquet à 0.
 
- on transforme alors le bloc en ziggaz
 
- puis on encode le bloc zigzagé en huffman+RLE. Comme il y a un sacré paquet de 0, ça se compresse très bien.
 
Y a 2-3 autres astuces également (le fait que ce soit encodé en YCbCr, le fait que le Y soit moins compressé que la couleur, le fait qu'on puisse faire du 4:2:2, etc.)

Je dirais comme gilou que t'as pas dû bien piger le truc, alors
J'ai implémenté Huffman en Java y a pas longtemps et texte ou binaire, je fais pas la différence. Le seul truc, c'est que l'alphabet pour un fichier texte étant plus limité, y aura plus de chances que le taux de compression soit meilleur qu'avec un fichier binaire. Cela étant, c'est à peu près tout au niveau des différences entre binaire et texte, y a aucun traitement spécial qui est infligé à l'un ou à l'autre dans le code.
Pis réfléchis un brin : tu vas ouvrir ton fichier en rb ou rt ? Tu bosses avec quel type de données ? Si t'as pas la réponse immédiatement, ba considère respectivement ces 2 aspects :
* quelle est la différemce entre rt et rb ?
* ça prend quoi comme paramètres, fread() ?

Lam's => merci pour ces infos

Lam's : je me rappele plus exactement les détails de l'algo JPEG mais ce qui est sur c'est que tu as laissé de coté notre sympathique Joseph et ses transformées (transformées de fourrier)
 
Edit : http://donut.99.free.fr/En-vrac/tipe/dct.htm

 
Non justement. DCT et Transformée de Fourier ne sont pas la même chose et n'ont pas le même usage.
 
Par exemple, si tu as une couleur unie pour ton bloc de 8x8, alors ta DCT aura le composant DC (en haut à gauche) à ta valeur, et le reste à 0, alors qu'une TdF aurait tous ses coefficients à 1.  
 
La FFT n'est pas très bonne à quantiser pour les images qui varient peu (et c'est le cas des photos numériques), alors que la DCT est très bien.
 
A noter que le JPEG2000 utilise les ondelettes. De mon expérience, ça ne donne pas des résultats spectaculairement meilleurs sur les images en 640x480, mais apparemment, pour les grosses résolutions, y a du mieux.