编程新手：如何编写自己的数据压缩算法？

Question

现在是夏天，因此我决定自己编写一个数据压缩程序，最好使用C代码。我基本了解压缩的工作原理，只有几个问题：

1）C语言是否适合完成这个任务？
2）在输入文件中应该使用字节还是二进制级别进行处理？

如果有人能够给我正确的指导，我会非常感激。我想自己编写代码，而不使用预先存在的压缩库或类似的东西。

- araisbec

---

很有趣又能增长知识，这有什么不好的呢？ - mwcz

看一下哈夫曼编码的算法http://en.wikipedia.org/wiki/Huffman_coding 这是一个很好的例子算法，可以帮助你入门。 - Dana the Sane

Answer 1

你可以从霍夫曼编码开始学习。很多计算机科学课程都会将其作为一个项目来实现，所以应该是可行的。C语言适合用于霍夫曼编码，但最好先在高级语言中完成，以便理解概念。宾夕法尼亚大学的硕士级项目提供幻灯片、提示和示例项目供参考（在该页面上搜索“huff”）。

- Brian Lyttle

Answer 2

回答你的问题:

1. C语言是适合的。
2. 这取决于算法，或者你如何考虑“压缩”。

我的意见是，首先决定你想做无损压缩还是有损压缩，然后选择一个算法来实现。以下是一些指针:

对于无损压缩，有些非常直观，比如跑长度编码(run-length encoding)， 例如，如果有11个a和5个b，你只需将它们编码为11a5b。 有些算法使用一个字典(dictionary)，请参考LZW编码(LZW encoding)。 最后，我建议使用Huffman编码(Huffman encoding)，因为它非常直截了当、简单，并有助于在学习算法时获得经验(供教育目的使用)。

对于有损压缩，JPEG压缩中使用离散傅立叶变换(Discrete Fourier Transform,DFT)或小波(wavelet)。这对了解多媒体压缩很有用。

维基百科page是一个很好的起点。

- Ivan Xiao

Answer 3

1. 是的，C语言非常适合这种工作。

2. 你使用字节还是位取决于你决定实现的算法。例如，哈夫曼编码本质上是面向位的，而许多其他压缩算法则不是。

- NPE

Answer 4

1. C语言是编写压缩程序的好选择，当然你也可以使用其他很多编程语言。

2. 由于计算机不能直接寻址比字节更小的存储单位（按定义来说），因此使用字节进行操作是个不错的选择。你所选择的压缩算法将会影响你对数据的操作方式。

祝你好运！

- Carl Norum

Answer 5

1) C语言是否适合完成这个任务？

是的。

2) 我应该使用字节处理输入文件吗？还是以某种二进制级别进行处理？

它们是相同的，所以这个问题没有意义。

不使用现有的压缩库

你可以使用现有的压缩算法吗？有许多"压缩算法"，在谷歌上搜索会展示很多有用的信息。

- S.Lott

---

我提到了使用字节进行工作，而不是在更低的级别上以某种方式管理较小的位组。我已经阅读了有关哈夫曼压缩的资料，它似乎是使用单个位来工作，除非我理解错了。 - araisbec

比特始终被组合成字节，字节是最小的粒度。你的算法可能会处理比特，但它是通过访问、修改和存储整个字节的比特来实现的。 - S.Lott