如何优化霍夫曼解码？

Question

所以我一直在尝试使用霍夫曼解码，我有这个工作功能，但它具有可怕的时间和空间复杂性。到目前为止，我一直在做的是读取每个字节，获取每个位并将其添加到 currentBitString。然后我反转字符串，并将其添加到一个巨大的字符串中，该字符串基本上包含文件的所有字节数据。在那之后，我会追踪这个巨大的字符串并寻找霍夫曼代码，然后如果它匹配，我会写入文件。这段代码解码一个 200kb 大约需要 60 秒，这非常糟糕，但我不确定如何改进它？我知道对于初学者来说，我可以一次向文件写入一个以上的字节，但它似乎并没有改善我尝试的时间？

         public static void decode(File f) throws Exception {

    BufferedInputStream fin = new BufferedInputStream(new FileInputStream(f));

    int i = f.getName().lastIndexOf('.');

    String extension="txt";

    String newFileName=f.getName().substring(0, i)+extension;

    File nf = new File(newFileName);

    BufferedOutputStream fw = new BufferedOutputStream(new FileOutputStream(nf));

    int c;

    byte bits;

    byte current;

    String currentBitString="";

    String bitString="";

    //read each byte from file, reverse it, add to giant bitString

    //reads ALL BYTES

    while( (c=fin.read())!=-1 ) {

        current=(byte) c;

        currentBitString="";

        bits=0;

        for(int q=0;q<8;q++) {

            bits=getBit(current,q);

            currentBitString+=bits;

        }

        StringBuilder bitStringReverse=new StringBuilder(currentBitString);

        bitString+=bitStringReverse.reverse().toString();

    }

    currentBitString="";

    boolean foundCode=false;

    for(int j=0;j<bitString.length();j++) {

        currentBitString+=bitString.charAt(j);

        for(int k=0;k<nodes.length;k++) {

            //nodes is an array of huffman nodes which contains the the byte 

            //data and the huffman codes for each byte

            if(nodes[k].code.compareTo(currentBitString.trim())==0) {

                fw.write(nodes[k].data);    

                foundCode=true;

                break;

            }

        }

        if(foundCode) {

            currentBitString="";

            foundCode=false;

        }

    }

    fw.flush();

    fw.close();

    fin.close();

}

这是 gitBit 函数

        public static byte getBit(byte ID, int position) {

        // return cretin bit in selected byte

        return (byte) ((ID >> position) & 1);

        }

Answer 1

不要将整个事情读入内存。处理遇到的代码。读取足够的位以解码下一个代码，对其进行解码，为后续代码保留未使用的位，重复。不要使用字符串来表示位，每个字符代表一位。使用位来表示位。shift, and, and or 运算符是您应该使用的。您将有一个整数作为位缓冲区，其中包含解码下一个代码所需的所有位。不要搜索所有代码长度，而是在其中线性搜索所有代码以找到您的代码！我很难想出一个更慢的方法。您应该使用树下降或表查找进行解码。如果您首先生成规范的霍夫曼代码，则可以实现一种简单的查找方法。有关示例，请参见puff.c。教科书的方法（比 puff.c 做的要慢）是在接收端构建相同的 Huffman 树，然后一点一点地沿着树向下直到你得到一个符号。发出符号并重复。您应该能够在现代处理器的单个内核上在几毫秒内处理 200K 的压缩输入。

Answer 2

您可以替换字符串concatination+=用StringBuilder。这会分配更少的对象并减少垃圾收集器的负载。int c;StringBuilder bitString = new StringBuilder();//read each byte from file, reverse it, add to giant bitString//reads ALL BYTESwhile ((c = fin.read()) != -1) {&nbsp; &nbsp; byte current = (byte) c;&nbsp; &nbsp; StringBuilder currentBitString = new StringBuilder();&nbsp; &nbsp; for (int q = 0; q < 8; q++) {&nbsp; &nbsp; &nbsp; &nbsp; byte bits = getBit(current, q);&nbsp; &nbsp; &nbsp; &nbsp; currentBitString.append(bits);&nbsp; &nbsp; }&nbsp; &nbsp; bitString.append(currentBitString.reverse());}而不是将代码和数据放入数组中，nodes您应该在HashMap此处使用 a 。您通过迭代整个数组来比较代码，直到找到正确的匹配项。平均而言，这是n/2对String#equals()每个项目的调用。使用 aHashMap您将其减少到〜1。使用代码作为键的数据填充您的地图。Map<String, Integer> nodes = new HashMap<>();nodes.put(code, data);从地图访问数据boolean foundCode = false;for (int j = 0; j < bitString.length(); j++) {&nbsp; &nbsp; currentBitString.append(bitString.charAt(j));&nbsp; &nbsp; Integer data = nodes.get(currentBitString.toString().trim());&nbsp; &nbsp; if (data != null) {&nbsp; &nbsp; &nbsp; &nbsp; fw.write(data);&nbsp; &nbsp; &nbsp; &nbsp; foundCode = true;&nbsp; &nbsp; }&nbsp; &nbsp; if (foundCode) {&nbsp; &nbsp; &nbsp; &nbsp; currentBitString = new StringBuilder();&nbsp; &nbsp; &nbsp; &nbsp; foundCode = false;&nbsp; &nbsp; }}