Outil de compression

Voir le sujet précédent Voir le sujet suivant Aller en bas

Outil de compression

Message  sharky.fr le Dim 7 Juin 2009 - 20:31

Bonjour à tous,

J'essaye de développer un petit outil de compression. J'ai déjà écrit les
spécifications et un semblant d'analyse fonctionnelle mais j'aimerai des avis
extérieurs avant d'aller plus loin.


Huffman
Outil de compression

1. Spécifications
1.1 Introduction
1.2 Cible
1.3 L'archive
1.4 Comportement
1.4.1 Compression
1.4.2 Décompression
1.4.4 Listage d'une archive
1.5 Utilisation
1.5.1 Syntaxe
1.5.2 Options
1.6 Évolutions futures
2. Analyse fonctionnelle
2.1 Compression, décompression
2.2 Types Abstraits de Donnée
2.2.1 noeud
2.2.2 tableCodes
2.2.3 fileMin
2.2.4 arbre
A.1 L'algorithme d'Huffman


1. Spécifications

1.1 Introduction

On cherche à se doter d'un programme en ligne de commande capable de
compresser et décompresser un fichier texte en utilisant l'algorithme
d'Huffman semi-adaptatif.

1.2 Cible


L'outil de compression est avant tout un programme pour GNU/Linux. Les
archives doivent être lisible quelque soit l'architecture (32/64bits).

1.3 L'archive


L'archive créée par le programme est un fichier binaire ne contenant qu'un
seul fichier compressé. Elle se décompose en deux parties principales :
d'abord l'en-tête, ensuite les données compressées.
L'en-tête fournit les informations nécessaires à la décompression :
* un identifiant de format
* le nom du fichier original
* le poids en byte du fichier original
* la table des fréquences des bytes du fichier original

1.4 Comportement


1.4.1 Compression


Si le fichier à compresser n'existe pas, un message d'erreur est affiché et
le traitement s'arrête. De même si le poids de l'archive est plus important
que celui du fichier original, sauf si l'utilisateur précise qu'il désire
forcer la compression. Si un fichier existe déjà au chemin de l'archive il
est écrasé.

1.4.2 Décompression


Si le fichier à compresser n'existe pas, un message d'erreur est affiché et
le traitement s'arrête. De même si le format de l'archive n'est pas reconnu.
Dans le cas ou un fichier existe au chemin spécifié pour la décompression, il
est écrasé.

1.4.4 Listage d'une archive


Il est possible de lister le contenu de l'archive afin de le connaître
avant de la décompresser. Le programme ouvre src, lit l'en-tête et écrit les
informations comme suit :

Archive :
Fichier :
Taille :

1.5 Utilisation


1.5.1 Syntaxe


huff [OPTIONS] [FICHIER]

1.5.2 Options


-c, --creer dst src

Crée une nouvelle archive dst contenant src.

-x, --extraire src

Extrait le contenu de l'archive src.

-l, --liste src

Liste le contenu de l'archive src

-f, --force

Force la compression, même si celle-ci aboutit à la création d'une archive
au poids plus gros que le fichier original.

-h, --help

Affiche l'aide et se ferme.

-v, --version

Affiche la version et se ferme.

Les options -c et -x s'excluent mutuellement.
Si aucune option n'est passée, cela revient à passer -h.

1.6 Évolutions futures

* Possibilité de compresser plusieurs fichiers dans une seule archive.
* Possibilité de compresser des répertoires.
* Interface graphique.


2. Analyse fonctionnelle

2.1 Compression, décompression

La compression commence par la lecture du fichier original pour déterminer
le nombre d'occurrence de chaque byte. A partir de ces informations, il est
possible de construire l'arbre d'Huffman et de déduire le code de chaque byte.
Après la création de l'archive on écrit l'en-tête décrite en 1.3, et enfin
les données compressées.

La décompression s'effectue de façon analogue. Après avoir vérifié
l'identifiant de format, on récupère le reste de l'en-tête et on crée le
fichier original. La table des fréquence permet de recréer l'arbre d'Huffman,
de retrouver le code de chaque byte. Il reste alors à écrire les données
décompressées.

2.2 Types Abstraits de Donnée

2.2.1 noeud

Description :

Structure contenant toutes les informations relatives à un byte.

Champs :

* byte : un octet
* nbocc : un entier non signé - nombre d'occurrence de byte.
* code : un entier non signé - code du byte.
* nbbits : un entier non signé - nombre de bits du code.

2.2.2 tableCodes

Description :

Séquence de n noeuds. Chaque noeud représente un byte du fichier à compresser
ou de l'archive.

Champs :

* taille : entier non signé - nombre d'élément de la table.
* table : tableau de taille noeuds.

Propriétés :

Les noeuds sont triés par ordre alphabétique pour faciliter la recherche.

2.2.3 fileMin

Description :

File de priorité minimale contenant des noeuds. La clé est le champ nbocc.

Champs :

* capacité : entier non signé - nombre d'élément que la file peut contenir.
* taille : entier non signé - nombre d'élément de la file.
* file : tableau de noeuds - file de noeuds.

Opérations :

* construire(dr file:fileMin, table:tableCode) : err
* extraireMin(dr file:fileMin) : noeud
* inserer(dr file:fileMin, d e:noeud) : err

2.2.4 enTete

Description :

En-tête d'une archive.

Champs :

* nomFichier : chaîne - nom du fichier contenu dans l'archive.
* poids : entier non signé - taille en byte du fichier original.
* table : tableCode - la table des (byte, nb. d'occurence).

2.2.4 arbre

Description :

Arbre binaire d'Huffman.

Champs :

* e : noeud
* fg : arbre - fils gauche.
* fd : arbre - fils droit.


A.1 L'algorithme d'Huffman


L'algorithme d'Huffman est un algorithme de compression sans perte très
répandu. Il utilise un code à longueur variable et sans préfixe. C'est à dire
qu'aucun code n'est préfixe d'un autre, ce qui simplifie le travail lors de
la décompression en évitant toute ambiguïté.

On désire compresser le texte "hello". Codé sur un nombre fixe de 8 bit,
cette chaîne fait 40 bits.
On commence par calculer compter le nombre de chaque byte :

bytenb. occurrence
e1
h1
l2
o1
On construit maintenant une file de priorité minimale ayant pour clé le
nombre d'occurrence :

(e, 1) (h, 1) (o, 1) (l, 2)

On extrait les deux premiers éléments de la file, en créant un nouveau noeud,
étiqueté par la somme des nombres d'occurrences. Son fils gauche et son fils
droit sont respectivement le premier et le second élément extraits de la file.
On insère cet élément dans la file et on recommence n - 1 fois, avec n le
nombre de byte différents. On obtient l'arbre d'Huffman :

Code:

(o, 1) 2 (l, 2)
      / \
    /  \
(e, 1)    (h, 1)

Code:

(l, 2) 3
      / \
    /  \
  (o, 1)  2
        / \
        /  \
  (e, 1)    (h, 1)

Code:

            5
          / \
          /  \
    (l, 2)    3
              / \
            /  \
        (o, 1)    2
                / \
                /  \
          (e, 1)  (h, 1)
Il reste à déterminer la code de chaque feuille. Pour cela on pondère les
branches avec 0 à gauche, 1 à droite :
Code:

            5
        0 / \ 1
          /  \
    (l, 2)    3
            0 / \ 1
            /  \
        (o, 1)    2
              0 / \ 1
                /  \
          (e, 1)  (h, 1)

bytenb. occurrencecode
e1110
h1111
l20
o110
Finalement : 111 110 0 0 10 représente la chaîne "hello". On passe de 40 à 10
bits, soit un taux de compression de 25%.

Ainsi lors de la décompression, il suffit de partir de la racine de l'arbre
sachant que 0 signifie "bifurquer à gauche" et 1 "bifurquer à droite" jusqu'à
tomber sur une feuille.

A propos de la complexité de l'algorithme créant l'arbre d'Huffman. Si il est
à priori impossible de faire moins de n - 1 itérations le choix de la
file-min est important. Le plus efficace est d'utiliser un tas-min ce qui
permet de construire l'arbre en O(n.log(n)) plutôt qu'en O(n²) avec une liste chaînée triée.

Merci à ceux qui prendrons la peine de lire ce long post.

EDIT: je viens de voir que les arbres ont un mauvais rendu... Désolé mais il semblerait que je ne puisse pas mieux faire.

sharky.fr

Messages : 2
Date d'inscription : 15/02/2009
Age : 27
Localisation : Montpellier

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Outil de compression

Message  -ed- le Lun 8 Juin 2009 - 10:00

Ca me parait tout à fait correct et bien réfléchi. Je n'ai rien à ajouter.

(Désolé pour le rendu, c'est incompréhensible, car ton texte est tout à fait correct.)

_________________
C is a sharp tool !

-ed-
Admin
Admin

Messages : 289
Date d'inscription : 26/05/2008
Age : 60
Localisation : Paris 6eme arrondissement (75, France)

Voir le profil de l'utilisateur http://bien-programmer.fr

Revenir en haut Aller en bas

Re: Outil de compression

Message  sharky.fr le Lun 8 Juin 2009 - 19:59

Bonne nouvelle dans ce cas =)
Je posterai la partie conception dans le forum approprié d'ici quelques jours.

Merci !

sharky.fr

Messages : 2
Date d'inscription : 15/02/2009
Age : 27
Localisation : Montpellier

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Outil de compression

Message  Contenu sponsorisé Aujourd'hui à 15:30


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum