title: LZW Encoder Decoder - Symbol Table
body: <p>My LZW Compression works when I use a symbol table(dictionary) of length 256, Encoder and Decoder both work with 256 and everything works fine but when I increase this number for example to 512, 1024, 4096 the decoded file output is not the same with the first input file...Any hints?</p>
  
  <p>Source Code:</p>
  
  <p>LZWEncoder.java:</p>
  
  <pre><code>import java .io .*;
  public class LZWEncoder
  {
      public static void main ( String [] args )
              throws FileNotFoundException , IOException
              {
          File file = new File ("calgary/book1");
          File fileOut = new File ( "calgary/book1_enc");
          FileInputStream reader = new FileInputStream ( file );
          FileOutputStream writer = new FileOutputStream ( fileOut );
          int size_st;
          long file_size;
          file_size = file.length();
          size_st = (int) file_size/1024;
          System.out.println("File size " + file_size + " Sysmbol tree" + size_st);
  
          if (size_st &lt; 256)
              size_st = 256;
          else if (size_st &lt; 512)
              size_st = 512;
          else if (size_st &lt; 1024)
              size_st = 1024;
          else if (size_st &lt; 2048)
              size_st = 2048;
          else
              size_st = 4096;
  
          byte[] size_stInBytes = (Integer.toString(size_st)+"\n").getBytes();
      //  writer.write(size_stInBytes);
  
          System.out.println("File size " + file_size + " Sysmbol tree " + size_st);
  
          // input stream with lookahead
          LookAheadIn in = new LookAheadIn ( file );
          LZWst st = new LZWst (4096); // specialised ST
          while (! in.isEmpty ())
          {
              int codeword = st.getput (in );
              writer.write ( codeword );
          }
          writer.close ();
          reader.close ();
              }
  }
  </code></pre>
  
  <p>LZWDecoder.java:</p>
  
  <pre><code>import java.io.File;
  import java.io.FileInputStream;
  import java.io.FileNotFoundException;
  import java.io.FileOutputStream;
  import java.io.IOException;
  import java.util.Scanner;
  
  
  public class LZWDecoder
  {
      public static void main ( String [] args )
              throws FileNotFoundException , IOException
              {
          File file = new File ("calgary/book1_enc");
          Scanner first_line = new Scanner("calgary/book1_enc");
          File fileOut = new File ( "calgary/book1_dec2");
          FileInputStream reader = new FileInputStream ( file );
          FileOutputStream writer = new FileOutputStream ( fileOut );
          String size_st;
          size_st =first_line.nextLine();
          System.out.println(" Sysmbol tree " + size_st);
          String [] st = new String [4096];
          int i;
          for (i=0; i &lt;128; i++)
              st[i] = Character.toString (( char ) i);
  
          String prev = "";
          int codeword ;
          while (( codeword = reader.read())!= -1)
          {
  
              String s;
              if ( codeword == i) // Tricky situation !
                  s = prev + prev.charAt(0);
              else 
                  s = st[codeword ];
              for (int j = 0; j&lt;s.length(); j++)
                  writer.write(s.charAt (j));
              if ( prev.length() &gt; 0 &amp;&amp; i &lt; 4096 )
                  st[i++] = prev + s.charAt(0);
              prev = s;
          }
          writer.close();
          reader.close();
              }
  }
  </code></pre>
  
  <p>LZWst.java:</p>
  
  <pre><code>import java.io.FileNotFoundException;
  import java.io.IOException;
  
  public class LZWst
  {
      private int i; // next codeword to assign
      private int codeword ; // codeword to return
      private Node [] roots ; // array of TSTs
      private int st_size;
      public LZWst (int st_sz)
      {
          st_size = st_sz;
          roots = new Node [128];
          for (i=0; i &lt;128; i++) // init with ASCII
              roots [i] = new Node (( char ) i,i);
      }
      private class Node
      { // standard node code
          Node (int c, int codeword )
          {
              this .c = c;
              this . codeword = codeword ;
          }
          int c;
          Node left , mid , right ;
          int codeword ;
      }
  
      public int getput ( LookAheadIn in)
              throws FileNotFoundException , IOException
              {
          int c = in. readChar ();
          if ( c == -1) return -1; // EOF
          roots [c] = getput (c, roots [c],in );
          in. backup ();
          return codeword ; // longest prefix
              }
      public Node getput ( int c, Node x, LookAheadIn in)
              throws FileNotFoundException , IOException
              { // recursive search *and* insert
          if (x== null ) {
              if (i&lt;st_size){
              x = new Node (c,i++);
              System.out.println("Value of i: " + i);
              }
              return x;
          }
          if (c&lt;x.c) x. left = getput (c,x.left ,in );
          else if (c&gt;x.c) x. right = getput (c,x.right ,in );
          else {
              int next = in.readChar();
              codeword = x. codeword ;
              x.mid = getput (next ,x.mid ,in );
          }
          return x;
              }
  }
  </code></pre>
  
  <p>LookAheadIn.java:</p>
  
  <pre><code>import java.io.File;
  import java.io.FileInputStream;
  import java.io.FileNotFoundException;
  import java.io.IOException;
  
  public class LookAheadIn
  {
      private FileInputStream in = null ;
      private int last ;
      private boolean backup = true ;
      public LookAheadIn ( File file )
              throws FileNotFoundException , IOException
              {
          in = new FileInputStream ( file );
          last = in. read ();
          backup = true ;
              }
      public void backup () { backup = true ; }
      public int readChar () throws FileNotFoundException , IOException
              {
          if (! backup ) last = in. read();
          backup = false ;
          return last ;}
      public boolean isEmpty(){ return last == -1; }
  }
  </code></pre>