1
$\begingroup$

I need to compress a string in my application but I am very limited in the operations I can perform. In particular, I cannot store data in any file and I cannot query any database. Also, I cannot call any library so I have to code my own data compression algorithm. What would be the simplest algorithm to achieve this goal? I could code the smaz algorithm myself but it does not seem to work very well with long strings.

$\endgroup$
7
4
$\begingroup$

If you need something reasonably effective but not very taxing to implement, I would recommend LZW.

LZW has several advantages, not the least of which is that it uses fixed-width codes (the width strictly increases as compression proceeds), rather than Huffman or arithmetic coding. It also does not require string searching through a sliding window, instead performing hash table or tree lookup per input character. This means that it requires significantly less code to implement than methods based on LZ77.

$\endgroup$
0
3
$\begingroup$

The simplest (besides "no compression at all") is RLE.

RLE is useless on many kinds of data, but better kinds of general-purpose compression require more complex algorithms.

$\endgroup$
3
  • $\begingroup$ It is simple indeed and it does not require any external data. However, I am looking for something a little more efficient than this. I want to encode a json string or an xml string. I am not sure RLE will be very useful for that case. $\endgroup$ – Florian Lavorel Jan 13 at 14:46
  • $\begingroup$ If it's json consider using the msgpack format? Maybe together with RLE for msgpack strings. If you only need a subset of json it might be easy to implement a parser yourself. $\endgroup$ – user82867 Jan 13 at 16:00
  • $\begingroup$ Thank you for the idea but msgpack does not look like a simple algorithm to code yourself and unfortunately I cannot rely on any external library. $\endgroup$ – Florian Lavorel Jan 14 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.