哈夫曼压缩与解压缩学习笔记（三）

//哈夫曼树节点

public class HuffNode  implements Comparable<HuffNode>
{
    public int value;//节点的字节值
    public int weight;//节点的权值(字节出现的频率)
    
    public int compareTo( HuffNode rhs )
    {
        return weight - rhs.weight;
    }
    
    HuffNode left;//左节点
    HuffNode right;//右节点
    HuffNode parent;//父节点
    
    HuffNode( int v, int w, HuffNode lt, HuffNode rt, HuffNode pt )
    {
        value = v; weight = w; left = lt; right = rt; parent = pt;
    }
}

//哈夫曼树

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.util.PriorityQueue;
import java.io.*;
public class HuffmanTree {

    
    public long charCountSum;
    private CharCounter theCounts;//字节计数器
    //存放哈夫曼树的所有节点,字节i对应的节点是theOndes[i]
    private HuffNode [ ] theNodes = new HuffNode[ BitUtils.DIFF_BYTES + 1 ];//256+1
    private HuffNode root;//哈夫曼树的根节点

    public HuffmanTree( )
    {
        theCounts = new CharCounter( );
        root = null;
    }
    
    public HuffmanTree( CharCounter cc )//构造函数
    {
        theCounts = cc;//注入字节计数器
        root = null;
        createTree( );//创建哈夫曼树
        charCountSum=charCountSum();//总的字节数(原文件的大小)
    }
    
    public static final int ERROR = -3;
    public static final int INCOMPLETE_CODE = -2;
    public static final int END = BitUtils.DIFF_BYTES;
    
              
    //根据字节计数器的统计结果,创建哈夫曼树,
    private void createTree( )
    {
        PriorityQueue<HuffNode> pq = new PriorityQueue<HuffNode>( );//优先队列
        
  for( int i = 0; i < BitUtils.DIFF_BYTES; i++ )//对0---256之间的每一个字节构造哈夫曼节点
            if ( theCounts.getCount( i ) > 0 )
            {
                //以字节值,字节在原文件中出现的次数(权)构建哈夫曼节点
                HuffNode newNode = new HuffNode( i,
                       theCounts.getCount( i ), null, null, null );
                theNodes[ i ] = newNode;//保存节点
                pq.add( newNode );//节点加入优先队列
            }
              
        while( pq.size( ) > 1 )//创建哈夫曼树
        {
            HuffNode n1 = pq.remove( );
            HuffNode n2 = pq.remove( );
            HuffNode result = new HuffNode( INCOMPLETE_CODE,
                                  n1.weight + n2.weight, n1, n2, null );
            n1.parent = n2.parent = result;
            pq.add( result );
        }      
        
        root = pq.element( );//返回哈夫曼树的根
    }

  
    public int[] getCode( int ch )//以整型数组的形式返回字节ch的哈夫曼编码,如{1,1,0},{1,1,1}
    {
        HuffNode current = theNodes[ ch ];//找到与ch对应的节点
        if( current == null )
            return null;
            
        String v = "";
        HuffNode par = current.parent;//ch的直接父节点
        
        while ( par != null )//找ch的父节点,一直到根
        {
            if( par.left == current )//顺带写出ch的哈夫曼码
                v = "0" + v;
            else
                v = "1" + v;
            current = current.parent;
            par = current.parent;
        }
      
        int [ ] result = new int[ v.length( ) ];
        for( int i = 0; i < result.length; i++ )
            result[ i ] = v.charAt( i ) == '0' ? 0 : 1;
            
        return result;//以整型数组的形式返回字节ch的哈夫曼编码
    } 
    
    
    public int getChar( String code )//由字节的哈夫曼编码求出此字节
    {
        HuffNode p = root;
        for( int i = 0; p != null && i < code.length( ); i++ )
            if( code.charAt( i ) == '0' )
                p = p.left;
            else
                p = p.right;
                
        if( p == null )
            return ERROR;
            
        return p.value;            
    }

    //解压缩的关键方法
//从BitInputStream流中一位一位的读(然后在树中找节点)，直到读到一个哈夫曼编码,返回哈夫曼编码对应的字节值
    public int getChar(BitInputStream bips) throws IOException
    {
    	HuffNode p = root;//哈夫曼树的根节点
    	while( p!=null)
    	{	
	    	int bit=bips.readBit();//从流中读一位
	    	if(bit==-1)
	    		return -1;
	        if(bit == 0 )//如果是0,在哈夫曼树中向左找
	        	p =p.left;
	        else
	        	p =p.right;//如果是1,在哈夫曼树中向右找
	        if(p.left==null&&p.right==null)
	        	break;
    	}   
       
        if( p == null )
            return ERROR;
    	return p.value;
    }
    
     //往压缩文件中写编码表信息:字节----字节的权值(出现的次数)
    public void writeEncodingTable( DataOutputStream out ) throws IOException
    {
    	
        for( int i = 0; i < BitUtils.DIFF_BYTES; i++ )
        {
            if( theCounts.getCount( i ) > 0 )
            {
                out.writeByte( i );//写字节
                out.writeInt( theCounts.getCount( i ) );//写字节出现的次数
            }
        }
        out.writeByte( 0 );
        out.writeInt( 0 );//写一个结束标志
        
    }
    
   //读哈夫曼编码表
    public void readEncodingTable( DataInputStream in ) throws IOException
    {
        for( int i = 0; i < BitUtils.DIFF_BYTES; i++ )
            theCounts.setCount( i, 0 );//初值全部为0
        
        int ch;
        int num;
        
        for( ; ; )
        {
            ch = in.readByte( );//读字节值
            num = in.readInt( );//字节的权值
            if( num == 0 )//遇到结束标志
                break;
            theCounts.setCount( ch, num );//将读到的结果放入字节计数器
        }
        
        createTree( );//根据字节计数器中的数据,创建哈夫曼树
        charCountSum=charCountSum();//原文件总的字节数
    }
   
    public long charCountSum()//计算原文件总的字节数
    {
    	return theCounts.charCountSum();
    	
    }

}
  

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

public class Hzip {

   //压缩文件
 public static void compress( String inFile ) throws IOException {
   //读取数据文件
		
   FileInputStream fis =new FileInputStream(inFile);//要压缩的文件
   CharCounter charCounter=new CharCounter(fis);//字节计数器,统计文件中字节出现的次数
HuffmanTree tree=new HuffmanTree(charCounter);//根据字节计数器统计的结果创建哈夫曼树,得到根节点
	
   fis.close();
	    
	
   String compressedFile = inFile + ".huf";//压缩文件的扩展名为huf       
   OutputStream fout =null;
   fout=new FileOutputStream( compressedFile );//准备要写的压缩文件
        
  DataOutputStream out=new DataOutputStream(fout);
 tree.writeEncodingTable(out);//往压缩文件中写入码表(字节--出现次数)信息,以便解压缩时恢复哈夫曼树
		
  fis=new FileInputStream(inFile);//原文件
  BitOutputStream hzout = new BitOutputStream(fout );//压缩后的文件

  int ch;
  while( ( ch = fis.read( ) ) != -1 )//从原文件中读一个一个字节地读
  {
  hzout.writeBits( tree.getCode(ch) );//写入这个字节到压缩文件,八位八位地写
  }    
    fis.close( );
     
    hzout.close( );  
    fout.close();
  }
        //解压缩文件
 public static void uncompress( String compressedFile ) throws IOException{
        String outFile;
        String extension;
        
        outFile = compressedFile.substring( 0, compressedFile.length( ) - 4 );
        extension = compressedFile.substring( compressedFile.length( ) - 4 );
        
        if( !extension.equals( ".huf" ) )//先判断要解压文件的扩展名
        {
            System.out.println( "Not a compressed file!" );
            return;
        }
        
       
        InputStream fin = new FileInputStream(compressedFile );//准备读
        DataInputStream in = new DataInputStream( fin );
          
        HuffmanTree tree=new HuffmanTree();

   //先从已压缩文件中读出码表(字节---字节出现的次数)信息,并由此信息创建哈夫曼树,
        //具体代码请参看tree.readEncodingTable(in)方法
        tree.readEncodingTable(in);

        System.out.println("总频数:"+tree.charCountSum);
        //解码，开始解码压缩文件
        BitInputStream hzin = new BitInputStream( in );
        
      OutputStream fout = new FileOutputStream( outFile );//准备输出文件
        int ch;
        long count=0;

         
//tree.getChar(hzin)方法从BitInputStream流中一位一位的读(然后在树中找节点)，
        //直到读到一个哈夫曼编码,返回此哈夫曼编码对应的字节值
        while(( ch =tree.getChar(hzin) ) != -1 )
        {
        	fout.write(ch );//将解压后的字节写入输出文件
       		count++;
    		if(count>=tree.charCountSum)
    			break;
        }
        fin.close();
        hzin.close( );
        fout.close( );
    }
    
    //大家测试吧
    public static void main( String [ ] args ) throws IOException
    {
    	String cf="D:\\temp\\7.bmp";
    	long start = System.currentTimeMillis();
    	//compress(cf);
    	uncompress(cf+".huf");
    	long end = System.currentTimeMillis();
    	System.out.println("耗时: " + (end-start)+ " 毫秒"); 
    }
    public static void main2( String [ ] args ) throws IOException
    {
        if( args.length < 2 )
        {
            System.out.println( "Usage: java Hzip -[cu] files" );
            return;
        }
        
        String option = args[ 0 ];
        for( int i = 1; i < args.length; i++ )
        {
            String nextFile = args[ i ];
            if( option.equals( "-c" ) )
                compress( nextFile );
            else if( option.equals( "-u" ) )
                uncompress( nextFile );
            else
            {
                System.out.println( "Usage: java Hzip -[cu] files" );
                return;
            }
        }
    }
}

哈夫曼压缩与解压缩学习笔记（三）