java - 如何优化霍夫曼解码？

Question

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

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

这是 HuffmanNode 类的数据成员(节点数组是 HuffmanNode 数组)

       public class HuffmanNode{
       byte data;
       int repetitions;
       String code;
       HuffmanNode right;
       HuffmanNode left;
       }

Answer 1

您可以将字符串连接 += 替换为 StringBuilder。这会分配更少的对象并减少垃圾收集器的负载。

int c;
StringBuilder bitString = new StringBuilder();
//read each byte from file, reverse it, add to giant bitString
//reads ALL BYTES
while ((c = fin.read()) != -1) {
    byte current = (byte) c;
    StringBuilder currentBitString = new StringBuilder();
    for (int q = 0; q < 8; q++) {
        byte bits = getBit(current, q);
        currentBitString.append(bits);
    }
    bitString.append(currentBitString.reverse());
}

您应该在此处使用 HashMap，而不是将代码和数据放入数组 nodes 中。您通过迭代整个数组来比较代码，直到找到正确的匹配项。平均每个项目有 n/2 次调用 String#equals()。使用 HashMap 可以将其减少到 ~1。

使用代码数据作为键填充您的 map 。

Map<String, Integer> nodes = new HashMap<>();
nodes.put(code, data);

从 map 访问数据

boolean foundCode = false;
for (int j = 0; j < bitString.length(); j++) {
    currentBitString.append(bitString.charAt(j));
    Integer data = nodes.get(currentBitString.toString().trim());
    if (data != null) {
        fw.write(data);
        foundCode = true;
    }
    if (foundCode) {
        currentBitString = new StringBuilder();
        foundCode = false;
    }
}