我已经给了一些课程来实现我选择的压缩算法。它可以是任何语言，但是我知道最好的是Java的语言，其次是C.将评估基础上 -选择压缩算法来实现
解压后的输出必须与原始输入相匹配，所以我只能看着损失更少的算法。
运行时间必须与消息长度成正比。
内存要求必须独立于消息的长度。
我们实现将如下测试 -
的标准文本文件
具有字节值的二进制文件从0-255
大型文件〜 10mb的未指定内容。
我最初的想法是使用动态算术编码，但我想知道是否有更适合上述约束的算法？其次，用C而不是Java来做它是一个更好的主意吗？我问这个是因为我认为C的记忆足迹会更小，但我不确定这是否真的如此。
我花了一些时间Google搜索这个问题，几个网站提到LZW编码结合动态霍夫曼编码。这是一个明智的途径吗？我们的讲师确实告诫我们，多年来尝试动态霍夫曼编码的提交中有90％没有正确实施。
这就是说，我不害怕试一试，但在开始之前我会重视一些意见。
任何反馈将不胜感激。
为了回答我自己的问题，Shannon-Fano应该对这样的任务“足够好”。如果你在数据压缩领域从未做过任何事情，我建议远离霍夫曼编码（或算术编码的专用版本）。
根据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
只有当你完全了解SF（或你已经实现了之前类似的算法），我建议去一个更严格的算术编码方法。我最近实施了SF的信息理论班，它的一些部分似乎是非直观和奇怪的，直到我得到了我的头。在纸上看起来很简单，但是（像很多其他算法一样）可能是骗人的。
除非你有额外的“风格点”，我个人会去香农法诺。
我不能使用Shannon Fano有几个原因。 首先，您必须将符号分类为不增加的概率顺序，因此您必须在文件中进行两次传递（一个用于分析，一个用于压缩），或者将整个文件读入内存。 第二个原因是它生成的树并不总是最优的。即使静态霍夫曼编码也能产生更好的结果，这并不难实现。 – Saf 2013-03-15 00:37:24
@Saf：我知道SF并不是最理想的，但最优并不在你的名单上;）我检查了三次！将10mb全部读入内存应该不成问题;但如果你不能使用它，那真是无赖。这是对霍夫曼/算术编码的一个很好的介绍（因为它是后者的特例）。 – 2013-03-15 00:40:28
我可以用它作为后备，或者甚至像你所建议的那样，作为一个起点。我将不得不两次扫描文件，加载整个文件会使内存需求与消息的长度成正比。我怀疑我会因为不得不扫描文件两次而大量停靠，我们的讲师倾向于关注最有效的路线。感谢您的指导。 – Saf 2013-03-15 00:49:47
内存约束建议使用某种自适应编码。算术编码很好。但是你没有具体说明性能。该算法是否必须打击特定类文件上的任何性能目标？一个仅仅复制文件的算法符合上述要求，（但不会教你太多）。
对于语言的选择，请使用您更舒适的东西。要执行很多位操作，所以C或Java都适合。你应该编写一些代码来处理将文件转换成比特流并返回，并将其作为一个单独的模块。我可以看到用C或Java来做这件事。
除了“尽可能做到最佳”之外，我们没有任何绩效目标，我知道的含糊不清，但我怀疑这是挑战的一部分。它应该适用于任何类型的文件，所以我们不必担心文件是音频还是视频等，除了可能检查我们没有最终信息扩展 – Saf 2013-03-15 00:58:21
你应该在你的班级学到定理：无损压缩方法可以压缩所有文件。但这听起来像是他要求某种标准方法。另外请注意，您可以输入2次文件（2次仍然是成比例的）。您只是不允许将整个文件保存在内存中。 – UncleO 2013-03-15 01:05:27
我们只是通过课程的一半，我们从算法开始，然后转向不同类型的文件，即GIF，MP3等。但这是一个很好的观点，我会问演讲者是否应该优化它某些文件类型。 – Saf 2013-03-15 01:29:58
只是LZW，没有其他编码，很简单，工作出奇的好。现在没有人会真正使用LZW，因为还有其他算法可以更快地进行压缩。然而对于任务来说，你无法打败LZW的简单。没有霍夫曼，动态或其他。没有香农 - 法诺。没有算术或范围编码。是的，内存使用量与消息的长度无关。 Mark Nelson写了一个very good explanation。
您可以用C或Java来完成，但C可能不太容易出错，因为它具有无符号类型。
如果90％以前使用霍夫曼提交的意见都是错误的，也许这对您而言是一个更好的挑战。 – 2013-03-15 00:14:02
Shannon-Fano不符合您的（3）要求吗？得到正确的结果非常简单。如果你以前从未实现过压缩算法，我会建议S-F。 – 2013-03-15 00:14:45
如果您确实参加了LZW-Dynamic-Huffman路线，除了* Dr.Dobbs 1989文章（http：//www.drdobbs）中提出的建议之外，我唯一的意见是使用near- *任何人的* LZW技术*。 COM /体系结构和设计/ LZW数据压缩/ 184408217）。我在算法中发现了对特里韦尔奇“错误”的“分析”，以及作者对该问题的“解决方案”给读者和韦尔奇先生造成了侮辱，韦尔奇坦率地忘记了数据压缩算法，而不是该文章的作者将永远知道。 – WhozCraig 2013-03-15 00:43:55