LZW Encoder Decoder - Symbol Table

Question

My LZW Compression работает, когда я использую таблицу символов (словаря) длиной 256, Encoder и Decoder работают с 256, и все работает нормально, но когда я увеличиваю это число, например, до 512, 1024, 4096 выход декодированного файла не совпадает с первым входным файлом ... Любые подсказки?

Исходный код:

LZWEncoder.java:

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 < 256) 
      size_st = 256; 
     else if (size_st < 512) 
      size_st = 512; 
     else if (size_st < 1024) 
      size_st = 1024; 
     else if (size_st < 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(); 
      } 
} 

LZWDecoder.java:

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 <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<s.length(); j++) 
       writer.write(s.charAt (j)); 
      if (prev.length() > 0 && i < 4096) 
       st[i++] = prev + s.charAt(0); 
      prev = s; 
     } 
     writer.close(); 
     reader.close(); 
      } 
} 

LZWst.java:

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 <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<st_size){ 
      x = new Node (c,i++); 
      System.out.println("Value of i: " + i); 
      } 
      return x; 
     } 
     if (c<x.c) x. left = getput (c,x.left ,in); 
     else if (c>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; 
      } 
} 

LookAheadIn.java:

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; } 
} 

Answer 1

Вы читаете байты, они не могут хранить большие значения. Если вы хотите сделать LZW с кодами, превышающими 255, вам нужно либо закодировать потоки битов, либо для тестирования (как временного взлома) записать два байтовых слова (unsigned int размером 16).

Заменить

writer.write (codeword); 

с

writer.write (codeword>>8); 
writer.write (codeword&0xff); 

и проверить, работает ли он. Если это так, вы можете потратить некоторое время на реализацию потока на основе бит. Вам также потребуется обновить считыватель и декодер.