title: LZW Compression - A modified version
body: <p>I have an LZW algorithm -</p>
  
  <pre><code>private void start(int maxNumBits) throws IOException{
      System.out.println("Beginning");
      /** Compress a string to a list of output symbols. */
      // Build the dictionary.
      for (int i = 0; i &lt; 256; i++)
          dict.put("" + (char)i, i);
      int i;
      String w = "";
      int bitsRead = 0;
      int bitsOutput = 0;
      int trieLength = 0;
      float lastCr = 0f;
      while((i = reader.read()) != EOF){
          bitsRead += 8;
          float currentCr = (float)bitsRead / (float)bitsOutput;
          if(bytesRead % 1024 == 0)
              System.out.println(currentCr);
          String wi = w + (char)i;
          if (dict.containsKey(wi) &amp;&amp; ((currentCr &gt;= lastCr) || (trieLength &lt; maxNumBits))){
              w = wi;
              trieLength += 8;
          }
          else {
              fos.write(dict.get(w));
              bitsOutput += 8;
              // Add wi to the dictionary.
              dict.put(wi, mapSize++);
              w = "" + (char)i;
              trieLength = 0;
          }
          lastCr = currentCr;
      }
      // Output the code for w.
      if (!w.equals("")){
          fos.write(dict.get(w));
          bitsOutput += 8;
      }
  }
  </code></pre>
  
  <p>where <code>maxNumBits</code> is supposed to be the maximum size of the trie. Assume the exception is caught in a main class which passes the <code>maxNumBits</code> parameter. Assume <code>dict</code> is a <code>HashMap</code>, <code>reader</code> is a <code>FileInputStream</code> and <code>fos</code> is a <code>FileOutputStream</code>.</p>
  
  <p>In my version, if the trie becomes full ( that is, <code>trieLength &gt; maxNumBits</code> ), the compression continues until the current compression ratio (<code>currentCr</code>) is less than the last compression ratio (<code>lastCr</code>).</p>
  
  <p>I've run this on a ~8mb file and changing the trie length doesn't do anything to the cumulative compression ratio. Is this code</p>
  
  <pre><code>if(dict.containsKey(wi) &amp;&amp; ((currentCr &gt;= lastCr)||(trieLength &lt; maxNumBits)))
  </code></pre>
  
  <p>correct for the requirements described?</p>
  
  <p>Thanks for your help,</p>
  
  <p>Sam</p>
  
  <p>edit - thanks for the help with formatting, Edward</p>