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