Ajuda no algoritmo de Huffman

0 respostas
nois_159

Boa noite pessoal, quero passar meu código de huffman, como eu fiz, apesar, que tem um erro..
tipo, Quando entro com a palavra por exemplo: anabananadanada a saída tem que ser:
000001011
b= 000
d= 001
n= 01
a= 1

no caso a saída de meu código está saindo assim:
000100101 (não bate com a tabela)
b=000
d=100
n=10
a=1

bom, vou mostrar o meu código, se alguém souber eu agradeço muito, mais queria passar pra alguém que queira me corrigir com algo, estou precisando de luzes bem forte pra poder achar o erro.

public class Huffman {

    private int [] VetorCaracter = new int [256];
    private int Tam=0;
    PriorityQueue heap = new PriorityQueue();
    private StringTokenizer temp;
    
    public Huffman(int [] palavra){

    	VetorCaracter = palavra;
    	CriarHeap();//Criando o heap com as frequencias e letras do arquivo
    	Compactar();//Compactando o arquivo
    	Impressao();//Imprimindo a tabela de Huffman
    }

    //Metodo que cria o No para adicionar em heap
    private void CriarHeap()
    {
    	for(int i=0; i<256; i++)
        if(VetorCaracter[i]>0)
        {
           	Tam++;
    		Node Aux = new Node(i,VetorCaracter[i]);
           	heap.add(Aux);
        }
    }

    
    //Criando a arvore compacta utilizando o metodo heap
    private void Compactar(){
        System.out.println("=====================================");
	for(int i=0;i<Tam-1;i++){//Tamanho(tam)-1 para ser remoovido dois no do Heap
            Node aux = new Node();
            Node no = (Node)heap.remove();
            Node on = (Node)heap.remove();
            aux.dir=on;
            aux.esq=no;
            aux.F=no.F+on.F;
            heap.add(aux);
            //IMPRESSAO AUXILIAR
            System.out.println("|       ____|   "+aux+"   |____     |");
            System.out.println("|     ("+aux.esq+"  -  "+aux.dir+")   |");
            System.out.println("=====================================");
        }
    }

    
    private void Impressao(){
        Node no = new Node();
	no = (Node)heap.peek();
	percorre(no,"");
        impfreq();
    }
    String aux = "";
    //Metodo que percorrer a Arvore e criar a Tabela
    private void percorre(Node no,String codigo)
	{
		if(no==null)
		{
			return;
		}
		if(no.esq!=null)
		{
			//System.out.print("0 ");
			percorre(no.esq," 0 "+codigo);
		}
		if(no.dir!=null)
		{
			//System.out.print("1 ");
			percorre(no.dir," 1 "+codigo);

		}
		else
		{
                    aux+=codigo;
                    System.out.println(codigo+" = "+(char)no.L+" =  "+no.F);
                    
		}
	}
        public void impfreq(){
            System.out.print("\n frequencia binaria \n"+aux);
        }
}

public class Main 
{
    public static void main(String args[]) throws Exception {
        int i;
        int[] vetor = new int[256];
        FileReader f = new FileReader("oi.txt");
        while (f.ready()) {
            i = f.read();
            vetor[i] = vetor[i] + 1;
        }
        Huffman huffman = new Huffman(vetor);//instanciando do objeto Huffman como parametro (vetor)
    }
}


//Classe para implementar o No enquanto sendo utilizado pelo Heap
class Node implements Comparable{

    public int L,F;//(L = Letra, F = Frequencia)declarando os atributos para guardar as informacoes do no
    public Node dir;//(dir = direita)atributo que aponta para o no direito
    public Node esq;//(esq = esquerdo)atributo que aponta para o no esquerdo

    //entrada do valor chave
    public Node(int x,int y){
        this.L = x;
	this.F = y;
	this.dir = null;
	this.esq = null;
    }

    //construtor padrao

    public Node(){

    }

    //retornando o elemento
    public Node elemento(){
        return this;
    }

    //comparando as frequencias no node e colocando na posiicao correra no heap
    public int compareTo(Object o){
        Node x = (Node) o;
	return F - x.F;
    }

    //retornando as variaveis "L"(letra) e "F"(frequencia) do Node
    /*@Retornando os valores das variaveis para o Node*/
    public String toString(){
        return " =  "+F+"  "+(char)L;
    }

}

Bom é isso aí, se alguém puder me tirar essa dúvida agradeço muito!

Criado 1 de julho de 2010
Respostas 0
Participantes 1