huffman.java

lzw huffman coding .

/*
 *Aluno ANDRE LUIS DURAO ABDO
 *MATRICULA: 283999
 *DATA:23/03/2006
 *CLASSE Huffman
 *Lab04 (Tema: Compressao)
 */

import java.io.*;

class Huffman {

	public static void main (String[] args) throws IOException {
		if (!args[0].equals("")){
			encode(args[0]);
			decode("output.dat");
		}
	}
	
	private static void encode (String txt) {
		int[] Nsimbolos = new int[256];
		int atual;
		try {
			FileReader in = new FileReader(txt);
			DataOutputStream out = new DataOutputStream(new FileOutputStream("output.dat"));
			while ((atual = in.read()) != -1)
				Nsimbolos[atual]++;
			in.close();
			String[] codigos = new String[256];
			codigos = gera_codigo(Nsimbolos);
			for (int i = 0; i < 256; i++)
				out.writeByte((byte) Nsimbolos[i]);
			//reinstancia in, volta para inicio do arq
			in = new FileReader(txt);
			StringBuffer bits = new StringBuffer();
			while ((atual = in.read()) != -1)
				bits.append(codigos[atual]);
			for (int cont = 0; cont < bits.length(); cont++) {
				String temp = "";
				for (int h = 0; h < 8; h++)
					if (cont < bits.length())
						temp += bits.charAt(cont++);
				out.writeByte((byte) Integer.parseInt(temp));
			}
			in.close(); out.close();
			System.out.println("Arquivo de texto comprimido para output.dat");
		} catch (FileNotFoundException fnfE) {
			System.out.println("Arquivo nao encontrado.");
		} catch (IOException IOE) {
			System.out.println("Excecao IO.");
		}
	}
	
	private static String[] gera_codigo (int[] Nsimbolos) {
		int total = 0;
		double[] frequencias = new double[256];
		for (int i = 0; i < 256; i++)
			total += Nsimbolos[i];
		for (int i = 0; i < 256; i++) {
			frequencias[i] = Nsimbolos[i];
			frequencias[i] /= total;
		}
		HuffmanNode[] Tree = criaNodos(frequencias);
		int marcaInicio = 0;
		for (int i = 255; i > 0; i--) {
			if (Tree[i].getFrequency() == 0.0) {
				marcaInicio = i + 1;
				i = 0;
			}
		}
		HuffmanNode[] aux = new HuffmanNode[255];
		int cont = 0;
		while (marcaInicio < 255) {
			HuffmanNode temp = new HuffmanNode(Tree[marcaInicio].getFrequency() + 
				Tree[marcaInicio+1].getFrequency(),Tree[marcaInicio],Tree[marcaInicio+1]);
			aux[cont++] = Tree[marcaInicio];
			aux[cont++] = Tree[marcaInicio+1];
			Tree[marcaInicio] = new HuffmanNode(0.0,null,null);
			Tree[marcaInicio+1] = temp;
			marcaInicio++;
			ordena(Tree);
		}
		String[] codigos = new String[256];
		codigos = encontraCodigos(Tree[marcaInicio],"",codigos);
		return codigos;
	}

	private static String[] encontraCodigos (HuffmanNode nodo, String codigo, String[] codigos) {
		if (nodo.left == null && nodo.right == null)
			codigos[nodo.getSymbol()] = codigo;
		if (nodo.left != null)
			codigos = encontraCodigos(nodo.left,codigo + "0",codigos);
		if (nodo.right != null)
			codigos = encontraCodigos(nodo.right,codigo + "1",codigos);
		return codigos;
	}

	private static void ordena (HuffmanNode[] num) {
		for (int i = 255; i >= 1; i--) {
			for (int j = 0; j < i; j++) {
				if (num[j].getFrequency() > num[j+1].getFrequency()) {
					HuffmanNode aux1;
					aux1 = num[j+1]; num[j+1] = num[j]; num[j] = aux1;
				}
			}
		}
	} // fim ordena

	private static HuffmanNode[] criaNodos (double[] frequencias) {
		HuffmanNode[] Tree = new HuffmanNode[256];
		for (int i = 0; i < 256; i++)
			Tree[i] = new HuffmanNode(i, frequencias[i]);
		ordena(Tree);
		return(Tree);
	}

	private static void decode (String nomearq) {
		int atual;
		try {
			FileInputStream tr = new FileInputStream(nomearq);
			DataInputStream fr = new DataInputStream(tr);
			FileWriter fw = new FileWriter("input.txt");
			int[] Nsimbolos = new int[256];
			for (int i = 0; i < 256; i++)
				Nsimbolos[i] = (int) fr.readByte();
			String[] codigos = new String[256];
			codigos = gera_codigo(Nsimbolos);
			StringBuffer bits = new StringBuffer();
			while ((atual = fr.read()) != -1) {
				int temp = (int) atual;
				for (int i = 0; i < 8; i++)
					bits.append((int) getBit(temp,i));
			}
			String code = "";
			for (int cont = 0; cont < bits.length(); cont++) {
				code += bits.charAt(cont);
				for (int i = 0; i < 256; i++) {
					if (codigos[i] != null) {
						if (code.equals(codigos[i])) {
							fw.write((char) i);
							code = "";
						}
					}
				}
			}
			fr.close(); fw.close(); tr.close();
			System.out.println("Arquivo de texto decomprimido para input.txt");
		} catch (FileNotFoundException fnfE) {
			System.out.println("Arquivo nao encontrado.");
		} catch (IOException IOE) {
			System.out.println("Excecao IO.");
		}
	} 

	private static int getBit (int n, int pos) {
		return ( (n & (1 << pos) ) >> pos );
	}

}