Pages

lundi 31 octobre 2011

Application interactive permettant la compression /décompression d’une image avec JAVA


La compression des données est un vaste sujet qui a fait l’objet de nombreux ouvrages et articles; elle donne lieu aujourd’hui à de nombreuses recherches en raison des enjeux économiques sous-jacents.
On se contentera donc dans cet article, d’ouvrir un champ de réflexion en indiquant la méthode la plus utilisée aujourd’hui pour compresser les données qui est la méthode HUFFMAN ,en essayant d'écrire son code en langage Java afin d'arriver en fin de compte à compresser un fichier texte, le décompresser ,compresser une image JPEG et la décompresser.




1. Cahier des charges
1-1 : Présentation
La compression de données traite la manière dont on peut réduire l'espace nécessaire à la représentation d'une certaine quantité d'information.
      Bien qu'il soit possible de compresser et décompresser des données à l'aide d'outils tels que WinZip , gzip..Il est possible de réaliser cette compression à l'aide du langage Java en utilisant une des différentes méthodes de compression.
      Ce mini projet présente une brève introduction à la compression et la décompression de données, et montre comment compresser et décompresser des données, efficace et pratique, au sein de vos applications Java en concevant un petit logiciel de compression en utilisant l'algorithme de HUFFMAN, une application interactive qui nous permet de choisir le fichier à compresser ou éventuellement à décompresser, et le résultat n’est autre que les statistiques de la compression de notre fichier.

1-1 : Besoins fonctionnels
Notre travail a pour mission de remplir les tâches suivantes :
  • La mise en place d’une fenêtre interactive.
  • La mise en place d’un menu donnant ainsi une multitude dechoix à l’utilisateur.
  • L’opération de compression d’un fichier que l’utilisateur aura choisi.
  • La décompression de ce même fichier
  • L’affichage des statistiques de compression du fichier choisi.
 1-1 : Besoins techniques
La compression selon l’algorithme de HUFFMAN repose sur un ensemble de notions incluses dans le langage de programmation Java, pour cela le seul besoin technique rencontré est la plateforme Eclipse ainsi que l’environnement Java ou le  JRE (Java Runtime Environment).

2. Les méthodes de compression
La compression de données ou codage de source est l'opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, contenant les mêmes informations, en utilisant un algorithme particulier. Il s'agit d'une opération de codage, c'est-à-dire changer la représentation de l'information, dans le but de rendre la représentation compressée plus courte que la représentation originale. La décompression est l'opération inverse de la compression. Il existe deux principaux types de la compression :

     2-1 : La compression avec pertes
La compression avec pertes ne s'applique qu'aux données perceptibles, en général sonores ou visuelles, qui peuvent subir une modification, parfois importante, sans que cela ne soit perceptible par un humain. La perte d'information est irréversible, il est impossible de retrouver les données d'origine après une telle compression. La compression avec perte est pour cela parfois appelée compression irréversible ou non conservative.

 2-1 : La compression sans pertes
La compression est dite sans perte lorsqu'il n'y a aucune perte de données sur l'information d'origine. Il y a autant d'information après la compression qu'avant. L'information à compresser est vue comme la sortie d'une source de symboles qui produit des textes finis selon certaines règles. Le but est de réduire la taille moyenne des textes obtenus après la compression tout en ayant la possibilité de retrouver exactement le message d'origine.
Parmi les algorithmes de compression presque sans perte, on retrouve : Codage RLE, Codage HUFFMAN, Codage Baudot. Nous étudierons le codage HUFFMAN pour la suite.

3. La méthode HUFFMAN
Le codage de HUFFMAN est un algorithme de compression de données sans perte élaboré par David Albert HUFFMAN, l’algorithme a été publié en 1952.
La méthode de compression HUFFMAN consiste à diminuer au maximum le nombre de bits utilisés pour coder un fragment d'information. Prenons l'exemple d'un fichier de texte : le fragment d'information sera un caractère ou une suite de caractères. Plus le fragment sera grand, plus les possibilités seront grandes et donc la mise en œuvre complexe à exécuter. L'algorithme de HUFFMAN se base sur la fréquence d'apparition d'un fragment pour le coder : plus un fragment est fréquent, moins on utilisera de bits pour le coder. Pour pouvoir compresser puis décompresser l'information, on passera donc par les étapes suivantes :
La création de la table des fréquences :
Analysons la phrase suivante : ‘compression huffman’. La table de fréquences aura donc l’allure suivante :

Lettres
Occurrences
Fréquence
C
1
5,26%
O
2
10,52%
M
2
10,52%
P
1
5,26%
R
1
5,26%
E
1
5,26%
S
2
10,52%
I
1
5,26%
N
2
10.52%
H
1
5,26%
U
1
5,26%
F
2
10,52%
A
1
5,26%
[ESPACE]
1
5,26%
Total
19
100%



































La création de l’arbre de HUFFMAN:
L'arbre de HUFFMAN est la structure données qui va nous permettre de donner un code pour chaque lettre en fonction de sa fréquence.
Afin d’aboutir à l’arbre de HUFFMAN il faut trier la table de fréquences ci-dessus par ordre croissant de fréquences.

Lettres
Occurrences
Fréquence
A
1
5,26%
C
1
5,26%
E
1
5,26%
H
1
5,26%
I
1
5,26%
P
1
5,26%
R
1
5,26%
U
1
5,26%
[ESPACE]
1
5,26%
F
2
10.52%
M
2
10,52%
N
2
10,52%
O
2
10,52%
S
2
10,52%
Total
19
100%





La construction de l’arbre est très facile : il suffit de prendre les deux nœuds les moins fréquents et de les ajouter comme fils d'un nouveau nœud qui aura pour fréquence la somme des deux.
Il suffit de réitérer cette étape jusqu'à ne plus avoir qu'un seul nœud. Le chemin de gauche sera marqué par un 0, celui de la droite par un 1.



Après élaboration, on peut déduire la nouvelle table de fréquence ainsi que le codage binaire approprié à chaque caractère.



Lettres
Occurrences
Fréquence
Codage
A
1
4
1000
C
1
4
1001
E
1
4
1010
H
1
4
1011
I
1
4
1100
P
1
4
1101
R
1
5
11100
U
1
5
11101
[ESPACE]
1
4
1111
F
2
3
000
M
2
3
001
N
2
4
0100
O
2
4
0101
S
2
3
011
Total
152
108
























4. L'analyse UML

Cette rubrique fera l’objet de l’analyse UML en présentant les différentes classes et les relations d’interactions entre elles.





5. Commentaires 
Cette rubrique fera l’objet d’une description générale des différentes classes ainsi que les packages importés les plus importés
  Class Huffman:
Cette classe est la classe principale. Elle se charge principalement de l'interface graphique et d'appeler les autres classes qui effectueront les tâches reliées à la compression et décompression éventuellement.
Class Heap:
Cette classe permet la génération d’un arbre binaire selon la méthode de Huffman.
Class FiltreExtension:
Elle permet de facilement créer un filtre pour un JFileChooser. Elle n’a aucun lien avec la compression elle même, mais permet de faciliter le choix du fichier à compresser ou à décompresser.

Class Lecteur:
Cette classe se charge de lire la fréquence des bytes dans le fichier à compresser.

Class Node:
Cette classe représente un objet Nœud. Ce Nœud représente un nœud dans l'arbre d'Huffman.

Class Statistique:
Cette classe permet de compiler certaines statistiques concernant la compression d'un fichier. Elle ne dépend d'aucune autre classe et reçoit ses valeurs par ses Setteurs appelés lors de la compression.

Class TreeOps:
Cette classe permet de créer un objet permettant certaines fonctions sur l'arbre de Huffman.

Class FileHeader:
Cette classe représente un objet contenant toutes les informations nécessaires pour décompresser le fichier. Une instance sera créée par la classe Huffman.

Class Decoder:
Cette classe fait le travail de décompression. La classe principale Huffman principale ne fait que l'appeler pour effectuer la tâche. Cette méthode se charge de reconvertir les codes Huffman vers les octets originaux.

Class Encoder:
Cette classe se charge de compresser les données et de les écrire. La classe principale Huffman ne fait que l'appeler pour effectuer la tâche de compression.
Java.io
Ce package traite essentiellement la notion de flux d’entrées/sorties. Parmi les classes qu’il englobe on trouve :
FileInputStream : Classe des flux de communication d’entrées.
BufferedInputStream, DataInputStream, ObjectInputStream : Classes des flux de traitements d’entrées.
FileOutputStream : Classe des flux de communication de sorties.
BufferedOutputStream, DataOutputStream, ObjectOutputStream : Classes des flux de traitements de sorties.
Java.awt
Ce package assure essentiellement la gestion de l’interface utilisateur. Il permet ainsi la gestion des images grâce au package awt.image, la gestion des événements utilisateurs grâce au package awt.event et bien d’autres.
Javax.swing
Swing est une librairie de classes qui permet de réaliser de véritables IHM (Interface Homme Machine), c'est-à-dire tout ce qui est Bouton, Menu, ProgressBar, frame, Label, ComboBox . . .



6. Interfaces JAVA:

Cette rubrique contient des exemples de captures d’écran prises lors de l'exécution du programme.
     · A l’exécution du programme, après avoir choisi Fichier, Compresser dans     le   menu, l’interface de l’exécution aura l’allure suivante :

·        Ci-dessous l’interface qui permet de choisir le fichier à compresser :



 ·        Après le choix du fichier, la table de fréquences est instanciée, l’arbre Huffman est construit, la table de correspondance est générée, le fichier compressé est créé et on obtient une fenêtre de choix pour la visualisation des statistiques comme suit :




·        Après confirmation, on obtient les statistiques de la compression  comme suit :






7. Codes sources:
Class Encoder:

import java.io.*;
import javax.swing.*;


public class Encoder
{
  private String buffer;
  private ObjectOutputStream oos;
  private FileHeader fileHeader;
  private long bitWritten;


  // Constructeur
  public Encoder(ObjectOutputStream os, FileHeader fh)
  {
    buffer = "";
    oos = os;
    fileHeader = fh; // On place le FileHeader


    Huffman.stats.setHeadSize(fh.getHeadLength()); // Stats
  } // Constructeur


  // Méthode writeHeader
  private void writeHeader()
  {
    try
    {
      oos.writeObject(fileHeader);
      oos.flush();
    }
    catch (IOException ex)
    {
      JOptionPane.showMessageDialog(null,
                                      "Erreur lors de l'écriture de l'entete.",
                                      "Erreur!", JOptionPane.ERROR_MESSAGE);
    }
  } // Fin de write Header


  // Méthode writeEncoded
  private void writeEncoded(String code) throws IOException
  {
    byte toWrite = 0;


    buffer += code; // On ajoute le code à la fin du buffer


    while(buffer.length() >= 8) // tant que l'on peut ecrire un byte
    {
      for(int i = 7; i >= 0; i--)
      {
        toWrite <<= 1; // on shift les bits d'une position
        if(buffer.charAt(0) == '1') // si on a 1
          toWrite++; // On additionne 1
        buffer = buffer.substring(1); // On retire un bit
      } // Fin du for (un byte a été rempli)


      oos.writeByte(toWrite); // On ecrit le byte
      toWrite = 0; // On remet le byte à 0
      //buffer = buffer.substring(8); // On retire le "byte" écrit du buffer


    } // Fin du while
  } // Fin de writeEncoded (il peut rester des bits ds buffer


  // Méthode writeEOF (vide le buffer s'il reste moins de 8 caracteres dedans
  private void writeEOF() throws IOException
  {
    byte finalByte = 0;


    for(int i = 7; i >= 0; i--)
    {
      finalByte <<= 1; // on shift les bits d'une position


      if(buffer.length() > 0) // S'il reste des infos ds le buffer, on analyse
      {
        if(buffer.charAt(0) == '1') // si on a 1
          finalByte++; // On additionne 1
        buffer = buffer.substring(1); // On réduit le buffer...
      } // Fin du if(reste des infos)
    } // Fin du for (le dernier byte est pret a etre ecrit


    oos.writeByte(finalByte); // On ecrit le dernier byte
    oos.flush(); // on s'assure qu'il ne reste rien ds le buffer de oos
    oos.close(); // On ferme le stream


  } // Fin de writeEOF


  public void encodeFile(DataInputStream dis, String[] corresp)
                                                              throws IOException
  {
    byte[] data;


    writeHeader(); // On ecrit l'entete du fichier
    // On ecrit ensuite le corp
    int capacity = dis.available();
    while(capacity > 0)
    {
      data = new byte[capacity];
      dis.read(data);


      for(int i = 0; i < data.length; i++)
        writeEncoded(convert(data[i], corresp));


      capacity = dis.available();
    } // Fin du while
    writeEOF(); // On ecrit la fin du fichier
    dis.close(); // On ferme le stream
  } // Fin de encode


  private String convert(byte info, String[] corresp)
  {
    int posi = (info < 0 ? info + 256 : info); // unsigned byte
    return corresp[posi];
  }
} // Fin de la classe
Class Decoder:

import java.io.*;
import javax.swing.*;


public class Decoder
{
  private ObjectInputStream ois;
  private DataOutputStream dos;
  private FileHeader fileHeader;
  private Node huffTree;
  private long bytesWritten; // Nb de bytes écrits
  private Node currentByteValue;


  // Constructeur
  public Decoder(ObjectInputStream is)
  {
    ois = is;
    bytesWritten = 0; // On initialise le nb de bytes ecrits à 0
  } // Fin du constructeur


  // Méthode readHeader
  private void readHeader()
  {
    try
    {
      fileHeader = (FileHeader)ois.readObject();
      // On prends le nom original et on ouvre un stream.
      dos = new DataOutputStream(new FileOutputStream(
                                                fileHeader.getOrigFileName()));
      huffTree = fileHeader.getHuffTree(); // On récupère l'arbre huffman
      currentByteValue = huffTree; // On place le noeud courant à la racine
    }
    catch (IOException ex)
    { JOptionPane.showMessageDialog(null, "Erreur: Lecture de l'entete.",
                                          "Erreur!", JOptionPane.ERROR_MESSAGE);
    }catch (ClassNotFoundException ex)
    { JOptionPane.showMessageDialog(null, "Erreur: Echec du cast.", "Erreur!",
                                                    JOptionPane.ERROR_MESSAGE);
    }
  } // Fin de readHeader


  private void decode(byte[] data) throws IOException
  {
    byte toWrite;
    int posi;


    for(int i = 0; i < data.length; i++) // pour chaque byte
    {
      byte leByte = data[i];
      for(int j = 7; j >= 0; j--) // pour chaque bit du byte
      {
        if(((leByte >>> j) & 0x1) == 0)
          // On descend vers la gauche
          currentByteValue = currentByteValue.getLeftChild();
        else
          // On descend vers la droite
          currentByteValue = currentByteValue.getRightChild();


        if(currentByteValue.isLeaf()) // Si le Node contient une valeur
        {
          posi = currentByteValue.getPosi();
          // On retourne une valeur entre -128 et 127 (putain de signed byte!!!)
          toWrite = (byte)(posi >= 128 ? posi - 256 : posi);
          dos.writeByte(toWrite); // On l'ecrit
          bytesWritten++;
          // Si le nombre de bytes écrits correspond à la longueur du fichier
          // original
          if(bytesWritten == fileHeader.getLength())
            return; // On quitte
          currentByteValue = huffTree; // On remet le pointeur à la racine
        }
      } // Fin du for(j)
    } // Fin du for(i)
  } // Fin de decode


  public void decodeFile() throws IOException
  {
    byte[] data;


    readHeader(); // On lit l'entete du fichier


    // On lit ensuite le corps
    int capacity = ois.available(); // On prends le nombre de bytes dispo
    while(capacity > 0) // tant qu'il en reste à lire
    {
      data = new byte[capacity]; // On crée le tableau de données
      ois.read(data); // On remplit le tableau
      decode(data); // On le décode et l'ecrit
      capacity = ois.available(); // On verifie s'il reste des bytes à lire
    } // Fin du while
    ois.close(); // On ferme le stream Input
    dos.flush(); // On vide le buffer interne
    dos.close(); // On ferme le stream Output
  } // Fin de decodeFile


} // Fin de la classe Decoder
Class FileHeader:

/**
 * Title: Code Huffman (Classe FileHeader)
 * Description: Cette classe représente un objet contenant toutes les
 *              informations nécessaires pour décompresser le fichier. Une
 *              instance sera créée par la classe "Huffman" (principale) et
 *              passée à la classe "Encoder" qui se chargera de l'écrire par
 *              Sérialisation.
 * Copyright: Copyright (c) 2003
 * @author Carl Fauteux
 * @version 1.0
 */
import java.io.*;
import javax.swing.*;


public class FileHeader implements Serializable
{
  private String origFileName;
  private long bytes;
  private Node huffTree;


  // Constructeur
  public FileHeader(String name, long nbBytes, Node huffTree)
  {
    origFileName = name;
    bytes = nbBytes;
    this.huffTree = huffTree;
  } // Fin du constructeur


  // Méthodes get
  public String getOrigFileName() { return origFileName; }
  public long getLength() { return bytes; }
  public Node getHuffTree() { return huffTree; }


  public long getHeadLength()
  {
    long size = -1;


    try
    {
      File temp = new File("head.tmp");
      ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(
                                                                         temp));
      oos.writeObject(this); // Sérialisation d'une copie (pour obtenir le size)
      oos.flush();
      oos.close();  // Ferme le stream
      size = temp.length();  // On lit la grosseur
      temp.delete(); // On efface le fichier temp
    }
    catch (IOException ex)
    {
      JOptionPane.showMessageDialog(null,
                              "Erreur lors du calcul de la longueur d'entete.",
                              "Erreur!", JOptionPane.ERROR_MESSAGE);
    }
    return size;  // On retourne la longueur du header
  }
}
Class TreeOps:
 class TreeOps
{
  // Max 256 Nodes au dernier niveau
  private String[] codeTable = new String[256];

  // getLeavesCodes (permet d'obtenir les codes pour chaque feuille)
  public void getLeavesCodes(Node root)
  {
    if(root.isLeaf()) // si root n'a pas de child
    {
      // On place son code dans le tableau de corresp.
      codeTable[root.getPosi()] = root.getCode();
      return;
    }

    root.getLeftChild().setCode(root.getCode() + "0"); // Code du left
    getLeavesCodes(root.getLeftChild()); // appel par recurrence

    root.getRightChild().setCode(root.getCode() + "1"); // Code du right
    getLeavesCodes(root.getRightChild()); // appel par recurrence

  } // Fin de getLeavesCodes

  // getCorrespTable
  public String[] getCorrespTable() { return codeTable; }

  //reset correspTable
  public void resetCorrespTable() { codeTable = new String[256]; }
}

Class Statistique:

public class Statistique
{
  private long initSize, headSize, finalSize;

  // Méthodes set
  public void setInitSize(long size) { initSize = size; }
  public void setHeadSize(long size) { headSize = size; }
  public void setFinalSize(long size) { finalSize = size; }

  // Méthodes get
  public long getInitSize() { return initSize; }
  public long getRawCompSize() { return (finalSize - headSize); }
  public long getHeadSize() { return headSize; }
  public long getFinalSize() { return finalSize; }

} // Fin de la classe Statistique

Class Node:

import java.io.*;

public class Node implements Serializable
{
  private Node leftChild;
  private Node rightChild;
  private int posi;
  private transient int freq; // Ne sera pas sérialisé
  private transient String code; // Ne sera pas sérialisé

  // Constructeurs
  public Node()
  {
    freq = 0;
    code = "";
    posi = -1;
  }
  public Node(int lePosi)
  {
    freq = 0;
    posi = lePosi;
    code = "";
  }

  // Pour incrémenter
  public void incrementeFreq()
  {
    freq++;
  }

  // Pour savoir si Node est une feuille
  public boolean isLeaf()
  {
    if(leftChild == null && rightChild == null)
      return true;
    else
      return false;
  } // Fin de isLeaf

  // Méthodes set
  // Placer les enfants
  public void setLeftChild(Node child) { leftChild = child; }
  public void setRightChild(Node child) { rightChild = child; }
  // Placer la fréquence
  public void setFreq(int value) { freq = value; }
  // Placer le posi
  public void setPosi(int lePosi) { posi = lePosi; }
  public void setCode(String leCode) { code = leCode; }

  // Méthodes get
  // Chercher les enfants
  public Node getLeftChild() { return leftChild; }
  public Node getRightChild() { return rightChild; }
  // chercher la fréquence
  public int getFreq() { return freq; }
  // chercher le posi
  public int getPosi() { return posi; }
  public String getCode() { return code; }
} // Fin de la classe Node

Class  Lecteur:

import java.io.*;
import javax.swing.*;

public class Lecteur
{
  private File fichier;
  private byte words[];

  // Constructeur
  public Lecteur(File file)
  {
    fichier = file;
  }

  // Lecture
  public void lireFichier(Node[] tabFreq) throws IOException
  {
    DataInputStream dis = new DataInputStream(new FileInputStream(fichier));
    int capacite = dis.available();
    while(capacite > 0)
    {
      words = new byte[capacite];
      dis.read(words);
      computeFreq(words, tabFreq);
      capacite = dis.available();
    } // Fin du while
  } // Fin de Lecture

  // Calcul des fréquences
  private void computeFreq(byte[] tab, Node[] tabFreq)
  {
    for(int i = 0; i < tab.length; i++)
    {
      // obtenir un unsigned byte
      if(tab[i] < 0)
        tabFreq[tab[i] + 256].incrementeFreq();
      else
        tabFreq[tab[i]].incrementeFreq();
    } // Fin du for
  } // Fin de computeFreq
}

Class  FiltreExtension:
/**
 * Title: Code Huffman (Classe FiltreExtension)
 * Description: FileFilter personnalisé. Réutilisé à partir du TP2 pour
 *              permettre une meilleure flexibilité des JFileChooser.
 * Copyright: Copyright (c) 2003
 * @author Carl Fauteux
 * @version 1.0
 */

import java.io.*;

public class FiltreExtension extends javax.swing.filechooser.FileFilter
{
  String extension,
         description;

  public FiltreExtension(String ext, String desc)
  {
    if(ext.indexOf(".") == -1)
      ext = "." + ext;

    extension = ext;
    description = desc;
  }

  public boolean accept(File fichier)
  {
    if(fichier.getName().endsWith(extension))
      return true;
    else if(fichier.isDirectory())
      return true;
    return false;
  }

  public String getDescription()
  {
    return description + "(*" + extension + ")";
  }
}

Class  Heap:

public class Heap
{
  private Node[] heapArray;
  private int maxSize;           // taille maximale
  private int currentSize;       // nombre d'items dans le heap

  // Constructeur
  public Heap(int mx)
  {
    maxSize = mx;
    currentSize = 0;
    heapArray = new Node[maxSize];
  }

  // Méthode getCurrentSize
  public int getCurrentSize() { return currentSize; }

  // Méthode remove()
  // Efface l'item "root" et le retourne
  public Node remove()
  {
    Node root = heapArray[0];
    heapArray[0] = heapArray[--currentSize];
    trickleDown(0);
    return root;
  }  // Fin de remove()

  public void trickleDown(int index)
  {
    int smallerChild;
    Node top = heapArray[index];
    while(index < currentSize/2)        // n'est pas sur la derniere rangée
    {
      // On prend les 2 children
      int leftChild = 2*index+1;
      int rightChild = leftChild+1;
      // on trouve le plus petit child
      if(rightChild < currentSize &&   // rightChild existe?
         heapArray[leftChild].getFreq() >
         heapArray[rightChild].getFreq())
        smallerChild = rightChild;
      else
        smallerChild = leftChild;
      // top < smallerChild?
      if(top.getFreq() < heapArray[smallerChild].getFreq())
        break;
      // switch le child vers le haut
      heapArray[index] = heapArray[smallerChild];
      index = smallerChild;
    }  // Fin du while
    heapArray[index] = top;
  }  // Fin de trickleDown()

  // trickleUp()
  public void trickleUp(int index)
  {
    int parent = (index - 1)/2; // Le parent du Node à placer
    Node temp = heapArray[index]; // Le Node à déplacer dans une var temp

    // != root et freq < que son parent
    while(index > 0 && heapArray[parent].getFreq() > temp.getFreq())
    {
      heapArray[index] = heapArray[parent]; // on descend le parent
      index = parent; // on remonte l'index
      parent = (parent - 1)/2; // nouveau parent
    } // Fin du while

    heapArray[index] = temp;
  } // Fin de trickleUp()

  // insert (insere à la fin)
  public void insert(Node newNode)
  {
    if(currentSize < maxSize)
      heapArray[currentSize++] = newNode;
  } // Fin de insert

  // insertOrdered (insere au bon endroit)
  public void insertOrdered(Node newNode)
  {
    insert(newNode);
    trickleUp(currentSize - 1);
  } // Fin de insertOrdered

  // heapify (ordonne le heap)
  public void heapify()
  {
    for(int j = currentSize/2 -1; j >= 0; j--)
      trickleDown(j);
  } // Fin de heapify
}


Class  Huffman:

import java.io.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.border.*;
import java.text.*;

public class Huffman extends JFrame implements ActionListener
{
  private final double KO_SIZE = 1024.00;
  private File file;
  private Node[] tabFreq = new Node[256];
  private String[] tabCorresp;
  private Node huffmanTree;
  protected static Statistique stats = new Statistique();

  // Composantes graphiques
  private JMenuBar menubar = new JMenuBar();

  private JMenu mnuFichier = new JMenu("Fichier");
  private JMenuItem mnuCompress = new JMenuItem("Compresser");
  private JMenuItem mnuUncompress = new JMenuItem("Décompresser");
  private JMenuItem mnuQuit = new JMenuItem("Quitter");

  private JMenu mnuAide = new JMenu("Aide");
  private JMenuItem mnuAbout = new JMenuItem("À propos...");

  private JTextArea affichage = new JTextArea(15, 30);
  private JScrollPane scroll = new JScrollPane(affichage);

  private JLabel status = new JLabel();

  // Composants invisibles
  private JFileChooser fileChooser = new JFileChooser();

  // Constructeur
  public Huffman()
  {
    fileChooser.setCurrentDirectory(new File("."));
    fileChooser.setFileSelectionMode(JFileChooser.FILES_ONLY);

    // Menu
    mnuCompress.addActionListener(this);
    mnuFichier.add(mnuCompress);

    mnuUncompress.addActionListener(this);
    mnuFichier.add(mnuUncompress);

    mnuFichier.addSeparator();
    mnuQuit.addActionListener(this);
    mnuFichier.add(mnuQuit);

    mnuAbout.addActionListener(this);
    mnuAide.add(mnuAbout);

    menubar.add(mnuFichier);
    menubar.add(mnuAide);

    setJMenuBar(menubar);
    // Fin du menu

    getContentPane().setLayout(new BorderLayout(10, 10));

    affichage.setEditable(false);
    affichage.setBackground(Color.lightGray);
    affichage.setTabSize(2);
    affichage.setLineWrap(true);
    affichage.setWrapStyleWord(true);
    affichage.setText("Compression Huffman (Carl Fauteux) v1.0");

    scroll.setViewportView(affichage);
    scroll.setBorder(new SoftBevelBorder(SoftBevelBorder.LOWERED));
    getContentPane().add(scroll, BorderLayout.CENTER);

    status.setMaximumSize(new Dimension(800, 50));
    status.setBorder(new SoftBevelBorder(SoftBevelBorder.LOWERED));
    getContentPane().add(status, BorderLayout.SOUTH);

    setTitle("Compression Huffman (Carl)");
    pack();
    setVisible(true);
    setDefaultCloseOperation(EXIT_ON_CLOSE);
  } // Fin du constructeur

  // Méthode actionPerformed
  public void actionPerformed(ActionEvent e)
  {
    if(e.getSource() == mnuCompress)
    {
      file = selectFile(false);
      // pas null?
      if(file != null)
      {
        status.setText("Compression...");
        stats.setInitSize(file.length()); // Statiftiques

        affichage.append("\n---------------------------------");
        affichage.append("\nCompression de " + file.getAbsolutePath());
        affichage.append("\n\t- Instanciation de la table de fréquences...");
        initNodeTable(tabFreq);
        affichage.append("\n\t- Lecture des fréquences...");
        getFreqTable();
        affichage.append("\n\t- Construction de l'arbre Huffman...");
        buildHuffmanTree();
        affichage.append("\n\t- Génération de la table de correspondance...");
        getCorresp();

        String fileName = file.getName();
        fileName += ".hcf";

        affichage.append("\n\t- Création du fichier compressé \"" + fileName
                                                                      + "\".");
        try
        {
          Encoder encoder = new Encoder(new ObjectOutputStream(
                                        new FileOutputStream(fileName)),
                                        new FileHeader(file.getName(),
                                        file.length(), huffmanTree));
          encoder.encodeFile(new DataInputStream(new FileInputStream(file)),
                                                 tabCorresp);
          stats.setFinalSize(new File(fileName).length());  // Statistiques
          affichage.append("\nFichier compressé avec succès!");
          status.setText("Compression réussie!");
          showStats();
        }
        catch (IOException ex)
        {
          JOptionPane.showMessageDialog(this, "Erreur lors de la compression.",
                                        "Erreur!", JOptionPane.ERROR_MESSAGE);
        }
      } // Fin de if(!null)
    } // fin de compress

    else if(e.getSource() == mnuUncompress)
    {
      file = selectFile(true);
      // pas null et fichier compressé
      if(file != null && file.getName().endsWith(".hcf"))
      {
        try
        {
          status.setText("Décompression...");
          affichage.append("\n---------------------------------");
          affichage.append("\nDécompression de " + file.getAbsolutePath());
          affichage.append("\n\t- Création du décodeur...");
          Decoder decoder = new Decoder(new ObjectInputStream(
                                                    new FileInputStream(file)));
          affichage.append("\n\t- Décodage en cours...");
          decoder.decodeFile();
          affichage.append("\n\t- Fichier décompressé!");
          status.setText("Décompression réussie!");
        }
        catch (IOException ex)
        {
          JOptionPane.showMessageDialog(this,
                                        "Erreur lors de la décompression.",
                                        "Erreur!", JOptionPane.ERROR_MESSAGE);
        }
      } // Fin de if(!null && ".hcf")
      else
        JOptionPane.showMessageDialog(this, "Mauvais format de fichier!",
                                      ".hcf requis", JOptionPane.ERROR_MESSAGE);
    } // fin de uncompress

    else if(e.getSource() == mnuQuit)
      System.exit(0);
    else if(e.getSource() == mnuAbout)
      JOptionPane.showMessageDialog(this,
                                    "Compression selon l'algorithme Huffman."
                                  + "\nAuteur: Carl Fauteux    Copyright: 2003",
                                "À propos...", JOptionPane.INFORMATION_MESSAGE);
  } // Fin de la méthode actionPerformed

  // selectFile
  private File selectFile(boolean compressed)
  {
    File fichier = null;

    if(compressed) // On prend un fichier compressé?
    {
      fileChooser.addChoosableFileFilter(new FiltreExtension("hcf",
                                                           "Compressé HCF"));
      // Si l'usager confirme
      if(fileChooser.showOpenDialog(this) == JFileChooser.APPROVE_OPTION)
      {
        // On obtient le fichier
        fichier = fileChooser.getSelectedFile();
      }
    } // fin de if(compressed)
    else //fichier non compressé
    {
      fileChooser.setFileFilter(fileChooser.getAcceptAllFileFilter());
      // Si l'usager confirme
      if(fileChooser.showOpenDialog(this) == JFileChooser.APPROVE_OPTION)
      {
        // On obtient le fichier
        fichier = fileChooser.getSelectedFile();
      }
    } // fin du else

    if(fichier != null)
    {
      //fichier existe?
      if(!fichier.exists())
      {
        JOptionPane.showMessageDialog(this, "Fichier introuvable!", "Erreur",
                                                    JOptionPane.ERROR_MESSAGE);
        return null;
      } // Fin du if(existe)
      // Lecture?
      if(!fichier.canRead())
      {
        JOptionPane.showMessageDialog(this, "Impossible de lire le fichier.",
                                          "Erreur", JOptionPane.ERROR_MESSAGE);
        return null;
      } // Fin du if(peutLire)
    } // fin du (fichier != null)

    // Fichier valide et lisible:
    return fichier; // return null si aucun fichier selectionné
  } // Fin de selectFile

  // getFreqTable()
  private void getFreqTable()
  {
    Lecteur freqReader = new Lecteur(file);

    try { freqReader.lireFichier(tabFreq); }
    catch(IOException e)
    {
      JOptionPane.showMessageDialog(this,
                                  "Erreur lors de la lecture des fréquences...",
                                  "Erreur", JOptionPane.ERROR_MESSAGE);
    }
  } // Fin de getFreqTable()

  // initNodeTable (prévient des erreurs)
  private void initNodeTable(Node[] tab)
  {
    for(int i = 0; i < tab.length; i++)
    {
        tab[i] = new Node(i);
    }
  } // Fin de initNodeTable

  // methode buildHuffmanTree
  private void buildHuffmanTree()
  {
    Heap priorityQ = new Heap(256); // PriorityQueue
    for(int i = 0; i < tabFreq.length; i++) // On insère les éléments valides
    {
      if(tabFreq[i].getFreq() > 0)
        priorityQ.insert(tabFreq[i]);
    }
    priorityQ.heapify(); // On l'ordonne

    // On crée l'arbre Huffman
    while(priorityQ.getCurrentSize() >= 2)
    {
      Node temp = new Node(); // On créé un nouveau noeud
      // On place le plus petit comme leftChild
      temp.setLeftChild(priorityQ.remove());
      // L'autre plus petit comme rightChild
      temp.setRightChild(priorityQ.remove());
      // Le fréquence du nouveau Node == somme des freq de ses children
      temp.setFreq(temp.getRightChild().getFreq()
                  + temp.getLeftChild().getFreq());
      priorityQ.insertOrdered(temp); // On insere le nouveau Node dans le PQ
    } // Fin du while

    huffmanTree = priorityQ.remove();

    priorityQ = null; // on indique au garbage collector qu'on libère priorityQ

  } // fin de buildHuffmanTree

  // getCorresp
  private void getCorresp()
  {
    TreeOps tree = new TreeOps();

    tree.getLeavesCodes(huffmanTree);
    tabCorresp = tree.getCorrespTable();

    tree = null; // on indique au GC qu'il peut s'en occuper...
  } // Fin de getCorresp

  private void showStats()
  {
    DecimalFormat df = new DecimalFormat("0.00 %");
    DecimalFormat ko = new DecimalFormat("0.00 Ko");

    int choix = JOptionPane.showConfirmDialog(this,
                                      "Voulez-vous voir les statistiques ?",
                                      "Statistiques", JOptionPane.YES_NO_OPTION,
                                      JOptionPane.QUESTION_MESSAGE);
    if(choix == JOptionPane.YES_OPTION)
    {
      JTextArea affichage = new JTextArea();
      affichage.setEditable(false);
      affichage.setTabSize(2);
      affichage.setBackground(Color.lightGray);
      affichage.setText("Statistiques de compression "
                        + ":\n------------------------");
      affichage.append("\nTaille originale : "
                        + ko.format(stats.getInitSize()/KO_SIZE));
      affichage.append("\nTaille finale (sans header) : "
                        + ko.format(stats.getRawCompSize()/KO_SIZE));
      affichage.append("\nTaille du header : "
                        + ko.format(stats.getHeadSize()/KO_SIZE));
      affichage.append("\nTaille finale (avec header) : "
                        + ko.format(stats.getFinalSize()/KO_SIZE));
      affichage.append("\n\nTaux de compression :");
      affichage.append("\n\t- Brut (sans header) : " + df.format(1.00
           - (double)(stats.getRawCompSize()) / (double)(stats.getInitSize())));
      affichage.append("\n\t- Net (avec header) : " + df.format(1.00
           - (double)(stats.getFinalSize()) / (double)(stats.getInitSize())));
      affichage.setBorder(new SoftBevelBorder(SoftBevelBorder.LOWERED));
      JOptionPane.showMessageDialog(this, affichage, "Statistiques",
                                              JOptionPane.INFORMATION_MESSAGE);
    }
  }

  // Main
  public static void main(String[] args)
  {
    new Huffman();
  } // Fin du main
} // Fin de la classe

8. Conclusion
D’après la réalisation de ce travail, nous avons pu aboutir et apporter une réponse à notre problématique qui  consiste à réussir la compression et la décompression de données en langage JAVA.
















2 commentaires:

  1. Bonne Lecture... Ce sujet est doté d'une grande importance...

    RépondreSupprimer
  2. Bonjour,
    vous pouvez mettre le projet ??

    RépondreSupprimer

Partenaires

Computers Blogs

Contactez-nous

Nom

E-mail *

Message *

Tous droits resérvés-www.exercices-corriges.com Seo Blogger Templates