4

我已经获得了一些课程来实现我选择的压缩算法。它可以是任何语言，但我最了解的语言是 Java，其次是 C。它将基于 -

  1. 解压后的输出必须和原始输入匹配，所以只能看lossless的算法。

  2. 运行时间必须与消息的长度成比例。

  3. 内存要求必须与消息的长度无关。

我们的实现将按如下方式进行测试 -

  1. 标准文本文件

  2. 字节值范围为 0-255 的二进制文件

  3. 一个约 10mb 的未指定内容的大文件。

我最初的想法是使用动态算术编码，但我想知道是否有更适合上述约束的算法？其次，用 C 语言而不是 Java 语言是更好的主意吗？我问这个是因为我认为 C 的内存占用会更小，但我不确定是否真的如此。

我花了一些时间在谷歌上搜索这个问题，一些网站提到 LZW 编码与动态霍夫曼编码相结合。这会是一个明智的追求途径吗？我们的讲师确实警告我们，多年来尝试动态霍夫曼编码的提交中有 90% 没有正确实施。

也就是说，我不害怕尝试一下，但在开始之前我会重视一些意见。

任何反馈将不胜感激。

4

3 回答 3

4

只是 LZW，没有其他编码，非常简单，而且工作得非常好。现在没有人会真正使用 LZW，因为还有其他算法可以更快地压缩。然而，对于一个任务，你无法击败 LZW 的简单性。没有霍夫曼，动态或其他。没有香农-法诺。没有算术或范围编码。是的，内存使用量与消息的长度无关。Mark Nelson 写了一个很好的解释。

您可以在 C 或 Java 中执行此操作，尽管 C 可能不太容易出错，因为它具有无符号类型。

于 2013-03-15T04:29:48.553 回答
1

内存限制建议使用某种自适应编码。算术编码很好。但是您没有指定任何有关性能的内容。该算法是否必须达到特定类别文件的任何性能目标？仅复制文件的算法满足上述要求，（但不会教你太多）。

对于语言的选择，请使用您更熟悉的语言。将要执行很多位操作，因此 C 或 Java 都适合。您应该编写一些代码来处理将文件转换为比特流并再次返回，并将其作为一个单独的模块。我可以看到在 C 或 Java 中这样做。

于 2013-03-15T00:52:10.107 回答
1

为了回答我自己的问题，Shannon-Fano 对于这样的任务应该“足够好”。如果您从未在数据压缩领域做过任何事情，我建议您远离霍夫曼编码（或算术编码的专门版本）。

据此，顺丰满足您的空间/时间要求。我建议先实施类似的东西。伪代码由下式给出：

 1:  begin
 2:     count source units
 3:     sort source units to non-decreasing order
 4:     SF-SplitS
 5:     output(count of symbols, encoded tree, symbols)
 6:     write output
 7:   end
 8:  
 9:  procedure SF-Split(S)
10:  begin
11:     if (|S|>1) then
12:      begin
13:        divide S to S1 and S2 with about same count of units
14:        add 1 to codes in S1
15:        add 0 to codes in S2
16:        SF-Split(S1)
17:        SF-Split(S2)
18:      end
19:  end

只有当您彻底了解 SF（或者您之前已经实现过类似的算法）时，我才会建议您采用更严格的算术编码方法。我最近为一门信息理论课实施了 SF，但在我理解它之前，它的某些部分似乎不直观且奇怪。在纸面上，它看起来很简单，但是（像许多其他算法一样）可能具有欺骗性。

除非你获得额外的“风格点数”，否则我个人会选择 Shannon-Fano。

于 2013-03-15T00:23:59.717 回答