3

我正在尝试在 Java 中实现压缩/解压缩算法，这是我目前的进展：完整源代码。

只有两件事我不完全确定如何解决：

  1. 当我压缩文件时，它适用于除字节数较少的文件之外的所有文件。有朋友告诉我，问题是当我们压缩文件时，我们需要树，并且必须将它存储在文件本身中，从而使压缩文件因树而变大。关于如何解决这个问题的任何指示？
  2. 完全不知道如何实现解压。
4

2 回答 2

2

问题1无法解决。例如，如果您有一个只有 3 个不同字节的文件，并且您进行了哈夫曼压缩，您将创建一个如下所示的树：http ://huffman.ooz.ie/?text=asd

因此，压缩文件中的树会自动大于完整的旧文件，但如果您要做其他任何事情，它就不再是霍夫曼压缩了。对于具有很多不同字节的所有文件都相同。原则上：文件中更多相等的字节将在压缩后带来更好的结果

第二件事是非常普遍的，但要获得一些帮助，请查看以下代码：https ://github.com/nayuki/Huffman-Coding/blob/master/src/nayuki/huffmancoding/HuffmanDecompress.java

于 2013-05-29T06:01:38.920 回答
1

树可以以非常紧凑的方式存储。

我做过一次——基本上我以 LR 模式遍历树。因此，在节点 N 处，如果左分支是叶子，则写入 a1后跟该叶子编码的符号，否则只需写入 a0并下降到该节点。

然后对右分支执行相同的操作 - 如果它是叶写入1然后符号，如果它是节点写入0并下降到该节点。

这棵树http://huffman.ooz.ie/?text=asd（感谢 Bernhard！）可以写成1[D]01[A]1[S]总共 28 位或 4 字节（例如，将 [D] 替换为01000100）。

以相反的方式对表进行解码。我没有时间编写代码，但它确实有效，而且我相信它必须接近树的最紧凑编码（我没有任何证据）。

于 2013-05-29T06:17:02.457 回答