huffman.java

赫夫曼编译码器： 用哈夫曼编码进行通信可以大大提高信道利用率

import structure.*;
import java.util.Iterator;
import java.io.*;

public class Huffman
{
    public static void main(String args[])
    {  
        char c;  
       String r="";
	   try{
       FileReader f = null;
           f = new FileReader("C:/ToBeTran.txt");
          //System.out.println(fr); 
       BufferedReader b=new BufferedReader(f);
           //System.out.println(br);
       String Line = null;
           Line = b.readLine();
           //System.out.println(Line);
           
       while(Line!=null){
           r=Line;
           Line=null;
           b.close();
           f.close();
       }
       //System.out.println(s);
       }catch(IOException e1){
           e1.printStackTrace();
       }
       List freq=new SinglyLinkedList();
       
           // read data from input
         for(int i=0;i<=r.length()-1;i++) 
           {c = r.charAt(i);
	        if (c == '\n') break;
            // look up character in frequency list
            leaf query = new leaf(c);
            leaf item = (leaf)freq.remove(query);
            if (item == null)
            {   // not found, add new leaf
                freq.addLast(query);
            } else { // found, increment leaf
                item.frequency++;
                freq.addLast(item);
            }
            }

            
             
        // insert each character into a Huffman tree
        Iterator li = freq.iterator();
        OrderedList trees = new OrderedList();
        while (li.hasNext())
        {
            trees.add(new huffmanTree((leaf)li.next()));
        }
    
        // merge trees in pairs until one remains
        Iterator ti = trees.iterator();
        while (trees.size() > 1)
        {
            // construct a new iterator
            ti = trees.iterator();
            // grab two smallest values
            huffmanTree smallest = (huffmanTree)ti.next();
            huffmanTree small = (huffmanTree)ti.next();
            // remove them
            trees.remove(smallest);
            trees.remove(small);
            // add bigger tree containing both
            trees.add(new huffmanTree(smallest,small));
        }
        // print only tree in list
        ti  = trees.iterator();
	    Assert.condition(ti.hasNext(),"Huffman tree exists.");
        huffmanTree encoding = (huffmanTree)ti.next();
        encoding.print();
        encoding.write();
        
        
      for(int i=0;i<=4;i++)
     { String x="";
       leaf nu=(leaf)freq.removeFirst();
	   try{
       FileReader fr = null;
           fr = new FileReader("C:/hfmTree.txt");
          //System.out.println(fr); 
       BufferedReader br=new BufferedReader(fr);
           //System.out.println(br);
       String Line = null;
           Line = br.readLine();
           //System.out.println(Line);
           
       while(Line!=null){
           x=Line;
           Line=null;
           br.close();
           fr.close();
       }
       //System.out.println(s);
       }catch(IOException e1){
           e1.printStackTrace();
       }
	       try{ 
      FileWriter fw=new FileWriter("C:/hfmTree.txt");

       fw.write(x+nu.frequency);
       fw.close();
     }catch(IOException exp){
      exp.printStackTrace();
   }
     String y="";
    try{
       FileReader fr = null;
           fr = new FileReader("C:/hfmTree.txt");
          //System.out.println(fr); 
       BufferedReader br=new BufferedReader(fr);
           //System.out.println(br);
       String Line = null;
           Line = br.readLine();
           //System.out.println(Line);
           
       while(Line!=null){
           y=Line;
           Line=null;
           br.close();
           fr.close();
       }
       //System.out.println(s);
       }catch(IOException e1){
           e1.printStackTrace();
       }
	   try{ 
       FileWriter fw=new FileWriter("C:/hfmTree.txt");
       fw.write(y+nu.ch);
       fw.close();
     }catch(IOException exp){
      exp.printStackTrace();
   }
   
   }
    }
}

class leaf
{
    int frequency; // frequency of char
    char ch;	// the character

    public leaf(char c)
    // post: construct character entry with frequency 1
    {
	ch = c;
	frequency = 1;
    }
    public leaf(char c,int b)
    {
    ch=c;
    frequency=b;	
    }
    public boolean equals(Object other)
    // post: return true if leaves represent same character
    {
	leaf that = (leaf)other;
	return this.ch == that.ch;
    }
}

class huffmanTree implements Comparable
{
    BinaryTree root; // root of tree
    
    BinaryTree e=new BinaryTree("si");
    int totalWeight;     // weight of tree
    
    public huffmanTree()
    {
      root=null;
      totalWeight=1;
    }

    public huffmanTree(leaf e)
    // post: construct a leaf with associated character
    {
	root = new BinaryTree(e);
	totalWeight = e.frequency;
    }
    

    public huffmanTree(huffmanTree left, huffmanTree right)
    // pre: left and right non-null
    // post: merge two trees together and merge their weights
    {
	this.totalWeight = left.totalWeight + right.totalWeight;
	root = new BinaryTree(e.root().value(),left.root,right.root);
    }

    public int compareTo(Object other)
    // pre: other is non-null
    // post: return integer reflecting relation between values
    {
	huffmanTree that = (huffmanTree)other;
	return this.totalWeight - that.totalWeight;
    }

    public boolean equals(Object that)
    // post: return true if this and that are same tree instance
    {
	return this == that;
    }
    
    public void print()
    // post: print out strings associated with characters in tree
    {
	print(this.root,"");
    }

    protected void print(BinaryTree r, String representation)
    // post: print out strings associated with chars in tree r,
    //       prefixed by representation
    {
	if (!r.left().isEmpty())
	{   // interior node
	    print(r.left(),representation+"0"); // append a 0
	    print(r.right(),representation+"1"); // append a 1
	} else { // leaf; print encoding2
	    leaf e = (leaf)r.value();
	    System.out.println("Encoding of "+e.ch+" is "+
	       representation+" (frequency was "+e.frequency+")");

 
	}
    }
       public void write()
    // post: print out strings associated with characters in tree
    {
	 write(this.root,"");
    }
    protected void write(BinaryTree r, String representation)
    // post: print out strings associated with chars in tree r,
    //       prefixed by representation
    {
	if (!r.left().isEmpty())
	{   // interior node
	    write(r.left(),representation+"0"); // append a 0
	    write(r.right(),representation+"1"); // append a 1
	} else { // leaf; print encoding2
	    leaf e = (leaf)r.value();
	      String s="";
	   try{
       FileReader f = null;
           f = new FileReader("C:/CodeFile.txt");
          //System.out.println(fr); 
       BufferedReader b=new BufferedReader(f);
           //System.out.println(br);
       String Line = null;
           Line = b.readLine();
           //System.out.println(Line);
           
       while(Line!=null){
           s=Line;
           Line=null;
           b.close();
           f.close();
       }
       //System.out.println(s);
       }catch(IOException e1){
           e1.printStackTrace();
       }
	       try{ 
      FileWriter w=new FileWriter("C:/CodeFile.txt");
       w.write(s+e.ch+representation+'\n');
       w.close();
     }catch(IOException exp){
      exp.printStackTrace();
   }
 
	}
    }
}

/*
If a woodchuck could chuck wood!
*/
/*
    Encoding of ! is 0000 (frequency was 1)
    Encoding of a is 00010 (frequency was 1)
    Encoding of l is 00011 (frequency was 1)
    Encoding of u is 001 (frequency was 3)
    Encoding of d is 010 (frequency was 3)
    Encoding of k is 0110 (frequency was 2)
    Encoding of w is 0111 (frequency was 2)
    Encoding of I is 10000 (frequency was 1)
    Encoding of f is 10001 (frequency was 1)
    Encoding of h is 1001 (frequency was 2)
    Encoding of c is 101 (frequency was 5)
    Encoding of   is 110 (frequency was 5)
    Encoding of o is 111 (frequency was 5)
    Old length=256 new length=111 57% compression.
*/