LZW.java

共7个文件:

1:

package LZW;
/*
* LZW.java
*
* Created on 01 Dec 2005
*
* Implementation of LZW compression/decompression algorithm
*/

import java.io.* ;

/**
*
*
* @author   Moshe Fresko
* @course Algorithmic Programming 1
* @exercise 3
*/

public class LZW implements Compression
{
boolean stopped = false ;

Dict dict ;
   // The bits that should be written for each code
int numOfBits ;
   // The previous string that we should remember
   // in order to insert into the dictionary
final ByteArray emptyBA = new ByteArray() ;
ByteArray w=emptyBA ;
   // Constructor gets the number of bits to be written for each code
public LZW()
{
   numOfBits = 12 ;
    // Create a new Limited Dictionary
    // For maximum of 2^bits entries
   dict = new LimitedDict(1<<numOfBits) ;
    // Add all ascii characters to the dictionary
   for (int i=0;i<256;++i)
    dict.add(new ByteArray((byte)i)) ;
}
   // Encodes the next character.
   // If there is a code generated returns it.
   // If not returns -1.
int encodeOneChar(int n) {
   byte c = (byte) n ;
   ByteArray nw = w.conc(c) ;
   int code = dict.numFromStr(nw) ;
    // if it exists then we continue to search for a longer string
   if (code!=-1) {
    w = nw ;
    return -1 ;
   } else {
    dict.add(nw) ;
    nw = w ;
    w = new ByteArray(c) ;
    return dict.numFromStr(nw) ;
   }
}
   // If there is something left in w, returns its code
int encodeLast() {
   ByteArray nw = w ;
   w = emptyBA ;
   return dict.numFromStr(nw) ;
}
   // Write the code in bits into output stream
void writeCode(OutputStream os, int code) throws IOException
{
   for (int i=0;i<numOfBits;++i) {
    os.write(code&1) ;
    code /= 2 ;
   }
}

int readCode(InputStream is) throws IOException
{
   int num = 0 ;
   for (int i=0;i<numOfBits;++i) {
    int next = is.read() ;
    if (next<0)
     return -1 ;
    num += next<<i ;
   }
   return num ;
}
   // We need to call the close() method of BitOutputStream,
   // but without closing the encompassing OutputStream
private class UnClosedOutputStream extends FilterOutputStream {
   public UnClosedOutputStream(OutputStream os)
    { super(os) ; }
     public void write(byte b[], int off, int len) throws IOException
      { out.write(b,off,len) ; }
      // Does not close anything
   public void close() throws IOException
    { }
}

public void compress(InputStream is, OutputStream os) throws IOException {
   os = new BitOutputStream(new UnClosedOutputStream(os)) ;
   int next ; // next input character
   int code ; // next code generated
   while ((next=is.read())>=0) {
    if (stopped)
     break ;
    code = encodeOneChar(next) ;
    if (code>=0)
     writeCode(os,code) ;
   }
   code = encodeLast() ;
   if (code>=0)
    writeCode(os,code) ;
     os.close() ;
}

ByteArray decodeOne(int code) {
    // Either "ABA" or null, w="AB"
   ByteArray str = dict.strFromNum(code) ;
   if (str==null) {
    str = w.conc(w.getAt(0)) ;
    dict.add(str) ;
   } else
    if (! w.isEmpty())
     dict.add(w.conc(str.getAt(0))) ;
             w = str ;
   return w ;
}

public void decompress(InputStream is, OutputStream os) throws IOException {
   is = new BitInputStream(is) ;
   ByteArray str ; // Next entry
   int code ;   // Next code to be read
   while ((code=readCode(is))>=0) {
    if (stopped)
     break ;
    str = decodeOne(code) ;
    os.write(str.getBytes()) ;
   }
}

public void stop()
   { stopped = true ; }

        public static void main(String args[]){
           LZW lzw=new LZW();
           try{
             lzw.compress(new FileInputStream("D:/des_test/src/LZW/TEST.PNG"),new FileOutputStream("D:/des_test/src/LZW/test.lzw"));
           //lzw.decompress(new FileInputStream("D:/des_test/src/LZW/test.lzw"),new FileOutputStream("D:/des_test/src/LZW/TEST1.PNG"));
             //lzw.compress(new FileInputStream("LZW.JAVA"),new FileOutputStream("lzw.lzw"));
             //lzw.decompress(new FileInputStream("lzw.lzw"),new FileOutputStream("lzw1.java"));
           }catch(Exception e){

           }
        }
}

==========

2.

package LZW;
// Keeps a limited sized dictionary
public class LimitedDict extends Dict {
int maxSize ;
LimitedDict(int maxSize)
   { this.maxSize = maxSize ; }
public void add(ByteArray str)
   { if (size()<maxSize)
    super.add(str) ; }
}

==============

3.

package LZW;
import java.util.* ;

// The dictionary
public class Dict {
   // mp keeps : Word => Index
   // ls keeps : Index => Word
Map mp = new HashMap() ;
List ls = new ArrayList() ;
   // Adds an element into the dictionary
public void add(ByteArray str)
   { mp.put(str,new Integer(ls.size())) ;
     ls.add(str) ;
     }
   // Gets the number for the given string.
   // If it does not exist, returns -1
public final int numFromStr(ByteArray str)
   { return ( mp.containsKey(str) ?
        ((Integer)mp.get(str)).intValue() :
        -1 ) ; }
   // Gets the string for the given number
   // If the number does not exist, return null
public final ByteArray strFromNum(int i)
   { return ( i<ls.size() ?
        (ByteArray) ls.get(i) :
        null ) ; }
public final int size()
   { return ls.size() ; }
} ;

================

4.

package LZW;
/*
* Compression.java
*
* Created on 01 Dec 2005
*
* Interface for any compression algorithm
*/

import java.io.* ;

/**
*
* @author   Moshe Fresko
* @course Algorithmic Programming 1
* @exercise 2
*/

interface Compression
{
   // Gets the input from the Input Stream
   // and writes the encoded code into Output Stream
void compress(InputStream inp, OutputStream out) throws IOException ;
   // Gets the already encoded input stream
   // Decodes it and writes into output stream
void decompress(InputStream inp, OutputStream out) throws IOException ;

}

==============

5.

package LZW;
// ByteArray is used instead of String,
// so that we will have no conversion from/to char,
// Conversion to (char) from int is not recognized for some specific characters
public class ByteArray {
   // The single member variable is a byte array kept inside, it is immutable
final byte[] arr ;
   // Constructor with a byte arrays will clone it, since we dont want access from outside
ByteArray(byte[] b)
   { arr = (byte[]) b.clone() ; }
   // Default Constructor, 0 length array
ByteArray()
   { arr = new byte[0] ; }
   // Constructor with a single byte
ByteArray(byte b)
   { arr = new byte[] { b } ; }
   // For the hash-table we need this
public boolean equals(Object o)
   { ByteArray ba = (ByteArray) o ;
     return java.util.Arrays.equals(arr,ba.arr) ; }
   // For the hash-table we need to give a hash code. (Change must be done for a better hash code)
public int hashCode()
   { int code = 0 ;
     for (int i=0;i<arr.length;++i)
    code = code*2+arr[i] ;
     return code ; }
   // returns the size of the byte array
public int size()
   { return arr.length ; }
   // returns the byte in a given position
byte getAt(int i)
   { return arr[i] ; }
   // concatenates another byte array into this one,
   // and returns the concatenation in another newly created one. (ByteArray is immutable)
public ByteArray conc(ByteArray b2)
   { int sz = size()+b2.size() ;
     byte[] b = new byte[sz] ;
     for (int i=0;i<size();++i) b[i]=getAt(i) ;
     for (int i=0;i<b2.size();++i) b[i+size()]=b2.getAt(i) ;
     return new ByteArray(b) ; }
   // Concatenates a byte into this ByteArray.
   // The result is returned in a new ByteArray. (ByteArray is immutable)
public ByteArray conc(byte b2)
   { return conc(new ByteArray(b2)) ; }
   // Returns a byte array of the copy of the inner byte arrays
public byte[] getBytes()
   { return (byte[]) arr.clone() ; }
   // Checks if it is zero length
public boolean isEmpty()
   { return size()==0 ; }
   // Drops the last character and returns it
public byte getLast()
   { return arr[size()-1] ; }
public ByteArray dropLast()
   { byte[] newarr = new byte[size()-1] ;
     for (int i=0;i<newarr.length;++i)
      newarr[i] = arr[i] ;
     return new ByteArray(newarr) ; }
public String toString()
   { return new String(arr) ; }
}

==========

6.

package LZW;
/*
* BitOutputStream.java
*
* Created on 01 Dec 2003
*/

import java.io.* ;

/**
*
* @author   Moshe Fresko
* @course Algorithmic Programming 1
* @exercise 2
*/

public class BitOutputStream extends FilterOutputStream
{
class BitManager {
   int   buf = 0 ;
   int   cnt = 0 ;
    // Returns -1 if there is nothing yet to be written
   int   writeOne(int next)
    { int ret = -1 ;
     buf=buf*2+next ;
     cnt++ ;
     if (cnt==7) {
      cnt = 0 ;
      ret = buf ;
      buf = 0 ;
     } else {
      ret = -1 ;
     }
     return ret ; }
    //
   int   writeLast()
    { int x=0 ;
     for (int i=0;i<7-cnt;++i)
      x=x*2+1 ;
     for (int i=7-cnt;i<8;++i)
      x=x*2 ;
     return buf|x ; }
}
BitManager bitManager = new BitManager() ;
      /** Constructor creates a new instance of BitOutputStream,
        A decarotor to OutputStream, via FilterOutputStream */
public BitOutputStream(OutputStream os)
   { super(os) ; }
      /** Writes a single bit into the included stream.
        Although the input is a single bit, it is given as an int.
        If it is non-zero, it is threated as 1. */
public void write(int i) throws IOException
   { int x = bitManager.writeOne(i>=1?1:0) ;
    if (x>=0)
     out.write(x) ; }
   /** Writes a list of bits given in the byte array as 0's and 1's */
public void write(byte[] arr) throws IOException
   { write(arr,0,arr.length) ; }

public void write(byte[] arr, int off, int len) throws IOException
   { int clen = 0 ;
    for (int i=0;i<len;++i) {
     int x = bitManager.writeOne(arr[off+i]) ;
     if (x>=0)
      arr[off+(clen++)]=(byte)x ;
    }
    out.write(arr,off,clen) ; }
      /** Closes the included stream. Before closing flushes the necessary buffer.
       Flush writes the partial byte kept in the internal buffer. */
public void close() throws IOException
   { out.write(bitManager.writeLast()) ;
     out.close(); }
   // "Main" reads a file in the form of characters of '0's and '1's
   // and prints them as bits into another file as a BitStream

public static void main(String[] args)
{
   if (args.length<2)
   {
    System.out.println("Usage: java BitOutputStream FromFile ToFile") ;
    System.out.println("where 'FromFile' includes characters of '0' and '1'") ;
    System.out.println("and they are written as bits into 'ToFile'") ;
    System.exit(1) ;
   }

   try {
    InputStream is = new BufferedInputStream(new FileInputStream(args[0])) ;
    OutputStream os = new BitOutputStream(new BufferedOutputStream(new FileOutputStream(args[1]))) ;
    int next ;
    while ((next=is.read())>=0) {
     char ch = (char) next ;
     if (ch=='0' || ch=='1')
      os.write((int)(ch-'0')) ;
    }
    is.close() ;
    os.close() ;
   } catch (FileNotFoundException fnfe) {
    System.out.println(args[0]+" file not found") ;
    System.exit(1) ;
   } catch (IOException ioe) {
    System.out.println("Error in reading file "+args[0]+" or writing file "+args[1]) ;
    System.exit(1) ;
   }
}
}

===========

7.

package LZW;
/*
* BitInputStream.java
*
* Created on 08 Dec 2005
*/

import java.io.* ;

/**
*
* @author   Moshe Fresko
* @course Algorithmic Programming 1
* @exercise 1
*/

public class BitInputStream extends FilterInputStream
{

      /** Constructor creates a new instance of BitInputStream,
        A decarotor to InputStream, via FilterInputStream */
public BitInputStream(InputStream is)
   { super(is) ; }

class BitManager {
   // Buffer to keep max of 7 bits (one byte)
   private int[] buf = new int[8] ;
   // Counter showing the bit number we are reading now
   private int cnt = -1 ;
   // If we are at the end of the stream
   boolean atTheEnd()
    { return ((buf[7]==1)&&(cnt<0)) ; }
   // Set the flag for the end of stream
   void setTheEnd()
    { buf[7]=1; cnt=-1; }
   // No more buffer, means we need to read the next byte
   boolean noMoreBuffer()
    { return cnt<0 ; }
   // set the buffer
   void setNext(int next)
    { // put the bits of the byte into the array
     for (cnt=0; cnt<8; ++cnt) {
      buf[cnt] = next % 2 ;
      next /= 2 ;
     }
     // if this was the last byte
     if (buf[7]==1) {
      for (cnt=7;cnt>=0;cnt--)
       if (buf[cnt]==0)
        break ;
      cnt-- ;
     } else {
      cnt = 6 ;
     }
    }
   // get the next bit
   int getNext()
    {   return buf[cnt--] ; }
   // how many left
   int left()
    { return cnt+1 ; }

} ;
BitManager bitManager = new BitManager() ;

byte[] tempBuf = null ;
int     tempBufPtr = 0 ;
int    tempBufLen = 0 ;
private int readNextByte() throws IOException
   { int val = -1 ;
    if (tempBufPtr==tempBufLen)
     val = super.read() ;
    else {
     byte b = tempBuf[tempBufPtr++] ;
     if ((b&0x80)>0)
      val = ((int)(b&0x7F))|0x80 ;
     else
      val = b ;
    }
    return val ;
   }
      /** Reads a single bit from the included stream.
       Returns either 1 or 0, and at the end of stream returns -1. */
public int read() throws IOException {
    // If we are already at the end, return -1
   if (bitManager.atTheEnd())
    return -1 ;
    // If we are in the last bit, then refill the buffer
   if (bitManager.noMoreBuffer()) {
    int i = readNextByte() ;
    if (i<0)
     bitManager.setTheEnd() ;
    else
     bitManager.setNext(i) ;
    return read() ;
   }
    // Return the specific bit
   return bitManager.getNext() ;
}

   /** Reads a list of bits given in the byte array as 0's and 1's*/
public int read(byte[] arr) throws IOException
   { return read(arr,0,arr.length) ; }

public int read(byte[] arr, int off, int len) throws IOException
{ int bytelen = ( (len-bitManager.left()) / 7 ) ;
   tempBuf = new byte[bytelen] ;
   tempBufLen = in.read(tempBuf) ;
   tempBufPtr = 0 ;
   for (int i=0;i<len;++i) {
    int next = read() ;
    if (next<0)
     return i ;
    arr[off+i]=(byte) next ;
   }
   return len ;
}

public static void main(String[] args)
{
   if (args.length<2)
   {
    System.out.println("Usage: java BitInputStream FromFile ToFile") ;
    System.out.println("where 'FromFile' is a file to be open as a Bit Stream") ;
    System.out.println("and they are written as characters of '0's and '1's") ;
    System.out.println("every line having one char") ;
    System.exit(1) ;
   }
   try {
    InputStream is = new BitInputStream(new BufferedInputStream(new FileInputStream(args[0]))) ;
    PrintWriter os = new PrintWriter(new OutputStreamWriter(new FileOutputStream(args[1]))) ;
    int next ;
    while ((next=is.read())>=0)
     os.println(next) ;
    is.close() ;
    os.close() ;
   } catch (FileNotFoundException fnfe) {
    System.out.println(args[0]+" file cannot be opened") ;
    System.exit(1) ;
   } catch (IOException ioe) {
    System.out.println("Error in reading file "+args[0]+" or writing file "+args[1]) ;
    System.exit(1) ;
   }
}
}