LZW压缩算法的实现

Question

我一直在阅读基于字典的压缩算法，包括LZW和LZSS。然后，我想使用Java实现LZW并开始了工作。我不是开发人员，所以我怀疑我的实现可能不够高效。你可以看看代码告诉我实现中有什么问题或低效之处吗？以下是完整代码。

public class LZW {

    public HashMap compdic, decompdic;
    String fileName = "walaloo.txt";
    short lastcode = 0, dlastcode = 0;

    LZW() {
        compdic = new HashMap<String, Integer>();
        decompdic = new HashMap<Integer, String>();
        createDictionary();
    }

    public void createDictionary() {
        try {
            short code;
            char ch;
            FileInputStream fis = new FileInputStream(fileName);
            InputStreamReader rdr = new InputStreamReader(fis, "utf-8");
            while ((code = (short) rdr.read()) != -1) {
                ch = (char) code;

                if (!compdic.containsKey(ch)) {
                    compdic.put("" + ch, code);
                    decompdic.put(code, "" + ch);
                    if (code > lastcode) {
                        lastcode = code;
                        dlastcode = code;
                    }
                }
            }
            fis.close();
        } catch (Exception ex) {
            Logger.getLogger(LZW.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    public void compressFile() {
        try {
            short code, codeword;
            char c;
            String s;

            System.out.print("Compressing...");
            FileInputStream fis = new FileInputStream(fileName);
            InputStreamReader rdr = new InputStreamReader(fis, "utf-8");
            FileOutputStream fos = new FileOutputStream(fileName + "1.lzw");
            ObjectOutputStream fout = new ObjectOutputStream(fos);

            s = (char) rdr.read() + "";
            while ((code = (short) rdr.read()) != -1) {
                c = (char) code;

                if (!compdic.containsKey(s + c)) {
                    codeword = Short.parseShort(compdic.get(s).toString());

                    fout.writeShort(codeword);
                    compdic.put(s + c, ++lastcode);
                    s = "" + c;
                } else {
                    s = s + c;
                }
            }

            codeword = Short.parseShort(compdic.get(s).toString());
            fout.writeShort(codeword);
            fout.writeShort(00);

            fout.close();
            fis.close();

            System.out.print("done");

        } catch (Exception ex) {
            Logger.getLogger(LZW.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    public void decompressFile() {
        short priorcode = -1, codeword = -1;
        char c;

        String priorstr, str;
        FileInputStream fis; 
        FileWriter fos; 
        ObjectInputStream fin;

        try {
            fis = new FileInputStream(fileName + "1.lzw");
            fos = new FileWriter(fileName + "2.txt");
            fin = new ObjectInputStream(fis);

            System.out.print("\nDecompressing...");
            priorcode = fin.readShort();
            fos.write(decompdic.get(priorcode).toString());
            while ((codeword = fin.readShort()) != -1) {
                if(codeword == 00)
                    break;

                priorstr = decompdic.get(priorcode).toString();

                if (decompdic.containsKey(codeword)) {
                    str = decompdic.get(codeword).toString();
                    fos.write(str);
                    decompdic.put(++dlastcode, priorstr + str.charAt(0));
                } else {
                    decompdic.put(++dlastcode, priorstr + priorstr.charAt(0));
                    fos.write(priorstr + priorstr.charAt(0));
                }

                priorcode = codeword;
            }

            fos.close();
            fis.close();
            System.out.print("done\n");

        } catch (Exception ex) {
            //Logger.getLogger(LZW.class.getName()).log(Level.SEVERE, null, ex);
            System.out.println("\n\nError: " + ex.getMessage());
            System.out.print(codeword + " " + priorcode + " " + decompdic.get(133) + " " + dlastcode);
        }
    }

    public static void main(String args[]) {
        LZW lzw = new LZW();
        lzw.compressFile();
        lzw.decompressFile();
    }
}

- birraa

---

这段代码已经可以工作了，你只是在寻找改进吗？那么你最好去http://codereview.stackexchange.com/上询问。 如果代码中有任何（已知的）问题，你应该说明它们，这样我们就能知道你的问题所在。 - Matthias Wimmer

如果代码按照预期工作，那么它看起来确实适合于代码审查。 - Phrancis

代码在我测试时运行良好，我没有发现任何问题。我最大的怀疑是在创建压缩字典时使用了short类型。这意味着一些使用Unicode编码大于32767的非拉丁字母表的语言无法处理。我还没有测试过这个问题。 - birraa

“我测试时运行良好”。你是如何测试的？建议：1）压缩文件；2）重命名输入文件；3）尝试使用新实例解压缩，如果无法处理，则会出现混乱 - 你的解压似乎需要明文才能设置“decompdic”。 - greybeard

Answer 1

你的字典大小为32,767项。(简短) 你没有限制它的大小，也没有检查它。它对于小文件可以正常工作。对于大文件会丢失数据。

- user11104398