String Compression Algorithm

Question

I've been wanting to compress a string in C++ and display it's compressed state to console. I've been looking around for something and can't find anything appropriate so far. The closest thing I've come to finding it this one:

How to simply compress a C++ string with LZMA

However, I can't find the lzma.h header which works with it anywhere.

Basically, I am looking for a function like this:

std::string compressString(std::string uncompressedString){
//Compression Code

return compressedString;
}

The compression algorithm choice doesn't really matter. Anybody can help me out finding something like this? Thank you in advance! :)

Have you looked at zlib? If you're storing binary I wouldn't put it back in a string. — Ryan Guthrie
– Ryan Guthrie, Commented Nov 19, 2012 at 17:05
If your string is long enough, you can spot periodic parts and turn them into short functions. If it is totally random, it will be less compressible. If it is made of lots of sequential + same chars, it will be more compressible. — huseyin tugrul buyukisik
– huseyin tugrul buyukisik, Commented Nov 19, 2012 at 17:06
Huffman encoding, Run Length Encoding (RLE), Delta-encoding. Alternately, if you're not actually interested in understanding the algorithm, get zlib. It's already in your phone, telly, browser, PS3, XBOX, etc, etc. It works, it's portable and it's ready to consume. — enhzflep
– enhzflep, Commented Nov 19, 2012 at 17:17

fvu · Accepted Answer · 2012-11-19 17:34:58Z

6

Based on the pointers in the article I'm fairly certain they are using XZ Utils, so download that project and make the produced library available in your project.

However, two caveats:

dumping a compressed string to the console isn't very useful, as that string will contain all possible byte values, most of which aren't displayable on a console
compressing short strings (actually any small quantity of data) isn't what most general-purpose compressors were designed for, in many cases the compressed result will be as big or even bigger than the input. However, I have no experience with LZMA on small data quantities, an extensive test with data representative for your use case will tell you whether it works as expected.

One algorithm I've been playing with that gives good compression on small amounts of data (tested on data chunks sized 300-500 bytes) is range encoding.

edited Nov 19, 2012 at 17:34

answered Nov 19, 2012 at 17:29

fvu

33.1k6 gold badges64 silver badges84 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Hirvesh Over a year ago

hey, thank you for your great answer! Actually I don't need to really write the compressed string to console. I just need to compare it with other compressed string. Is there a C++ implementation available for range encoding, preferably for string compression?

Collectives™ on Stack Overflow

String Compression Algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related