选择一种压缩算法来实现

Question

我被分配了一项作业，需要实现我选择的压缩算法。它可以使用任何语言，但我最熟悉的语言是Java，其次是C。它将根据以下标准进行评估：

1. 解压输出必须与原始输入匹配，因此我只能查看无损算法。 2. 运行时间必须与消息长度成比例。 3. 内存需求必须独立于消息长度。

我们的实现将按以下方式进行测试：

1. 标准文本文件 2. 具有0-255字节值的二进制文件 3. 未指定内容的大型文件（约10mb）。

我的初步想法是使用动态算术编码，但我想知道是否有更适合上述限制条件的算法？其次，使用C而不是Java是否更好？我之所以这样问是因为我认为C的内存占用量会更小，但我不确定实际情况是否如此。

我花了一些时间在谷歌上搜索这个问题，一些网站提到LZW编码结合动态霍夫曼编码。这是否是一个明智的方法？我们的讲师警告说，多年来尝试使用动态霍夫曼编码的90％的提交都没有正确实现。

话虽如此，我并不害怕尝试，但在开始之前我会很重视一些意见。

非常感谢任何反馈。

- Saf

---

如果之前使用哈夫曼编码的提交中有90%都是错误的，或许这对你来说会是更好的挑战。 - Randy Howard

香农-法诺编码不符合你的（3）要求吗？ 它非常简单易懂。 如果你以前没有实现过压缩算法，我建议使用S-F。 - David Titarenco

如果您选择使用LZW-Dynamic-Huffman算法，我的建议是除了Dr.Dobbs 1989 article中提出的方案外，可以使用几乎任何人的LZW技术。我发现该文章对Terry Welch算法中的“错误”进行的“分析”以及作者对该问题的“解决方案”既冒犯读者，也冒犯了Welch先生，他对数据压缩算法的了解比该文章的作者所知道的要多得多。 - WhozCraig

不要压缩，只需购买更多的磁盘空间。 - jxh

Answer 1

仅使用LZW编码非常简单，而且效果出乎意料地好。现在没有人会实际使用LZW，因为有其他算法可以更快速地更好地压缩。但是对于一项任务，LZW的简单性是无可比拟的。没有哈夫曼编码，动态或静态。没有香农-范诺编码。没有算术编码或范围编码。是的，内存使用量与消息长度无关。马克·纳尔逊写了一个非常好的解释（very good explanation）。

您可以使用C或Java完成，尽管C可能较少出错，因为它具有无符号类型。

- Mark Adler

Answer 2

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

根据this，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

只有当你完全理解了自适应算法（或者你之前已经实现过类似的算法）时，我才建议采用更严格的算术编码方法。最近我在一门《信息论》课程中实现了自适应算法，其中的一些部分在我理解之前看起来很不直观和奇怪。虽然在纸上看起来很简单，但是（像许多其他算法一样）这可能是误导性的。

除非你想获得额外的“风格分”，否则我个人会选择香农-范诺编码。

- David Titarenco

---

我不能使用Shannon Fano算法，原因有几个。首先，您必须按概率的非递增顺序对符号进行排序，因此您要么需要在文件中进行两次遍历（一次用于分析，一次用于压缩），要么将整个文件读入内存。第二个原因是它生成的树并不总是最优的。即使是静态的Huffman编码也能产生更好的结果，而且实现起来也不难。 - Saf

@Saf：我知道SF不是最佳选择，但最佳性能并不在你的列表中；）我检查了三遍！完全将10mb读入内存不应该是问题；但如果你不能使用它，那就很糟糕了。这是Huffman / Arithmetic编码的绝佳介绍（因为它是后者的特例）。 - David Titarenco

我可能会将其用作备选方案，甚至像你建议的那样作为起点。虽然我必须扫描文件两次，但是加载整个文件会使内存需求与消息长度成正比。我怀疑因为不得不扫描文件两次而被扣分，我们的讲师倾向于追求最有效率的路线。感谢指导。 - Saf

为什么人们要在这些代码中加入行号？ - Randy Howard

@RandyHoward：这是我链接的源代码的直接复制粘贴。 - David Titarenco

Answer 3

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

对于语言的选择，请使用您更熟悉的语言。将要执行许多位操作，因此C或Java都很适合。您应该编写一些处理文件转换为位流和反向操作的代码，并将其作为单独的模块。我可以看到用C或Java做到这一点。

- user66363

---

我们没有任何性能目标，除了“尽可能优化工作”，我知道这很模糊，但我认为这是挑战的一部分。它应该在任何类型的文件上都能很好地工作，因此我们不必担心文件是音频还是视频等，除非可能需要检查我们不会出现信息扩展的情况。 - Saf

你应该在课堂上学过这个定理：没有无损压缩方法可以压缩所有文件。但是他似乎在询问某种标准化的方法。另外请注意，您可以对输入文件进行两次遍历（两次仍然成比例）。只是您不允许将整个文件存储在内存中。 - user66363

我们才刚刚学习到课程的一半，开始学习算法，接下来将会学习不同类型的文件，例如GIF、MP3等。但这是一个好问题，我会问一下讲师是否应该针对某种文件类型进行优化。 - Saf