I'm taking an intro to programming course and one of our assignments is to write a lossless compression program in C++. The only limitations we have are that we can not use the STL, static variables, or global variables. A lot of the compression algorithms I have found require use of map/multimap which I am not allowed to use so Huffman encoding and LZW are pretty much out of the question unless I can write my own map class and get it to work.
我正在参加编程课程,我们的一项任务是用C ++编写无损压缩程序。我们唯一的限制是我们不能使用STL,静态变量或全局变量。我发现很多压缩算法都需要使用map / multimap,我不允许使用它,所以除非我能编写自己的map类并让它工作,否则Huffman编码和LZW几乎是不可能的。
A lot of algorithms I found also use std::string, but I am perfectly fine using cstring (which we are allowed to use). I also have access to some libraries created by my professor that we can use. We have access to the following:
我发现很多算法也使用std :: string,但我使用cstring(我们可以使用)完全没问题。我也可以访问我的教授创建的一些我们可以使用的库。我们可以访问以下内容:
- Various trees such as Red-Black, AVL, Splay
- Binary Heap
- Various hash tables such as several open addressing implementations, as well as separate chaining
- Vector, Linked List, and Queue
各种树木,如红黑,AVL,Splay
各种哈希表,例如几个开放寻址实现,以及单独的链接
矢量,链接列表和队列
So anything besides the above I would have to write the code for myself.
所以除了上面的任何内容我都必须为自己编写代码。
Does anyone have any very simple lossless compression algorithms they would recommend? Huffman and the other compression algorithms I found online seem very complex, not to mention I cannot use map/multimap in STL :(. I'm not looking for the absolute fastest algorithm here, just something to serve as a starting point and we will adjust it as needed to make it run faster.
有没有人有他们推荐的非常简单的无损压缩算法?我在网上发现的霍夫曼和其他压缩算法看起来非常复杂,更不用说我不能在STL中使用map / multimap :(。我不是在寻找绝对最快的算法,只是作为一个起点,我们将根据需要调整它以使其运行更快。
1 个解决方案
#1
A lot of the compression algorithms I have found require use of map/multimap which I am not allowed to use so Huffman encoding and LZW are pretty much out of the question
我发现很多压缩算法都需要使用map / multimap,我不允许使用它,所以Huffman编码和LZW几乎是不可能的
Huh? Of course not. Maps are a quite thin abstraction implementable on one of your trees or hash table implementations.
咦?当然不是。映射是一种非常精简的抽象,可以在您的一个树或哈希表实现上实现。
unless I can write my own map class and get it to work
除非我可以编写自己的地图类并让它工作
So that's likely the point of the exercise.
所以这可能就是演习的重点。
Just go ahead. You can do OO in assembly. You can write algorithms without (ready-made) datastructures. It's just more work. And more error prone. And more educational (I hope :) Clearly good tuition is required too)
前进吧。你可以在装配中做OO。您可以编写没有(现成的)数据结构的算法。这只是更多的工作。而且更容易出错。更多的教育(我希望:)显然也需要良好的学费)
#1
A lot of the compression algorithms I have found require use of map/multimap which I am not allowed to use so Huffman encoding and LZW are pretty much out of the question
我发现很多压缩算法都需要使用map / multimap,我不允许使用它,所以Huffman编码和LZW几乎是不可能的
Huh? Of course not. Maps are a quite thin abstraction implementable on one of your trees or hash table implementations.
咦?当然不是。映射是一种非常精简的抽象,可以在您的一个树或哈希表实现上实现。
unless I can write my own map class and get it to work
除非我可以编写自己的地图类并让它工作
So that's likely the point of the exercise.
所以这可能就是演习的重点。
Just go ahead. You can do OO in assembly. You can write algorithms without (ready-made) datastructures. It's just more work. And more error prone. And more educational (I hope :) Clearly good tuition is required too)
前进吧。你可以在装配中做OO。您可以编写没有(现成的)数据结构的算法。这只是更多的工作。而且更容易出错。更多的教育(我希望:)显然也需要良好的学费)