Huffman compression in JAVA

Huffman.java

import java.io.*;
import java.util.*;


public class Huffman{

	/**
	* Représente un noeud pour un arbre binaire
	*
	* Peut avoir une valeur, un nombre d'occurence, un fils gauche et un fils droit
	*/
	private class Node<T>{

		public T value;
		public int occurences;
		public Node<T> left;
		public Node<T> right;

		public Node(T value, int occurences, Node<T> left, Node<T> right){
			this.value = value;	
			this.occurences = occurences;
			this.left = left;
			this.right = right;
		}

	}

	/**
	* Permet de lire un fichier texte
	*
	* @param filepath	Le chemin du fichier
	* @return 		un tableau de caractère
	*/
	public static char [] getCharacters(String filepath) throws IOException{
		int size;
		File file = new File(filepath);
		char [] a = new char[(int) file.length()];
		FileReader fr = new FileReader(file); 
		fr.read(a);   

		fr.close();
		return a;
	}

	/**
	* Permet de compter l'occurence de chaque caractères depuis un tableau de caractères
	*
	* @param chars		Les caractères
	* @return 		Un dictionnaire contenant pour chaque caractère, le nombre d'occurence
	*/
	public static HashMap<Character, Integer> countCharacters(char [] chars){
		HashMap<Character, Integer> res = new HashMap<Character, Integer>();

		for(char a : chars){
			if(!res.containsKey(a)) res.put(a, 1);
			else res.put(a, res.get(a) + 1);
		}
		return res;

	}

	/**
	* Calcule l'entropie d'un fichier en fonction d'un dictionnaire de caractères donnés
	*
	* @param occurences	Un dictionnaire avec pour chaque caractère, le nombre d'occurence
	* @return 		L'entropie finale
	*/
	public static double entropie(HashMap<Character, Integer> occurences){
		double count = 0.0;
		for(Integer i : occurences.values())
			count += (int) i;
		double res = 0;

		for(char a : occurences.keySet()){
			double proba = occurences.get(a)/count;
			res -= proba * (Math.log(proba) / Math.log(2));
		}
		return res;

	}

	public static Node<Character> createTree(HashMap<Character, Integer> occurences){
		
		Node<Character> top;
		boolean end = false;

		while(!end){
			if(occurences.size() >= 2){
				// Trouver les deux plus petits
				char small1 = occurences.keySet()[0];
				int small1_oc = occurences.get(small1);
				char small2 = occurences.keySet()[1];
				int small2_oc = occurences.get(small2);

				for(char a : occurences.keySet()){
					int oc =  occurences.get(a);
					if(a != small1){
						if(oc < small1_oc){
							small1 = a;
							small1_oc = oc;
						}	
					}else if(a != small2){
						if(oc < small2_oc){
							small2 = a;
							small2_oc = oc;
						}

					}	
				}	

				// On les enleves de la liste
				occurences.remove(small1);
				occurences.remove(small2);

				// On met le plus grand a droite
				if(small1_oc > small2_oc){
					char temp = small1;
					int temp_oc = small1_oc;
					small1 = small2;
					small1_oc = small2_oc,
					small2 = temp;
					small2_oc = temp_co;	
				}

				Node<Character> left = new Node(small1, small1_oc, null, null);
				Node<Character> right = new Node(small2, small2_oc, null, null);


			}

			if(occurences.size() < 1)
				end = true;


		}
		
		return top;

	}

	public static void main(String [] args){
		if(args.length != 1){
			System.out.println("Usage : java Huffman file");
			System.exit(1);
		}

		String file = args[0];
		char [] content = {};
		try{

			content = getCharacters(file);

		}catch(FileNotFoundException e){

			System.out.println("File does not exists");
			System.exit(1);

		}catch(IOException e){
			System.out.println("Error while reading the file");
			System.exit(1);
		}

		HashMap<Character, Integer> occurences = countCharacters(content);
		double entropie = entropie(occurences);
		System.out.println("Entropie du fichier: " + entropie);
		
		Node<Character> tree = createTree(occurences);
	
	}

}

notes.md

Analyse du problème

• FileReader : Lecture des caractères d'un fichier
  • BufferReader
• FileWriter : Ecriture
• HashMap : Key -> Value
• Interface BinaryTree

Algo de création d'un arbre

Initialisation : Une liste de noeuds (caractère -> nombre d'occurence) Algo : Recuperer les deux noeuds les plus faibles Les associés en un noeud S'arreter quand on a plus rien

TO DO

Remplacer contenu hash map par des nodes avant de commencer la création Parmis la recherche, assembler les noeuds qui ne sont pas des valeurs aussi

Run

javac Huffman.java && java Huffman note.md