java - 哈夫曼压缩压缩后的文件比原始文件大

Question

我使用优先级队列在 Java 中实现了霍夫曼编码算法，其中我从根到叶遍历树，并根据符号在输入中出现的次数获得编码示例 #=000011。一切都很好，树构建得很好，编码正如预期的那样:但是我得到的输出文件比原始文件更大。我目前正在将“0”和“1”附加到遍历树的左节点和右节点的字符串中。这是我使用 OutputStream 进行写入的写入方法:

private void writeToFile(Map<Byte, BitSet> dictCode, byte[] data, OutputStream os) throws IOException {
    for (int i = 0; i < data.length; i++) {
        os.write(dictCode.get(data[i]).toByteArray());
    }
 }

data是我的文件(我将压缩的文件)，以字节为单位

Map<Byte, BitSet> dictCode BitSet是字节的哈夫曼树代码路径

例如，10 的位集将为 10={3}因为只有第三位为真:000100

我以字节为单位写入，为什么我的新文件比原始文件大？

Answer 1

看起来您的问题在于您正在写出字节流而不是位流。

假设在您的代码中，dictCode 映射对于 data 中的每个字节都有一个重要的条目，那么:

private void writeToFile(Map<Byte, BitSet> dictCode, byte[] data, OutputStream os) throws IOException {
    for (int i = 0; i < data.length; i++) {
        os.write(dictCode.get(data[i]).toByteArray());
    }
 }

正在将data中的每个字节至少写入os一个字节。因此，如果数据是输入文件中的原始字节，则您永远无法使用此代码编写更小的文件。

例如，使用 token 流

111 010 000 1101 111

你正在写

00000111 00000010 00000000 00001101 00000111

而不是

11101000 01101111 

这就是为什么您没有看到任何压缩。