Need some ideas for simple lossless compression algorithms in C++

1
votes

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.

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:

  • 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

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.

1
c++algorithmstlcompression
you're allowed to use cstring? please unroll... - deW1
LZW. Doesn't get much simpler than that, and it can be implemented very efficiently with a hash table. P. S. If your professor doesn't allow you use STL and other widely used libraries for your C++ programming project, he must be stupid. - Violet Giraffe
What class are you taking? Bad Programming 201 C++ without the ++ - NathanOliver
If you cannot use a std::map or std::multimap what's stopping you from implementing a very basic version of your own that gets the job done? - AndyG
Probably start with RLE for BMP images, LZW for executables. Horses for courses. And a little use of your favourite search engine might give you better ideas sooner than a long-winded comment-chat here. - High Performance Mark

1 Answers

2
votes

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

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)