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

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

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

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

我认为这当前在myTree.writeMe()中编码,你需要修改方法不返回String,但更适合二进制输出的东西,例如byte [].

它取决于你树类的内部工作方式如何做到这一点.我假设你在内部使用一些StringBuilder,只需在循环输入时添加编码的符号字符串.您需要一个能够处理单个位的容​​器,而不是StringBuilder.立即到达min的唯一合适的类是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();

如何有效地执行此操作取决于您在内部如何定义霍夫曼代码表.但是原理很简单,循环代码,确定每个地方是一个还是零,并将它们放在连续索引的BitSet中.

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

您现在拥有了霍夫曼编码数据.但是生成的数据将无法正确解压缩,因为您当前正在处理单词而您没有写任何指示压缩数据实际结束的位置(您目前使用换行符执行此操作).如果您编码例如3次'a',则BitSet将包含11 11 11.这是6位,但是当您转换为byte []时,它将被填充到8位:0b11_11_11_00.

那些额外的,不可避免的比特会让你的减压感到困惑.您需要以某种方式处理此问题,方法是首先编码数据中的符号数,或者使用显式符号信号结束数据.

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