AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  Connexion  

Partagez | 
 

 Encodeur huffman en ligne de commande + source

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
onilink_
Modérateur


Messages : 8850
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Encodeur huffman en ligne de commande + source   Mer 24 Oct 2012 - 15:30

Voici un petit encodeur/decodeur huffman réalisé pour les cours.
Je le poste ici pour ceux qui s’intéressent a tout ce qui touche a la compression/décompression de données.
Le code source est simple a comprendre, et la vitesse de compression/décompression est pas trop mauvaise.

Téléchargement: mediafire.com ?2b6txv4diisl11j

Utilisation
compresser: huffman fileIn fileOut
decompresser: huffman -d fileIn fileOut

Code source:
main.c
Code:
#include <stdio.h>
#include <stdlib.h>

#include "huffman.h"

int main(int argc, char** argv)
{
    if(argc < 2) {
        printf("Usage: huffman [-d] filein fileout\n");
        return 0;
    }
   
    if(argc == 2)
        huffmanEncode(argv[1], "out.huff");
    else
    if(argc == 3)
        huffmanEncode(argv[1], argv[2]);
    else
    {
        if(argv[1][0] == '-' && argv[1][1] == 'd')
            huffmanDecode(argv[2], argv[3]);
        else
            printf("Bad option\n");
    }
    return 0;
}

huffman.h
Code:
#ifndef HUFFMAN_H_INCLUDED
#define HUFFMAN_H_INCLUDED

typedef struct Tree
{
    float prob;
    short parent, feuilleGauche, feuilleDroite;
    unsigned char  car;
} Tree;

typedef struct Huffcode
{
    int len, code;
} Huffcode;

int huffmanEncode(const char* fnameIn, const char* fnameOut);
int huffmanDecode(const char* fnameIn, const char* fnameOut);

#endif // HUFFMAN_H_INCLUDED

huffman.c
Code:
#include <stdio.h>
#include <stdlib.h>
#include "huffman.h"

typedef unsigned char byte;

static int occ[256]={0};
static float proba[256];
static int total = 0;
static int nbFeuilles=0, nbNoeuds=0, root=-1;

/*
    Cette fonction cherche les deux fréquences les plus faibles dans tree
    afin de construire l'arbre binaire de fréquences.
*/
int chercherMin(Tree *tree, int taille, int *imin1, int *imin2)
{
    if(taille < 2)
        return 0;

    float min1 = 1.0, min2 = 1.0;
    *imin1 = -1;
    *imin2 = -1;
    for(int i=0; i<taille; i++)
    {
        if(tree[i].parent == -1) {
            if(tree[i].prob < min1) {
                *imin1 = i;
                min1 = tree[i].prob;
            }
            else
            if(tree[i].prob < min2) {
                *imin2 = i;
                min2 = tree[i].prob;
            }
        }
    }
   return 1;
}

/*
    Ouvre le fichier et compte les caractères, puis calcule leur
    fréquence d'apparition.
*/
int calculerFrequences(const char* fnameIn)
{
   FILE* f = fopen(fnameIn, "rb");
   
    if(f == NULL) {
        printf("Impossible d'ouvrir le fichier.n");
        return 0;
    }
   
    const int BUFF_SIZE = 4096;
    byte buffer[BUFF_SIZE];
    int loaded = fread(buffer, 1, BUFF_SIZE, f);
    int cursor = 0;
   
    while(cursor < BUFF_SIZE || loaded == BUFF_SIZE)
    {
        if(cursor >= BUFF_SIZE) {
            loaded = fread(buffer, 1, BUFF_SIZE, f);
            cursor = 0;
        }
        occ[buffer[cursor++]]++;
        total++;
    }
    fclose(f);
   
    if(total == 0) {
        printf("Fichier vide.n");
        return 0;
    }

    for(int i=0; i<256; i++)
        proba[i] = (float)occ[i]/total;

    for(int i=0; i<256; i++)
        nbFeuilles += (occ[i]>0);
   
    nbNoeuds = 2*nbFeuilles-1;
    return 1;
}

/*
    Crée l'arbre binaire en fonction des fréquences d'apparition
    des caractères pour créer les codes huffman.
*/
Tree* creerArbre()
{
    // Creation de l'arbre binaire
    Tree *tree = (Tree*) malloc(nbNoeuds * sizeof(Tree));
    for(int i=0; i<nbNoeuds; i++)
    {
        tree[i].prob = 1.0;
        tree[i].parent = -1;
    }
   
    int j=0;
    for(int i=0; i<256; i++) {
        if(proba[i]>0.0) {
            tree[j].prob = proba[i];
            tree[j].car = i;
            tree[j].parent = tree[j].feuilleGauche = tree[j].feuilleDroite = -1;
            j++;
        }
    }
   
    // min1, min2 = indices des 2 + petites proba qui n'ont pas de parents
    int idmin1, idmin2;
    while(j<nbNoeuds && chercherMin(tree, nbNoeuds, &idmin1, &idmin2))
   {
        tree[j].prob = tree[idmin1].prob + tree[idmin2].prob;
      tree[j].feuilleGauche = idmin1;
      tree[j].feuilleDroite = idmin2;
      tree[j].parent = -1;
      tree[idmin1].parent = tree[idmin2].parent = j;
      j++;
    }
   
    // j : racine de l'arbre
    root = j-1;   
    return tree;
}

/*
    Crée les codes huffman grace a l'arbre binaire.
*/
Huffcode* creerCodes(Tree* tree)
{
    // Creation des codes
    Huffcode *code = (Huffcode*) malloc(nbFeuilles * sizeof(Huffcode));
   
    for(int i=0; i<nbFeuilles; i++)
    {
        code[i].code = 0;
        code[i].len  = 0;
       
        int id = i;
        while(id != root)
        {
            int parent = tree[id].parent;
            if(id == tree[parent].feuilleDroite)
                code[i].code |= 1<<code[i].len; // 1
            // else 0
            id = parent;
            code[i].len++;
           
            if(code[i].len > 32) {
                printf("Impossible de creer les codes, la taille excede 32bits...\n");
                exit(1);
            }
        }
    }
    return code;
}

/*
    Crée le buffer ou on stoqueras le codage
*/
unsigned char* creerBuffer(Huffcode* code, Tree* tree, int* bufferSize)
{
    *bufferSize = 0;
    for(int i=0; i<nbFeuilles; i++)
    {
        *bufferSize += code[i].len * occ[(int)tree[i].car];
    }
    *bufferSize = ((*bufferSize|7)+1)>>3;
   
    // Creation du buffer
    unsigned char *buffer = (unsigned char*)malloc(*bufferSize);
   
    for(int i=0; i<*bufferSize; i++)
        buffer[i] = 0;
   
    return buffer;
}

/*
    Compresse le fichier et met le resultat dans le buffer
*/
int compress(const char* fnameIn, Huffcode* code, Tree* tree, unsigned char* buffer, int bufferSize)
{
    // Ecriture dans le buffer
    FILE* f = fopen(fnameIn, "rb");
   
    if(f == NULL) {
        printf("Impossible d'ouvrir le fichier %s\n", fnameIn);
        return 0;
    }
   
    // Table char / id
    int charId[256] = {0};
    for(int i=0; i<nbFeuilles; i++)
        charId[tree[i].car] = i;
   
   
    int pos=0, bytePos=0;
    unsigned int c = 0;
    while( (c = fgetc(f)) != EOF)
    {
        int id = charId[c];
       
        for(int i=code[id].len-1; i>=0; i--)
        {
            if( (code[id].code >> i)&1 )
                buffer[bytePos] |= (1<<pos);
            // on avance le curseur
            pos++;
            if(pos >= 8) {
                pos = 0;
                bytePos++;
               
                if(bytePos > bufferSize) {
                    return 0;
                }
            }
        }
    }
   
    fclose(f);
    return 1;
}

/*
    Enregistre la table des frequences ainsi que le buffer
*/
void save(const char* fnameOut, Tree *tree, unsigned char *buffer, int bufferSize)
{
    FILE *f = fopen(fnameOut, "wb");
   
    fwrite(&nbFeuilles, 1, 4, f);
    for(int i=0; i<nbFeuilles; i++)
    {
        fwrite(&tree[i].car, 1, 1, f);
        fwrite(&tree[i].prob, 1, 4, f);
    }
   
    fwrite(&total, 1, 4, f);
    fwrite(&bufferSize, 1, 4, f);
    fwrite(buffer, 1, bufferSize, f);
   
    fclose(f);
}

/*
    Fonction qui permettra de compresser un fichier
*/
int huffmanEncode(const char* fnameIn, const char* fnameOut)
{
    if(!calculerFrequences(fnameIn)) {
        printf("Probleme lors du calcul des frequences\n");
        return 0;
    } else printf("Frequences calculees\n");
   
    Tree *tree = creerArbre();
    printf("Arbre cree\n");
   
    Huffcode* code = creerCodes(tree);
    printf("Codes crees\n");
   
    int bufferSize;
    unsigned char* buffer = creerBuffer(code, tree, &bufferSize);
    printf("Buffer cree\n");
   
    if(!compress(fnameIn, code, tree, buffer, bufferSize)) {
        printf("Une erreur est survenue lors de la compression\n");
        return 0;
    }
    else printf("Compression completee\n");
   
    save(fnameOut, tree, buffer, bufferSize);
    printf("Fichier enregistre\n");
   
    free(buffer);
    free(tree);
    free(code);
   
    return 1;
}

/*
    Lis la table de fréquence et le buffer d'un fichier compressé
*/
unsigned char *read(const char* fname, int *bufferSize)
{
    FILE *f = fopen(fname, "rb");
   
    fread(&nbFeuilles, 1, 4, f);
    nbNoeuds = 2*nbFeuilles-1;
   
    for(int i=0; i<nbFeuilles; i++)
    {
        unsigned char c;
        fread(&c, 1, 1, f);
        fread(&proba[(int)c], 1, 4, f);
    }
   
    fread(&total, 1, 4, f);
    fread(bufferSize, 1, 4, f);
   
    unsigned char *buffer = (unsigned char*) malloc(*bufferSize);
    fread(buffer, 1, *bufferSize, f);
   
    fclose(f);
   
    return buffer;
}

/*
    Decode le buffer compressé et stoque le resultat dans le buffer 'decoded'
*/
void decode(Tree* tree, unsigned char* buffer, unsigned char* decoded)
{
    // Decompression
    int carPos = 0;
    int pos = 0, bytePos = 0;
    for(int k=0; k<total; k++)
    {
        int noeud = root;
       
        while(tree[noeud].feuilleGauche != -1)
        {
            if( (buffer[bytePos]>>pos)&1 )
                noeud = tree[noeud].feuilleDroite;
            else
                noeud = tree[noeud].feuilleGauche;
           
            pos++;
            if(pos>=8) {
                pos = 0;
                bytePos++;
            }
        }
       
        decoded[carPos++] = tree[noeud].car;
        #ifdef DEBUG
        printf("%c", tree[noeud].car);
        #endif
    }
}

/*
    Fonction pour decompresser un fichier
*/
int huffmanDecode(const char* fnameIn, const char* fnameOut)
{
    // lecture de la table des frequences et du buffer a decoder
    int bufferSize;
    unsigned char *buffer = read(fnameIn, &bufferSize);
   
    Tree *tree = creerArbre();
    printf("Arbre cree\n");
   
    Huffcode* code = creerCodes(tree);
    printf("Codes crees\n");
   
    // creation du buffer de sortie
    unsigned char *bufferDecoded = (unsigned char*) malloc(total);
   
    // decodage
    decode(tree, buffer, bufferDecoded);
    printf("Buffer decode\n");
   
    // enregistrement
    FILE *f = fopen(fnameOut, "wb");
    fwrite(bufferDecoded, 1, total, f);
    fclose(f);
    printf("Fichier enregistre\n");
   
    free(buffer);
    free(tree);
    free(code);
    free(bufferDecoded);
   
    return 1;
}

_________________
                 
Revenir en haut Aller en bas
 
Encodeur huffman en ligne de commande + source
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Programmes Panoramic en ligne de commande
» Commander IZArc en ligne de commande
» [CSS] Comment faire des ombres tout autour du tableau
» Demande d'informations complémentaires demandées par The Godfather et impossible à fournir !!!
» Ajouter des légendes à des photos

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum Le CBNA :: Informations :: Projets-
Sauter vers: