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

继续前文"哈夫曼压缩与解压缩学习笔记（一）"
http://128kj.iteye.com/blog/1706760

(3)BitOutputStream.java
   这个类用于写压缩文件,主要方法writeBits(int[] val)用于将某一个字节的哈夫曼编码val写入文件,写的时候是一位一位先写入缓存区（写的顺序是先写缓存区的低位,后到高位),只有满八位时才flush()真正写入,如果没有八位,从下一字节中读入。

例:上面提到的文件"ASCTASCTAAAAACCTTT"，共有18个字符,压缩写时先写第一个字符A,其哈夫曼编码只有一位0,先将0写入缓存区buffer的最低位,buffer=0,再写第二个字符S,一位一位的写,其哈夫曼编码为111,此时缓存区buffer=1110,然后...如下表所示:

字符写入次序    哈夫曼编码                缓冲区buffer的二进制表示
(1)A             0                 0
(2)S             111               1110
(3)C             110               0111110
(4)T             10                0  (当buffer=10111110时,清空缓存写入
                                          out,T的编码10中的1已写入,0仍在缓存中）
(5)A             0                 00
(6)S             111               11100
(7)C             110               01111100(缓存满,这是第二次写入的数据)
(8)T             10                01
(9)A             0                 001
(10)A            0                 0001
(11)A            0                 00001
(12)A            0                 000001
(13)A            0                 0000001(已有七位)
(14)C            110               01(buffer=10000001缓存满,这是第三次写入的数据)
(15)C            110               01101
(16)T            10                0101101(已有七位)
(17)T            10                0    (buffer=10101101缓存满,这是第四次写入的数据)
(18)T            10                010  最后写入的数据

这样向压缩文件写入的字节数据是: 10111110 01111100  10000001 10101101 010

import java.io.*;

public class BitOutputStream {

 private OutputStream out;
 private int buffer;//向输出流out中写一位(bit)数据时,先写入此缓存区,只有满八位时才flush()真正写入out
    private int bufferPos;//缓存区是否满的标志

    public BitOutputStream( OutputStream os )
    {
        bufferPos = 0;
        buffer = 0;
        out = os;
    }
    
    public void writeBit( int val ) throws IOException//向缓存区写一位数据val,取0或1
    {
        buffer = setBit(buffer, bufferPos++, val );//将数据写入缓存区
       if( bufferPos == BitUtils.BITS_PER_BYTES )//缓存区满时,清空并写入out文件
            flush( );
    }
    
  public void writeBits(int [] val) throws IOException//将用数组表示的哈夫曼编码val写入文件
    {
        for( int v : val )
            writeBit( v );
    }    
    
    public void flush( ) throws IOException
    {
        if( bufferPos == 0 )
            return;
        // System.out.println(Integer.toBinaryString(buffer));
        out.write( buffer );
        bufferPos = 0;//缓存区标志复位
        buffer = 0;    //缓存区清空
    }
    
    public void close( ) throws IOException//关闭文件时,要将缓存区的数据写入文件一次
    {
        flush( );
        out.close( );
    }
    
    private int setBit( int pack, int pos, int val )//将pack的第pos位的值设置为1
    {
       // System.out.println("pack="+pack+"  pos="+pos+"   val="+val);
      //  System.out.println();
        if( val == 1 )
            pack |= ( val << pos );//将pack的第pos位的值设置为1
        return pack;
    }

    public static void main(String args[]) throws IOException{
          int[] a={0,0};
          int[] b={1,1,0};
          int[] c={1,1,1};
          int[] d={1,0};
          int[] e={0,1,0,0,1};
     BitOutputStream bo=new BitOutputStream(new FileOutputStream("d:\\java\\1.txt",true));
          bo.writeBits(a);
          bo.writeBits(b);
          bo.writeBits(c);
          bo.writeBits(d);
          bo.writeBits(e);
         bo.close();
    }
    
   
}

（4）BitInputStream.java
    此类用于解压缩,主要方法readBit()从缓存区中读一位数据,缓存区低位数据先读,高位后读,当缓存区的数据读完时,再从in中读一字节放入缓存区,如何解压缩?先要从压缩文件中读出码表(字节---频率)数据,并构建哈夫曼树,然后如下进行。

例:对于先前写入压缩文件中字节数据:10111110 01111100  10000001 10101101 010,解压过程度是这样的:
(1)先读取一字节数据10111110,放入缓存buffer中,读出它的最低位数据0,然后遍历哈夫曼树,从根节点往下找左子节点,发现0正好对应节点A;

(2)再从缓存buffer中读次低位数据1,又从哈夫曼树的根节点开始找叶子节点,1就从右找,0就左找,如果没有到叶子,再从缓存buffer中读
一位数据1,还没有到叶子节点,再读一位,这样读三位111后,就找到了对应的S,

(3)再从缓存中一位一位读三次,由110从哈夫曼树中找到C

(4)这时缓存buffer中只有一位数据1可读了,读完后再从in中读一字节01111100放入缓存,这时缓存又有数据可读了,读它的最低位0,由10从哈夫曼树中找到T,再下一步找到A,S,C,T,A,A,A,A,A,C,C,T,T,T,这样可由字节数据10111110 01111100  10000001 10101101 010 还原文件"ASCTASCTAAAAACCTTT"。

import java.io.*;

public class BitInputStream {
    private InputStream in;//文件输入流
    private int buffer;//八位的缓存区，从in读入的一个字节数据先放在这里
    private int bufferPos;//缓存区标志


    public BitInputStream( InputStream is )
    {
        in = is;
        bufferPos = BitUtils.BITS_PER_BYTES;
    }
    
    //从缓存区中读一位数据,缓存区低位数据先读,高位后读,当缓存区的数据读完时,再从in中读一字节放入缓存区
    public int readBit( ) throws IOException
    {
        if ( bufferPos == BitUtils.BITS_PER_BYTES )
        {
            buffer = in.read( );//从输入流中读一个字节
           // System.out.println(Integer.toBinaryString(buffer));
            if( buffer == -1 )
                return -1;
            bufferPos = 0;
        }
       // System.out.println("buffer="+buffer);
        return getBit( buffer, bufferPos++ );    
    }
    
    public void close( ) throws IOException
    {
        in.close( );
    }
    
    private static int getBit( int pack, int pos )//获取pack的二进制表示中的第pos位上的数值.
    {
        return ( pack & ( 1 << pos ) ) != 0 ? 1 : 0;
    }
    
    public static void main(String args[]) throws IOException{
       FileInputStream is=new FileInputStream("d:\\java\\1.txt");
       BitInputStream bi=new BitInputStream(is);
       while(true){
         int b=bi.readBit();
         if(b==-1) break;
          System.out.print(b+"  ");
       }
      
   }

    
}

末完待续。。。。。。