java - 将二进制值写入文件以进行霍夫曼编码

Question

我正在尝试使用霍夫曼编码实现文件压缩。目前，我将标题写为压缩文件的第一行，然后写入编码的二进制字符串(即具有二进制编码值的字符串)。

但是，我的文件大小并没有减小，而是在增加，因为对于每个字符(如“a”)，我正在编写其对应的二进制文件，例如 01010001，这会占用更多空间。

如何以减少空间的方式将其写入文件？

这是我的代码

public void write( String aWord ) {

        counter++;
        String content;
        byte[] contentInBytes;

        //Write header before writing file contents
        if ( counter == 1 )
        {
            //content gets the header in String format from the tree
            content = myTree.myHeader;
            contentInBytes = content.getBytes();

            try {
                fileOutputStream.write(contentInBytes);
                fileOutputStream.write(System.getProperty("line.separator").getBytes());
            } catch (IOException e) {
                System.err.println(e);
            }
        }

        //content gets the encoded binary in String format from the tree
        content = myTree.writeMe(aWord);
        contentInBytes = content.getBytes();


            try {
                fileOutputStream.write(contentInBytes);
                fileOutputStream.write(System.getProperty("line.separator").getBytes());
            } catch (IOException e) {
                System.err.println(e);
            }
        }

示例输入文件:

abc
aef
aeg

压缩文件:

{'g':"010",'f':"011",'c':"000",'b':"001",'e':"10",'a':"11"}
11001000
1110011
1110010

Answer 1

正如我从评论中收集到的那样，您正在编写文本，但您真正想要实现的是编写二进制数据。您目前拥有的是一个很好的霍夫曼编码演示，但对于实际压缩数据是不切实际的。

要实现压缩，您需要将霍夫曼符号输出为二进制数据，您当前输出字符串“11”作为“a”，您只需要输出两位 11 .

我假设这是目前在 myTree.writeMe() 中编码的，您需要修改该方法以不返回一个字符串，而是更适合二进制输出的东西，例如字节[].

如何执行此操作在一定程度上取决于树类的内部工作原理。我假设您在内部使用了一些 StringBuilder 并在循环输入时简单地添加编码的符号字符串。您将需要一个能够处理单个位的容​​器，而不是 StringBuilder。立即出现的唯一合适的类是 java.util.BitSet(在实践中，人们通常会为此编写一个专门的类，使用专门的 API 来快速执行此操作)。但为简单起见，现在让我们使用 BitSet。

在方法 writeMe 中，您原则上将执行以下操作:

 BitSet buffer = new BitSet();
 int bitIndex = 0;
 loop over input symbols {
     huff_code = getCodeForSymbol(symbol)
     foreach bit in huff_code {
         buffer.put(bitIndex++, bit)
     }
 }
 return buffer.toByteArray();

如何有效地执行此操作取决于您如何在内部定义霍夫曼码表。但是原理很简单，遍历代码，判断每个位置是1还是0，然后将它们放入连续索引处的BitSet中。

if (digits == '1') {
    buffer.set(bitIndex);
} else {
    buffer.clear(bitIndex);
}

您现在拥有霍夫曼编码数据。但是生成的数据将无法正确解压缩，因为您当前正在处理单词并且您没有写任何指示压缩数据实际结束的位置(您当前使用换行)。例如，如果您编码 3 次“a”，则 BitSet 将包含 11 11 11。那是 6 位，但是当您转换为 byte[] 时，它会被填充为 8 位:0b11_11_11_00。

那些额外的、不可避免的位会混淆你的减压。您将需要以某种方式处理此问题，方法是首先对数据中的符号数量进行编码，或者使用显式符号表示数据结束。

这应该让您知道如何继续想法。许多细节取决于您如何实现树类和编码符号。