Java Huffmen Code as per document.

profilenihil.khagram
proj-4.zip
Home>Computer Science homework help>Java Huffmen Code as per document.

BitInputStream.java

BitInputStream.java

import  java . io . * ;

public   class   BitInputStream   implements   AutoCloseable
{
   private   byte []  bytes ;
   private   int  index ;

   public   BitInputStream ( File  in )   throws   FileNotFoundException ,   IOException   {
     this ( new   FileInputStream ( in ));
   }

   public   BitInputStream ( FileInputStream  fileInputStream )   throws   IOException   {
     DataInputStream  in  =   new   DataInputStream ( fileInputStream );
     int  size  =  in . available ();
     this . bytes  =   new   byte [ size ];
     this . index  =   0 ;
    in . read ( bytes );
    in . close ();
   }

   public   byte []  allBytes ()   {
     return  bytes ;
   }

   public   int  readBit ()   throws   IOException   {
     byte  b  =  bytes [ index  /   8 ];
     int  offset  =  index  %   8 ;
     final   int  mask  =   1   <<   7 ;
     ++ index ;
     return   ( b  &   ( mask  >>>  offset ))   ==   0   ?   0   :   1 ;
   }

   public   int  readByte ()   throws   IOException   {
     byte  value  =   0 ;
     for   ( int  i  =   0 ;  i  <   8 ;   ++ i )   {
      value  <<=   1 ;
      value  |=  readBit ();
     }
     return  value  &   0xFF ;
   }
  
   public   int  readInt ()   throws   IOException   {
     int  value  =  readByte ();
    value  =   ( value  <<   8 )   |  readByte ();
    value  =   ( value  <<   8 )   |  readByte ();
    value  =   ( value  <<   8 )   |  readByte ();
     return  value ;
   }

   public   void  close ()   throws   IOException   {
     // intentionally left blank
   }
}

BitOutputStream.java

BitOutputStream.java

import  java . io . * ;
import  java . util . BitSet ;
import  org . instructures . * ;

public   class   BitOutputStream   implements   AutoCloseable
{
   private   final   DataOutputStream  out ;
   private   final   BitSet  bits ;
   private   int  index ;

   public   static   void  main ( String []  args )   {
     ArgsParser  parser  =   ArgsParser . create ( "java BitOutputStream" );
     Operand < File >  OUT  =   Operand . create ( File . class ,   "OUT" );
    parser . requiredOperand ( OUT );
     ArgsParser . Bindings  settings  =  parser . parse ( args );

     try   ( BitOutputStream  out  =   new   BitOutputStream ( settings . getOperand ( OUT )))   {
       // use `xdd testfile; xdd -b testfile` to examine contents out
       if   ( "test1" . equals ( out . toString ()))   {
        out . writeByte ( 10 );
        out . writeBit ( 1 );
        out . writeByte ( - 1 );
        out . writeBit ( 1 );
        out . writeBit ( 0 );
        out . writeBit ( 0 );
        out . writeBit ( 0 );
        out . writeBit ( 1 );
        out . writeInt ( 42 );
        out . writeBit ( 1 );
        out . writeBit ( 0 );
        out . writeBit ( 1 );
       }
      out . writeInt ( - 1 );
      out . writeInt ( 7 );
      out . writeInt ( 0x1F1F1F1F );
      out . writeByte ( 10 );
      out . writeBit ( 1 );
      out . writeBit ( 0 );
      out . writeBit ( 0 );
      out . writeBit ( 1 );
      out . writeBit ( 1 );
      out . writeBit ( 1 );
      out . writeBit ( 1 );
     }   catch   ( Exception  e )   {
       System . err . printf ( "Error: %s%n" ,  e . getMessage ());
       System . exit ( 1 );
     }
   }

   public   BitOutputStream ( File  out )   throws   FileNotFoundException   {
     this ( new   FileOutputStream ( out ));
   }

   public   BitOutputStream ( FileOutputStream  out )   {
     this . out  =   new   DataOutputStream ( out );
     this . bits  =   new   BitSet ();
     this . index  =   0 ;
   }

   /*
   * How many bits have been sent to the output so far.
   */
   public   int  tally ()   {
     return  index ;
   }

   /*
   * How many bytes are needed to hold a `tally` number of bits.
   */
   public   int  bytesNeeded ()   {
     return   ( tally ()   +   7 )   /   8 ;
   }

   /*
   * Writes out the given bit as either 0 or 1.
   */
   public   void  writeBit ( int  b )   throws   IOException   {
     boolean  bitValue  =   ( b  !=   0 );
     int  pos  =  leftRightIndex ( index ++ );
    bits . set ( pos ,  bitValue );
   }

   /*
   * Writes out only the least significant byte of the given integer
   * value `v`.
   */
   public   void  writeByte ( int  v )   throws   IOException   {
     for   ( int  i  =   7 ;  i  >=   0 ;   -- i )   {
       this . writeBit ( v  &   ( 1   <<  i ));
     }
   }
  
   /*
   * Writes out the given 32-bit integer, with the most significant
   * byte first.
   */
   public   void  writeInt ( int  v )   throws   IOException   {
    writeByte ( v  >>>   ( 3   *   8 ));
    writeByte ( v  >>>   ( 2   *   8 ));
    writeByte ( v  >>>   ( 1   *   8 ));
    writeByte ( v  >>>   ( 0   *   8 ));
   }

   public   void  close ()   throws   IOException   {
    writeByte ( 0 );
    writeByte ( - 1 );
     byte []  contents  =  bits . toByteArray ();
    out . write ( contents ,   0 ,  contents . length  -   2 );
    out . close ();
   }

   private   static   int  leftRightIndex ( int  i )   {
     return   ( i  &   ~ 7 )   +   ( 7   -   ( i  %   8 ));
   }
}

Huffman Codes.docx

Huffman Codes

You will turn in one file: HuffmanCodes.java, which can encode and decode files using Huffman codes. The program has the following command-line interface:

$ java HuffmanCodes --help

Usage: java HuffmanCodes OPTIONS IN OUT

Encodes and decodes files using Huffman's technique

-e, --encode encodes IN to OUT

-d, --decode decodes IN to OUT

--show-frequency show the frequencies of each byte

--show-codes show the codes for each byte

--show-binary show the encoded sequence in binary

-h, --help display this help and exit

· When the encode option is used, the program will read in the file specified by the IN operand and create the file specified by the OUT operand. Depending on the nature of the input file, the output file could be smaller than the original input.

· When the decode option is used, the program will read in the file specified by the IN operand and interpret it as the output from the encode operation. If the given file represents a valid encoding, the original encoding for the file will be restored in a new file, specified by the OUT operand.

Frequency Counting

The show-frequency option assists debugging. When it is set, the frequency table computed from the input file is output during the encoding process. For example, if the input file is the characters "mississippi" (without a newline), then the output would be:

$ echo -n "mississippi" > mi.txt

$ java HuffmanCodes --encode mi.txt mi.encoded --show-frequency

FREQUENCY TABLE

'm': 1

'p': 2

'i': 4

's': 4

input: 11 bytes [88 bits]

output: 12 bytes [header: 71 bits; encoding: 21 bits]

output/input size: 109.0909%

The first column is each byte of the input file displayed in the format of a Java character literal (e.g., the newline character would be represented as '\n'). The second column is the count (in decimal) for the number of times that byte's value is present in the input file.

The table is ordered from least frequent to most frequent, with ties broken by each byte's value.

Generating Prefix-Free Codes

Like the show-frequency option, the show-codes option also assists debugging. It displays the variable-length Huffman codes for each value, using a sequence of "0" and "1" characters.

$ java HuffmanCodes --encode mi.txt mi.encoded --show-codes

CODES

"0" -> 's'

"11" -> 'i'

"100" -> 'm'

"101" -> 'p'

input: 11 bytes [88 bits]

output: 12 bytes [header: 71 bits; encoding: 21 bits]

output/input size: 109.0909%

Encoding the Sequence

Although you should also be using the xxd command to help you view your file contents in binary, it is also helpful to have an explicit show-binary option to describe the sequence:

$ java HuffmanCodes --encode mi.txt mi.encoded --show-binary

ENCODED SEQUENCE

100110011001110110111

input: 11 bytes [88 bits]

output: 12 bytes [header: 71 bits; encoding: 21 bits]

output/input size: 109.0909%

Decoding

The program will also decode sequences:

$ xxd -b mi.encoded

0000000: 00000000 00000000 00000000 00001011 01011100 11001011 ....\.

0000006: 01101101 11000010 11010011 00110011 00111011 01110000 m..3;p

$ java HuffmanCodes --decode mi.encoded mi.restored --show-codes

CODES

"0" -> 's'

"11" -> 'i'

"100" -> 'm'

"101" -> 'p'

original size: 11

$ cat mi.restored

mississippi

Details

· Download the BitInputStream.java and BitOutputStream.java utility files to help you create the the binary files