LZW压缩似乎无法正常工作

安迪·奥哈特

我试图使此代码正常工作,但是当我尝试对事物进行编码时,它似乎无法正常工作。我有一个60bytes的文本文件。我对其进行编码,输出的文件为100字节。当我对该文件进行解码时,它的大小约为65bytes。可以正确解码,但文件大小大于原始文件。我尝试对jpg进行编码,但文件大小确实减小了,但是之后无法打开文件。我试图解码jpg文件,但它没有用,似乎cmd已冻结。这是我试图使用的代码。

import java.util.*;
import java.io.*;

public class LZW {

// Dictionary 
public static short DSIZE = 256;
public static int DSIZEINT = 256;

/** Compress a string to a list of output symbols. */
public static List<Short> compress(String uncompressed) {
    // Build the dictionary.
    short dictSize = DSIZE;
    Map<String,Short> dictionary = new HashMap<String,Short>();
    for (short i = 0; i < DSIZE; i++)
        dictionary.put("" + (char)i, i);

    String w = "";
    List<Short> result = new ArrayList<Short>();
    for (char c : uncompressed.toCharArray()) {
        String wc = w + c;
        if (dictionary.containsKey(wc))
            w = wc;
        else {
            result.add(dictionary.get(w));
            // Add wc to the dictionary.
            dictionary.put(wc, dictSize++);
            w = "" + c;
        }
    }

    // Output the code for w.
    if (!w.equals(""))
        result.add(dictionary.get(w));
    return result;
}

 /** Compress a string to a list of output symbols, supporting larger filesizes. */
public static List<Integer> compressInt(String uncompressed) {
    // Build the dictionary.
    int dictSize = DSIZEINT;
    Map<String,Integer> dictionary = new HashMap<String,Integer>();
    for (int i = 0; i < DSIZEINT; i++)
        dictionary.put("" + (char)i, i);

    String w = "";
    List<Integer> result = new ArrayList<Integer>();
    for (char c : uncompressed.toCharArray()) {
        String wc = w + c;
        if (dictionary.containsKey(wc))
            w = wc;
        else {
            result.add(dictionary.get(w));
            // Add wc to the dictionary.
            dictionary.put(wc, dictSize++);
            w = "" + c;
        }
    }

    // Output the code for w.
    if (!w.equals(""))
        result.add(dictionary.get(w));
    return result;
}

/** Decompress a list of output ks to a string. */
public static String decompress(List<Short> compressed) {
    // Build the dictionary.
    short dictSize = DSIZE;
    Map<Short,String> dictionary = new HashMap<Short,String>();
    for (short i = 0; i < DSIZE; i++)
        dictionary.put(i, "" + (char)i);

    String w = "" + (char)(short)compressed.remove(0);
    String result = w;
    for (short k : compressed) {
        String entry;
        if (dictionary.containsKey(k))
            entry = dictionary.get(k);
        else if (k == dictSize)
            entry = w + w.charAt(0);
        else
            throw new IllegalArgumentException("Bad compressed k: " + k);

        result += entry;

        // Add w+entry[0] to the dictionary.
        dictionary.put(dictSize++, w + entry.charAt(0));

        w = entry;
    }
    return result;
}

/** Decompress a list of output ks to a string, supporting larger filesizes. */
public static String decompressInt(List<Integer> compressed) {
    // Build the dictionary.
    int dictSize = DSIZE;
    Map<Integer,String> dictionary = new HashMap<Integer,String>();
    for (int i = 0; i < DSIZE; i++)
        dictionary.put(i, "" + (char)i);

    String w = "" + (char)(int)compressed.remove(0);
    String result = w;
    for (int k : compressed) {
        String entry;
        if (dictionary.containsKey(k))
            entry = dictionary.get(k);
        else if (k == dictSize)
            entry = w + w.charAt(0);
        else
            throw new IllegalArgumentException("Bad compressed k: " + k);

        result += entry;

        // Add w+entry[0] to the dictionary.
        dictionary.put(dictSize++, w + entry.charAt(0));

        w = entry;
    }
    return result;
}

public static void main(String[] args) {

    String example = "";
    String s = "";
    int command = 0;

    //Check for correct argument
    if(args.length != 1) {
        System.out.println("Please enter 1 argument.\nArg1: Command ('encode', 'decode', 'encodeInt', 'decodeInt')\nAnd ensure that you are feeding in an input file and output file using '<' and '>'");
        System.exit(1);
    }
    if(args[0].equals("encode")){
        command = 1;
    }
    else if(args[0].equals("decode")){
        command = 2;
    }
    else if(args[0].equals("encodeInt")){
        command = 3;
    }
    else if(args[0].equals("decodeInt")){
        command = 4;
    }
    else {
        System.out.println("Please use either 'encode', 'decode', 'encodeInt', 'decodeInt' as the argument.");
        System.exit(1);
    }

    long start;
    long elapsedTime;

    //Compress
    if(command == 1){

        //Read input file
        s = BinaryStdIn.readString();

        //The actual compression
        start = System.nanoTime();
        List<Short> compressed = compress(s);
        elapsedTime = System.nanoTime() - start;

        //System.err.println(compressed);

        //first writes the number of ints to write
        BinaryStdOut.write(compressed.size());
        //writes compression (to file)
        Iterator<Short> compressIterator = compressed.iterator();
        while (compressIterator.hasNext()){
            BinaryStdOut.write(compressIterator.next());
        }

        System.err.println("LZW Encode time: " + elapsedTime + " ns");

    }
    //Decompress
    else if(command == 2){

        //Build Integer List with input
        List<Short> compressed = new ArrayList<Short>();
        int size = BinaryStdIn.readInt();
        while(size > 0){
            try{
                compressed.add(BinaryStdIn.readShort());
            }
            catch(RuntimeException e){
                System.err.print("*");
            }
            size--;
        }

        //System.err.println(compressed);

        //The actual decompression
        start = System.nanoTime();
        String decompressed = decompress(compressed);
        elapsedTime = System.nanoTime() - start;

        //Print out decompressed data (to file)
        System.out.println(decompressed);

        System.err.println("LZW Decode time: " + elapsedTime + " ns");

    }
    //Compress using Integer size
    else if(command == 3){

        //Read input file
        s = BinaryStdIn.readString();

        //The actual compression
        start = System.nanoTime();
        List<Integer> compressed = compressInt(s);
        elapsedTime = System.nanoTime() - start;

        //System.err.println(compressed);

        //first writes the number of ints to write
        BinaryStdOut.write(compressed.size());
        //writes compression (to file)
        Iterator<Integer> compressIterator = compressed.iterator();
        while (compressIterator.hasNext()){
            BinaryStdOut.write(compressIterator.next());
        }

        System.err.println("LZW Encode time: " + elapsedTime + " ns");

    }
    //Decompress using Integer size
    else if(command == 4){

        //Build Integer List with input
        List<Integer> compressed = new ArrayList<Integer>();
        int size = BinaryStdIn.readInt();
        while(size > 0){
            try{
                compressed.add(BinaryStdIn.readInt());
            }
            catch(RuntimeException e){
                System.err.print("*");
            }
            size--;
        }

        //System.err.println(compressed);

        //The actual decompression
        start = System.nanoTime();
        String decompressed = decompressInt(compressed);
        elapsedTime = System.nanoTime() - start;

        //Print out decompressed data (to file)
        System.out.println(decompressed);

        System.err.println("LZW Decode time: " + elapsedTime + " ns");

    }

    BinaryStdOut.close();


}
}

感谢任何帮助。谢谢。

马克·兰森(Mark Ransom)

即使是最佳的压缩算法,有时也会创建比输入大的输出。实际上,找到这样的输入是一个很好的测试案例。LZW通过找到重复的序列进行压缩,因此没有任何重复序列的输入将必然变得更大。

我曾经不得不创建这样的测试输入。我认为它类似于“ ABCD ... ACBDEG ...”。

编辑:现在,我更加仔细地查看了代码,我看到您正在将Shorts列表写入输出中。几乎可以肯定这是错误的。必要的步骤之一是将每个输出令牌打包到最少的位数中,而您完全丢失了该步骤。

从您的描述来看,代码还存在其他问题,但现在已经足够了。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章