选择要实施的压缩算法

Question

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

1. 解压后的输出必须与原始输入匹配，所以我只能看损失较小的算法。

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

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

我们的实施将进行如下测试 -

1. 标准文本文件

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

3. 一个大约 10mb 的大文件，其中包含未指定的内容。

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

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

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

任何反馈将不胜感激。

Answer 1

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

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

Answer 2

为了回答我自己的问题，香农-法诺应该“足够好”来完成这样的任务。如果您从未在数据压缩领域做过任何事情，我建议您远离霍夫曼编码（或算术编码的特殊版本）。

据此， SF满足您的空间/时间要求。我建议首先实施类似的事情。伪代码由下式给出：

 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 class and some parts of it seemed non-intuitive and weird until I got my head around it. On paper it looks simple, but (like numerous other algorithms) that can be deceiving.

除非你获得额外的“风格点”，否则我个人会选择香农法诺。