Gestion de nombre binaire...

Version imprimable

13/01/2006, 21h46
Zenol

Gestion de nombre binaire...

Bonjour, je voudrais ecrire des algoritmes de compression/decompression.
Pour cela, il me faut lire, ecrire et manipuler directement des bits.
Je voudrais savoir une petite liste de chose :
-La fonction .write() et .read de fstream doit absolument lire/ecrire 8bits???
-Comment ecrire directement dans la source le nombre 010010, ou encore manipuler dans des variables des suites de bits comme par exemple 010 ?
-Quel sont les règles qu'il vaut mieu respecter pour se faciliter la vie dans la manipulation des bits?

Merci d'avence ^^
13/01/2006, 22h08
Luc Hermitte

Re: Gestion de nombre binaire...

Citation:

Envoyé par JC_Master

a-La fonction .write() et .read de fstream doit absolument lire/ecrire 8bits???
b-Comment ecrire directement dans la source le nombre 010010, ou encore manipuler dans des variables des suites de bits comme par exemple 010 ?
c-Quel sont les règles qu'il vaut mieu respecter pour se faciliter la vie dans la manipulation des bits?

a- par paquets de 8.

b- Manipule tes bits dans des octets en mémoire et après sérialise les où il te plait

c- Manipuler des abstractions qui encapsulent les détails de gestion de la mémoire afin de se concentrer sur les manips de bits ?
14/01/2006, 12h01
Zenol

->Manipuler des abstractions qui encapsulent les détails de gestion de la mémoire afin de se concentrer sur les manips de bits ?
Bonne idée.. enffin si j'ai comprit(Tu veut que je fasse une classe qui s'ocupe de gèrer mes morceauts de bits, de les recoler ect?)

Sinon, un fichier doit obligatoirement contenir n*8 bits?
14/01/2006, 12h21
JolyLoic

Il y a std::bitset qui peut aider.
14/01/2006, 13h38
Luc Hermitte

Pas besoin de recoder quoique ce soit, entre std::bitset, set::vector<bool> et peut-être bien un dynamic bitset chez boost (il me semble), il y a le choix.

Et oui dans un fichier, ou dans un flux de données sur sockets, l'octet sera toujours l'élement atomique.
14/01/2006, 14h44
Zenol

Quand tu a noter set::vector<bool> tu voulais dire std::vector<bool> ou std::set<std::vector<boool>> ? ^^
Sinon, bitset ser a faire des manipulations sur les bits et peut en mmoriser par paquets(autre que 8)?
En fait, j'ai bien reflechi, je n'ai pas besoin de noter mes chifres sous forme binaire, une forme exadécimale conviendra(Enfin, pour le moment).
Je veut enfaite faire une dll qui se chargera de crypter/compresser puis de decrypter/decompresser un dossier de donnée. Une sorte de gros fichier qui fonctionera comme un repertoire, et dont je pourais aceder avec une fonction comme : getfile("/folder/file.bmp") par exemple.[Un peut comme les .grf pour ceux qui conaissent.] Je voudrais savoir si, une fois que j'ai décomprèsser/decrypter mon fichier, comment me débrouiller pour utiliser toute les fonctions/objet qui pointent vers un fichier(Comme std::ifstream ou SDL_image)
14/01/2006, 14h57
Jean-Marc.Bourguet

Citation:

Envoyé par JC_Master

En fait, j'ai bien reflechi, je n'ai pas besoin de noter mes chifres sous forme binaire, une forme exadécimale conviendra(Enfin, pour le moment).

Je ne vois pas de différence entre du binaire et de l'hexa pour ce genre de choses.

Citation:

Je voudrais savoir si, une fois que j'ai décomprèsser/decrypter mon fichier, comment me débrouiller pour utiliser toute les fonctions/objet qui pointent vers un fichier(Comme std::ifstream ou SDL_image)

Définir tes streambufs. Tu suis le lien vers la FAQ de fclc++ dans la signature de Luc et tu y trouves un exemple. Si ca ne te débloque pas, pose tes questions.
14/01/2006, 15h12
Zenol

Citation:

Envoyé par Jean-Marc.Bourguet

Citation:

Envoyé par JC_Master

En fait, j'ai bien reflechi, je n'ai pas besoin de noter mes chifres sous forme binaire, une forme exadécimale conviendra(Enfin, pour le moment).

Je ne vois pas de différence entre du binaire et de l'hexa pour ce genre de choses.

Si je travaillais sur des bits, j'aurais put avoir a gèrer des pacquets autre que 8, alors que en exa, c'est des paquets de 8(même si je peut ecrire 0x1 au lieu de 0x01)

streambufs -> C'est un nom de biscuit?
Tu suis le lien vers la FAQ de fclc++ dans la signature de Luc -> J'y vais, mais tu est sur que ce n'est pas des biscuits 8O
14/01/2006, 15h16
Jean-Marc.Bourguet

Citation:

Envoyé par JC_Master

Si je travaillais sur des bits, j'aurais put avoir a gèrer des pacquets autre que 8, alors que en exa, c'est des paquets de 8(même si je peut ecrire 0x1 au lieu de 0x01)

Tous les algo que je connais se terminent par une phase de Huffman ou de codage arithmétique. Donc il faut manipuler des paquets de bits de taille variable et non nécessairement multiple de 8. C'est quoi que tu veux utiliser?

Citation:

streambufs -> C'est un nom de biscuit?

Une classe de la bibliothèque standard: std::streambuf.
14/01/2006, 15h24
Zenol

[quote="Jean-Marc.Bourguet"]

Citation:

Envoyé par JC_Master

Tous les algo que je connais se terminent par une phase de Huffman ou de codage arithmétique.

O_O Pas de doute, je ne les connais pas... (ni MrHuffman, ni mr Arithmétique)

Bon, plus sérieusement :
-La faq explique comment créer des flux d'entrée/sortie, mais je ne voit pas comment ceci peut m'aider pour que sdl_image("/folder/img.bmp"); ouvre les octées que j'aurais stoquet en mémoire.[J'aimerais eviter de passer par un fichier temporaire)
-Je ne sais pas ce qu'est une phase de uffman. Pour le momment si j'arive a coder une metode de compression via dictionaire, se sera bien. En plus, cette metode est efficace sur de gros ficheir, hor mon dossier contiendra de nombreux fichier, et je pourais donc utiliser un dictionaire commun.
14/01/2006, 15h39
khayyam90

la doc sur le codage de Huffman -> http://tcharles.developpez.com/Huffman/
14/01/2006, 15h48
Jean-Marc.Bourguet

Citation:

Envoyé par JC_Master

Bon, plus sérieusement :
-La faq explique comment créer des flux d'entrée/sortie, mais je ne voit pas comment ceci peut m'aider pour que sdl_image("/folder/img.bmp"); ouvre les octées que j'aurais stoquet en mémoire.[J'aimerais eviter de passer par un fichier temporaire)

Tu parlais de istream, donc j'ai indiqué où trouver de l'info pour istream. Je ne connais pas sdl, je ne peux pas d'aider pour ça.

Citation:

Je ne sais pas ce qu'est une phase de uffman. Pour le momment si j'arive a coder une metode de compression via dictionaire, se sera bien. En plus, cette metode est efficace sur de gros ficheir, hor mon dossier contiendra de nombreux fichier, et je pourais donc utiliser un dictionaire commun.

Huffman (ou le codage arithmétique) est un moyen de gagner encore un peu sur le résultat du codage par dictionnaire.

Pour que ce soit utile d'avoir un dictionnaire commun pour de nombreux fichiers, il faut que ceux-ci aient des similitudes, sinon on perd.

De plus tu m'as l'air de vouloir faire de l'accès direct à un fichier, hors généralement on fait un codage adaptatif et avec un accès direct et un codage adaptatif, tu ne gagnes rien à compresser tes fichiers simultanément.

Je ne comrpend pas ce que tu me dit sur le codage adaptatife...
Je penser commencer par faire :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0xXX0xXX //Premier mot du dictionaire 0xXX0xXX //Deuxième mot du dictionaire 0xXX0xXX //... 0x000x00 //Debut du premier fichier /folder/pict1.img 0x00 //Contenu : 0xNN // Element du dico 0xNN // Element du dico 0xNN // Element du dico 0x00 //On code sur 1 byte de + 0xNNNN // Element du dico 0xNNNN // Element du dico 0xNNNN // Element du dico 0x000x00 // Debut d'un autre fichier /folder/pict2.img 0x00 //Contenu :
Edit : Je vien de lire la metode de compression de uffman. Sa me parait pas male du tout! Bon, par contre, il faudra une table par fichier, mais bon.
Sinon, j'ai une question technique : Si le contenu crypter resemble a sa : 01001, il menque 3 bit pour faire un paquet de 0. Comment je fait pour l'écrire dans un fichier? Si je complette la fin par 000, le problème sera a la relecture...

14/01/2006, 18h46
Jean-Marc.Bourguet

Citation:

Envoyé par JC_Master

Je ne comrpend pas ce que tu me dit sur le codage adaptatif

On change le dictionnaire en fonction de ce que le fichier à compresser contient.
15/01/2006, 11h10
Zenol

Oui? Donc si je comprèsse tout les fichiers(précèdament réduit de tail par un autre algorithme) avec un dictionaire commun, je ferais forcement des economies, car avec une grande variétée de fichier, j'aurais une grande variétée de mot a ajouter au dictionaire, et donc je ferais des economies. En plus, la lecture d'un fichier par le dictionaire, peut être faite avec n'importe quel partie du fichier, si on conais a quel position se trouve le début & la fin du fichier.

Sinon je repose ma question : Comment fait-on si a la fin d'un codage de uffman, il manque par exemple 3Bits pour que le nombre de bit soit multiple de 8?

Edit : J'ai lut ce document : http://fr.wikipedia.org/wiki/Lempel-Ziv-Welch
Seulement, dans l'exemple, il n'y a aucune compréssion! Le chaine retourner(colomne emit) est plus longue que la chaine a cripter("repetition"), et je ne compte pas le poid du dictionaire, si il est mit dans le fichier... Il y auraist-il une ereur?
15/01/2006, 16h01
Jean-Marc.Bourguet

Citation:

Envoyé par JC_Master

Oui? Donc si je comprèsse tout les fichiers(précèdament réduit de tail par un autre algorithme) avec un dictionaire commun, je ferais forcement des economies, car avec une grande variétée de fichier, j'aurais une grande variétée de mot a ajouter au dictionaire, et donc je ferais des economies.

Mais plus tu as de mots, plus il te faut de bits pour en représenter un. Avoir un grand dictionnaire n'est pas spécialement bien, il vaut mieux avoir un dictionnaire adapté.

Citation:

Sinon je repose ma question : Comment fait-on si a la fin d'un codage de uffman, il manque par exemple 3Bits pour que le nombre de bit soit multiple de 8?

Deux possibilités, il doit y en avoir d'autres: on transmet aussi la taille du fichier, on ajoute un marqueur de fin à l'alphabet compressé.

Citation:

Edit : J'ai lut ce document : http://fr.wikipedia.org/wiki/Lempel-Ziv-Welch
Seulement, dans l'exemple, il n'y a aucune compréssion! Le chaine retourner(colomne emit) est plus longue que la chaine a cripter("repetition"), et je ne compte pas le poid du dictionaire, si il est mit dans le fichier... Il y auraist-il une ereur?

Par principe, ces méthodes ne transmettent pas le dictionnaire: il est bâtit avec le même algorithme par l'encodeur et le décodeur.

Tout algorithme de compression a des entrées qu'il rend plus longue (sinon on réappliquerait l'algorithme à son résultat...), c'est en particulier le cas pour des petites chaînes.
15/01/2006, 16h24
Zenol

-Eu pardon, je me suis male expliquer. Je voulais dire que j'aurais plus de chance de troufer plusieure fois le même mot. Surement j'aurais un dictionaire volumineux, mais la probabilitée qu'il y ai seulement 1 fois un mot est très faible.

-on ajoute un marqueur de fin à l'alphabet compressé -> Commnet je fait pour savoir que c'est mon signale et pas la suite des données???(Il peut y avoir de la malchance et que au milieu du fichier se trouve la séquance de mon signale de fin...)

-Même sans donner le dictionaire, je ne voi pas le moindre gain? Pour chaque caractère comprèsser, on retrourne 1 caractère(sauf vers la fin ou on retourne 1 bit de plus!) Je ne voi pas comment il peut y avoir du gain....
15/01/2006, 16h34
Jean-Marc.Bourguet

Citation:

Envoyé par JC_Master

-Eu pardon, je me suis male expliquer. Je voulais dire que j'aurais plus de chance de troufer plusieure fois le même mot. Surement j'aurais un dictionaire volumineux, mais la probabilitée qu'il y ai seulement 1 fois un mot est très faible.

Il faut savoir si l'augmentation de la taille nécessaire pour représenter tout les mots est compensée par la fréquence du mot ajouté. Ce n'est pas gagné a priori. J'ai le souvenir de commentaires comme quoi dans un LZW il était intéressant de se fixer une taille maximale et arrivé à la taille maximale de vider complètement le dictionnaire plutôt que de continuer à ajouter des mots ou même de garder le dictionnaire tel quel.

Citation:

-on ajoute un marqueur de fin à l'alphabet compressé -> Commnet je fait pour savoir que c'est mon signale et pas la suite des données???(Il peut y avoir de la malchance et que au milieu du fichier se trouve la séquance de mon signale de fin...)

Ce symbole de fin est par définition quelque chose qui n'apparaît pas dans le fichier à coder. Si ton alphabet c'est les valeurs 0 à 255, ce serait donc la valeur 256.
15/01/2006, 17h01
Zenol

Le problème, C'est que 256 ne peut pas s'écrire sur 1 octet...

Sinon, je ne voi pas ou est le gain dnas l'algorithme. Même avec des textes imanses, je vois pas vraiment... Si on asoscier par exemple "abc" a 0x20 par exemple, la il y aurais un gain. Mais la, on met une clef qui a la taille du mot, donc il n'y a aucun gain ...
16/01/2006, 09h00
Jean-Marc.Bourguet

Citation:

Envoyé par JC_Master

Le problème, C'est que 256 ne peut pas s'écrire sur 1 octet...

Je ne vois pas de probleme la dedans.

Citation:

Sinon, je ne voi pas ou est le gain dnas l'algorithme. Même avec des textes imanses, je vois pas vraiment... Si on asoscier par exemple "abc" a 0x20 par exemple, la il y aurais un gain. Mais la, on met une clef qui a la taille du mot, donc il n'y a aucun gain ...

C'est justement le point que j'essaye de te faire comprendre: un dictionnaire trop grand (donc necessitant des encodages long) n'est pas necessairement utile.
16/01/2006, 21h11
Zenol

Esque tu pourais me donner un exemple ou il y a un gain???
Parce que, même sans le dictionaire, il n'y a pas le moindre gain, alors je ne voit pas comment il pourais y en avoir, que se soit avec dico, ou sans dico...
Esque c'est une histoire de : Plus un mot est fréquent, plus son codage est petit? Et dans ce cas, l'autre algorithme est bien plus eficace...
Sinon : Esque deux passage dnas l'algorithme que tu ma décrit(j'ai oublier le nom) ne fait pas un double gain?
Enffin, j'ai trouver un elgorithme qui organise els données, TEXTE -> TTXEE. Même si je sais comment l'executer, ou encore comment le programmer, je n'arive pas a comprendre ce qui fait qu'il marche, c'est a dire : Qu'il groupe les données + qu'il permet de retrouver la chaine d'origine)
Son fonctionement est :
(On decale la première lettre a gauche tout a droite)
TEXTE
EXTET
XTETE
TETEX
ETEXT
On classe apr ordre alphabetique
ETEXT
EXTET
TETEX
TEXTE
XTETE
Et on garde la dernière colomne...