IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Remplir un fichier binaire de BITS !!!!


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    enfin je pense pas que ca pose des probs

    dans mon fichier compressé j'ai la suite de caracteres correpondant au code ascii des int que j'ai codé, et le -6 (par ex) correpont bien au caractere qui a la code 250...

    donc je pense pas que ca pose un prob en vue de la decompression ....

  2. #2
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    je suis tres content ca roule !!!

    pour la decompression il me suffit de repasseren binaire, de reconstruire le tas de huffman et le parcourir bit par bit, ca devrait etre faisable

    merci pour ton aide encore une fois je pense que je vais m'en sortir now, mais si j'ai un prob je reviendrais .....

  3. #3
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Par défaut
    Citation Envoyé par Emmanuel Delahaye
    Je vois mal comment coder du Huffman sans passer la taille de chaque 'pseudo-caractères', puisque celle-ci est variable...
    C'est pourtant très simple, et ça se résume en une seule expression : "séparabilité des codes de Huffman". C'est quand même une des bases de cet algo...
    En bref, les codes de Huffman ne sont jamais préfixes d'un autre code de Huffman, et coder la longueur des codes compressés est donc complètement aberrant, pour ne pas dire saugrenu.
    D'ailleurs, à ce sujet, il y a deux grandes manières d'implémenter les codes de Huffman : une version où il existe deux codes de deux bits comme "codes courts", et une version où il existe un code d'un seul bit. La méthode "classique" consiste à avoir un code minimal de 2 bits (compression maximale : 25% de la taille d'origine), mais l'autre permet sur certains fichiers d'améliorer la compression (12.5% de la taille d'origine).

    Citation Envoyé par ben13
    maintenant je dois les prendres 8 par 8 et en faire un nombre compris entre 0 et 255. jai bien suivi mes cours sur la numération ( ) mais je suis obligé de me taper un algo avec les puissances de 2 ???? ya pas une fonction standard qui peut me convertir une suite de huit 0 et 1 en un entier ????????
    A l'époque, j'avais également eu à coder un algo de Huffman. J'étais parti sur une méthode (à mon sens) beaucoup plus simple, qui était de transformer mon fichier en flux de bits. En version simple, ça consiste lire ou à écrire au travers d'un octet qui sert de "buffer" aux bits émis, ces bits étant émis par décalage binaire du buffer.
    Tous les 8 bits émis, tu lis un nouvel octet ou tu écris celui qui est "plein". En interne, il te suffit de faire une encapsulation de tes fonctions de lecture/écriture (fread/fwrite) pour être tranquille.

    Enfin, pour garantir la séparabilité des codes (qui est liée à la répartition statistiques des caractères), il est en général préconisé de stocker cette table des fréquences dans le fichier compressé. L'optimisation de ce stockage peut également être un exercice assez amusant.

    Dans mon propre cas, l'implémentation était à faire en ADA, et ça n'a pas franchement été très compliqué malgré l'extrême rigidité du langage... Alors en C, c'est du gâteau ou presque d'implémenter un tel buffer, les problèmes ne pouvant réellement survenir que si l'on veut optimiser lourdement ces opérations de lecture/écriture.

    Si tu sais lire l'ADA, je peux te faire passer ces sources.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  4. #4
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    salut mac LAK

    moi j'ai eu la meme idee que toi sachant que la structure de tas a la propriété qu'aucun code est le prefixe d'un autre.

    mon fichier compréssé est donc la suite des codes binaires de chacun des caracteres du texte, sans aucune indication de longueur puisque celle ci ne sert a rien.

    bref la compression est tres bonne, il me reste plus qu'a implementer le tableau de correspondances caractere/code binaire dans le fichier compressé, et le tour est joué

    je vais essayer d'optimiser la taille de ce tableau car sinon la compression sur des fichiers de petite taille risque de ne pas etre evidente ........

    a+

  5. #5
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    pour les sources c'est gentil mais j'aime pas les sources ...... je prefere demander conseil s'il faut mais programmer moi meme, det toute facon je pense plus avoir de prob now.

    et en plus je sais pas lire l'ADA

  6. #6
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Par défaut
    Si tu veux, par contre, je peux poster ici les différentes optimisations que j'avais utilisées pour stocker la table des fréquences de manière la plus compacte possible. J'utilisais trois techniques différentes (et complémentaires) pour réduire cette taille.

    Ce n'est pas forcément optimal, mais par rapport aux 1024 octets "par défaut" de cette table, je tombais souvent à des chiffres bien inférieurs (souvent <100 octets, si ma mémoire est bonne). Bien sûr, si la taille de la table de fréquence (même optimisée) était supérieure au gain de compression, je renvoyais un warning "Fichier non-compressible" : libre à l'utilisateur après de forcer la "compression" ou pas, mais il était prévenu que la taille "compressée" serait supérieure à la taille d'origine. De toutes façons, ce cas de figure est inévitable avec les algorithmes de compression sans pertes, alors autant le gérer proprement ! ;-)

    Pour les sources, no problem : comme on dit, "Librement proposé, librement refusé" ! ;-) Et puis c'est vrai que ne pas savoir lire l'ADA, c'est une bonne raison...
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  7. #7
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    merci a toi.

    mais j'ai pensé que ca serait ptet pas une mauvaise idee que de stocker dans le fichier directement le tas de huffman. Parce que de toute facon le tableau de correspondances m'aurais servi uniquement a reconstruire l'arbre ....

    je vais essayer mais je pense que ca doit pas poser de prob en C en mettant dans mon fichier des sizeof(ma structure de noeud de mon tas ....) fois le nombre de noeud que je peux calculer recursivement .....

  8. #8
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    je me rapellais plus qu'un pointeur etait codé sur un int ...

    du coup l'arbre est beaucoup trop lourd

    je vais donc coder la tableau (les 256 tanpis pour celles qui servent a rien) mais chaque case sera composé de seulement 2 unsigned char (un pour la taille du code et un pour le code que j'aurai convertir du pseudo binaire en char)

    du coup 256*2 = 512 octets .... c'est raisonnable

  9. #9
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Par défaut
    Effectivement, stocker l'arbre est une très mauvaise idée : il faut stocker uniquement les fréquences, et recalculer l'arbre avant de décompresser.

    Perso, j'avais utilisé plusieurs astuces pour ce stockage :
    - Stocker, en début de table, le nombre de bits utilisés pour stocker les fréquences (de 1 à 32) => déjà, on gagnait beaucoup de place, et comme de toutes façons le fichier était déjà lu bit à bit, ça ne pénalisait pas le traitement. Il suffit de 5 bits pour stocker cette valeur.
    - Stocker le premier et le dernier caractère ayant une fréquence. Par exemple, sur du texte sans caractères accentués, ça donnait souvent 10 comme premier caractère (LF) au lieu de zéro, et 122 comme dernier caractère (au lieu de 255). Bref, une grosse place économisée. J'utilisais un bit pour indiquer s'il y avait un premier/dernier ou pas : en fonction du nombre de fréquences "gagnées" en début et fin de table, ce n'était parfois pas rentable de stocker ces deux valeurs => ainsi, je ne perdais qu'un seul bit au lieu de perdre deux octets.
    - Enfin, sur les fréquences restantes, je stockais une "table de présence". C'était tout simplement une succession de bits correspondant aux fréquences possibles (dans le cas précédent, de 10 à 122 donc, soit 113 bits), indiquant s'il y avait une fréquence non-nulle (1) ou pas (0). Sur du texte, il y avait souvent de nombreux "trous" dans la table des fréquences, un calcul simple permet de savoir s'il est rentable de stocker une telle table de présence ou pas (nombre de fréquences nulles X taille en bits d'une fréquence > nombre de fréquences à stocker == rentable). Comme précédemment, un simple bit suffit à indiquer si cette table est présente ou pas.

    Je te conseille de rajouter une signature (2 octets minimum) pour "identifier" le type de fichier (par exemple, les deux premiers octets du fichier étant toujours "AH" pour "Archive Huffman", ou n'importe quoi d'autre). Bref, le même "truc" que l'on trouve sur beaucoup de formats de fichiers (EXE Dos/Win, BMP, GIF, etc...).
    Il ne serait pas nuisible de mettre en plus un checksum pour le calcul d'intégrité de l'archive (CRC16 ou CRC32 par exemple) : non seulement c'est plus fiable, mais ça t'évitera de crasher ton programme si les données sont corrompues.

    On peut encore améliorer ce stockage des fréquences, bien entendu, mais ces trois trucs combinés donnaient souvent d'excellents résultats au vu du peu de calculs que ça demandait.

    Si tu veux t'amuser un peu, pense à écrire sur la sortie de ton programme les gains obtenus par tes procédés d'optimisation du stockage, tu risques d'être agréablement surpris dans certains cas.

    ++ !
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  10. #10
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    je vais pas faire tout ca lol c juste un projet pour mes cours....

    non mais la j'ai un prob par contre

    si je compresse un texte ou ya juste un '£' (caractere livre) dedans

    il me mets ca

    free(): invalid pointer 0x40086f6f!
    Erreur de segmentation

    pourtant mon algo marche avec un texte composé uniquement de lettres par exemple et meme tres long.........

    pourtant j'ai testé le code ASCII du '£' est bien reconnu par mon systeme ....


    ta une idee ???? merci

  11. #11
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    au fait, c'est une question moins importante que la precedente mais bon ...

    je vois pas l'interet de stocker les frequences, moi je stocke les codes binaires et je reconstruirai l'arbre a partir de ca.....

  12. #12
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    bon apres quelques test j'ai une erreur de segmentation (mais pas de message pointer invalide) pour pas mal de caracteres...... 'é' par exemple .......

  13. #13
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    hum apperement c'est des caractere qui sont dans la 2e moitié du code ASCII prolongé, c'est surement un prob de char qui est pas en unsigned.

    je vais voir ca je te tiens au courant

  14. #14
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    bon beh nom j'ai remplacé tous les char de mon script par des unsigned char et tjs l'erreur de segmentation ....

  15. #15
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    OK c'est resolu ! 8) 8)

    c'etait une erreur d'inatention rien de grave ....

    regarde un peut :

    -rwxr-xr-x 1 ben ben 15651 2004-12-20 18:54 huff2
    -rw-r--r-- 1 ben ben 7553 2004-12-20 18:54 huff2.c
    -rw-r--r-- 1 ben ben 5315 2004-12-20 18:56 zip


    le fichier nommé zip est la compression de huff2.c .... c'est pas mal quand meme ....

  16. #16
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Par défaut
    Citation Envoyé par ben13
    je vais pas faire tout ca lol c juste un projet pour mes cours....
    Ben moi aussi, c'était un projet de Licence, et alors ?

    Citation Envoyé par ben13
    je vois pas l'interet de stocker les frequences, moi je stocke les codes binaires et je reconstruirai l'arbre a partir de ca..
    Parceque stocker la table de fréquence permet de bien recomposer le même arbre, et de ne pas faire dépendre l'algo d'une implémentation particulière. De plus, stocker les codes pose quelques problèmes : il faut aussi stocker les caractères d'origine, et le code de Huffman lui-même. Or, à ce stade, il ne sont pas encore séparables !!
    Il faut aussi stocker leur longueur... Bref, ça prend souvent beaucoup plus de place que de stocker la table des fréquences, surtout si tu optimises un peu ce fameux stockage !

    Voici un dump de mon propre projet, sur un fichier de taille/nature similaire :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
     Compactage de fragment.cpp :
       - Calcul de la table des frequences : OK.
       - Calcul des codes de Huffman       : OK.
       - Sauvegarde de l'en-tete           : OK.
       - Compactage du fichier             : % 67
     
     
     Resultats :
     ===========
     
     Fichier original    : fragment.cpp
     Taille              : 7507 octets.
     
     Fichier compresse   : fragment.HUF
     Taille              : 5087 octets.
     Taux de compression : 67 %
     
     Informations :
     ==============
     
     Taille de l'en-tete         : 1234 bits.
     Longueur d'une frequence    : 10 bits.
     Nombre de frequences codees : 93
     Codage topologique          : Oui.
     Octet le plus frequent      : 32
                   Frequence     : 985
    Note : la taille de 5087 octets comprend la taille de l'entête, qui lui-même comprend la table des fréquences.
    Comme tu peux le constater, l'entête est très petit (un peu moins de 155 octets) par rapport à la taille du fichier : il ne représente qu'environ 3% de la taille de l'archive... Tu comprends maintenant pourquoi j'ai stocké la table des fréquences et non pas les codes ! ;-) 8)

    Citation Envoyé par ben13
    c'est pas mal quand meme ....
    Et tu arrives à le décompresser, ou pas encore ? Parceque c'est quand même "ZE" test ! ;-)
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  17. #17
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    j'ai pas encore programmé la decompression mais je vois pas pkoi ca marcherai pas ..... moi je suis tjs pas d'accord ( ) pour stocker la table des frequences.

    Avec mon tableau qui donne pour chaque caractere son code et la taille de ce code, je cree un arbre vide, puis je lis le code du premier caractere, si je tombe sur un 0, je descend vers le fils gauche, si je tombe sur un 1, je descends vers le droit....ceci jusqu'a la fin du code puis je fous mon caractere a cet endroit. Je recommence l'operation pour chaque caractere et a la fin je suis SUR de retomber sur l'arbre original, sans les frequences mais celles-ci ne servent plus a rien a ce stade.

    Ensuite je lis bit par bit (ce qui va d'alleurs me poser un petit prob mais bon) et je descend dans mon arbre, des que je tombe sur un NULL j'ecrit le caractere dans le fichier qui sera le fichier decompressé....


    Pke une chose que j'ai pas trop comprise avec ta methode, c'est que on est bien d'accord que je dois stocker le tableau des frequences mais aussi avec les codes et donc la taille des codes, et vu que je me sens pas de faire pleins d'optimisations comme toi .... ( car j'ai deja passé pas mal d'heures la dessus et j'ai pas mal de matieres a reviser pour les exams....) beh ca risque de me faire quelque chose de tres lourd à stocker ......

  18. #18
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    chui en train de penser que j'ai dit une belle connerie.

    En stockant le tab des frequences tu peut reconstruire l'arbre en utilisant la meme fonction qu'au debut et donc ta les codes, et tu peux donc reconstruire, encore avec la meme fonction, le tableau de codes ... c genial !!!! (bref tavais raison quoi...)

    dsl mais j'ai un peu le cerveau en bouillie ces derniers temps ....


    par contre si je fais aucune optimisation et que je considere que les indices correspondent aux caracteres, le tableau mesure quand meme 256 int donc 1024 Ko .... c'est lourd


    je vais reflechir un peu .....

  19. #19
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    du coup j'ai mieux regardé les optimisations que ta fait toi .... et c'est pas bete du tout mais je me sens pas de faire ca dans un premier temps je prefere un algo lisible au max pour pas m'y perdre en cas j't reviendrais plus tard .....

    si j'ai le temps demain je vais essayer de faire ca donc

    a+

  20. #20
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    63
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 63
    Par défaut
    bon voila j'ai reconstruit mon arbre a partir du fichier et ca marche (je l'ai affiché c'est ok), demain j'ai plus qu'a faire une fonction qui lit le fichier et qui parcours l'arbre pour afficher les caracteres ...

    je pense que je vais faire une sorte de "tableau buffer" dans lequel je mettrais les 0 et les 1 que j'aurai convertit des unsigned char contenus dans le fichier compressé ....

    par contre je me tate pour savoir de combien d'octet je devrais faire ce "tableau buffer" remarque a mon avis c'est bonnet blanc, blanc bonnet ....

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Remplir un fichier binaire à partir d'une image
    Par my_account dans le forum C
    Réponses: 5
    Dernier message: 10/12/2011, 16h17
  2. impossible de remplir une structure à partir d'un fichier binaire
    Par étoile de mer dans le forum Débuter
    Réponses: 3
    Dernier message: 21/12/2009, 12h28
  3. Fichiers binaires et machine 32 ou 64 bits
    Par genteur slayer dans le forum Fortran
    Réponses: 5
    Dernier message: 10/03/2009, 17h23
  4. Ecrire dans un fichier binaire en inversant les poids des bits
    Par zejo63 dans le forum Entrée/Sortie
    Réponses: 1
    Dernier message: 09/07/2007, 15h11
  5. Réponses: 5
    Dernier message: 03/06/2005, 14h06

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo