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

128kj

继续前文"哈夫曼压缩与解压缩学习笔记（二）"http://128kj.iteye.com/blog/1706818
    下面两个类主要是根据字节计数器的统计结果,创建哈夫曼树,计算字节的哈夫曼编码及由哈夫曼编码在树中找节点,往文件中写码表,读码表.
(5)HuffNode.java
//哈夫曼树节点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;    }}

(6)HuffmanTree.java

//哈夫曼树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    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;            }        }    }}
全文完。下载源码: