2 ms·

Hello, I wrote this lib as an initial test on short strings compression. It seems like it can be useful for things like memcached, Redis, and alike, but may als

by antirez 18y ago

Hello, I wrote this lib as an initial test on short strings compression. It seems like it can be useful for things like memcached, Redis, and alike, but may also be a good idea to make your MySQL DB shorter (chats, logs, user messages, news titles, urls, can all be compressed with this lib). In the README there is some info about the lib, the usage is brain-dead simple. It's code of few hours ago, but should be pretty stable already, with this kind of programming what's nice is that you can encrypt/decrypt millions of strings from /dev/urandom to spot obvious bugs in very short time. I wonder if this lib can be useful to somebody else. Some example: 'This is a small string' compressed by 50% 'foobar' compressed by 34% 'the end' compressed by 58% 'not-a-g00d-Exampl333' enlarged by 15% 'Smaz is a simple compression library' compressed by 39% 'Nothing is more difficult, and therefore more precious, than to be able to decide' compressed by 49% 'this is an example of what works very well with smaz' compressed by 49% '1000 numbers 2000 will 10 20 30 compress very little' compressed by 10%

Luc 18y ago
Very neat! Could you explain a bit how this would help with memcached and Redis? Is the idea to keep memory usage down (apologies if this is obvious, I haven't used memcached (yet))?
- antirez 18y ago
  Hello Luc, immagine you want to store millions of SMS messages into a memcached or Redis server. Memory usage can be a problem, compressing this data with Smaz you can use half the number of servers needed otherwise. The same works for URLs as well. Compression examples against URLs: 'http://google.com' compressed by 59% 'http://programming.reddit.com' compressed by 52% 'http://github.com/antirez/smaz/tree/master' compressed by 46%
rw 18y ago
"[...] with this kind of programming what's nice is that you can encrypt/decrypt millions of strings from /dev/urandom [...]" How many of those pseudorandom strings are you able to compress, in general?
- antirez 18y ago
  Most of this random strings will "globally" enlarge, but will locally compress. For example sequences of compressible subsequences of two-three bytes are very frequent. The remaining data that can't be compressed will stress the other code that emits verbatim uncompressed sequences. To stress more the compression with valid sequences it's possible to use a very big HTML file and get ranges at random instead to get this strings from /dev/urandom
joeyo 18y ago
What are you doing to achieve the compression? Huffman coding (or a similar symbol code)?
- antirez 18y ago
  no, you can "add" Huffman coding to this algorithm to get better compression (but it will be much slower). What I used is a modified version of the LZ algorithm family, but instead of a table assembled from the data I'm compressing I use a fixed one. It's basically a simple table-lookup, with two special bytes needed to emit verbatim bytes.
jcl 18y ago
It looks like your encoding routine could get better compression if it weighed alternative encodings more carefully. For example, "not-a-g00d-Exampl333" could be better compressed as a single run of literal characters rather than as several runs of literal characters interspersed with codebook entries. (In this sense, the single letter codebook entries might not be helping your compression ratio.)
- antirez 18y ago
  jcl yes this is a compromise, if you check smaz_compress it does this kind of checks but only in order to glue together consecutive verbatim outputs into a single one (up to 256 bytes), but does not back-check if a single byte interruption is not worth it. I think this can be an option that can be done in a second-pass way if a given #define is active. Thanks for the useful comment.
chime 18y ago
I was just looking for something like this last weekend. I am making an app in which the URL contains lots of different parameters and it is generated using JS. Compressing this long query-string would be awesome. I haven't looked at your code yet but do you think it would be possible to have a JS library that does just this? Maybe a jQuery plugin?
- antirez 18y ago
  Hello chime, it should be very simple to port the lib to JS. Given that JS supports hashes you get a much shorter implementation compared to the C one.

by antirez 18y ago

Luc 18y ago

Very neat! Could you explain a bit how this would help with memcached and Redis? Is the idea to keep memory usage down (apologies if this is obvious, I haven't used memcached (yet))?

antirez 18y ago
Hello Luc, immagine you want to store millions of SMS messages into a memcached or Redis server. Memory usage can be a problem, compressing this data with Smaz you can use half the number of servers needed otherwise. The same works for URLs as well. Compression examples against URLs: 'http://google.com' compressed by 59% 'http://programming.reddit.com' compressed by 52% 'http://github.com/antirez/smaz/tree/master' compressed by 46%

rw 18y ago

"[...] with this kind of programming what's nice is that you can encrypt/decrypt millions of strings from /dev/urandom [...]" How many of those pseudorandom strings are you able to compress, in general?

antirez 18y ago
Most of this random strings will "globally" enlarge, but will locally compress. For example sequences of compressible subsequences of two-three bytes are very frequent. The remaining data that can't be compressed will stress the other code that emits verbatim uncompressed sequences. To stress more the compression with valid sequences it's possible to use a very big HTML file and get ranges at random instead to get this strings from /dev/urandom

joeyo 18y ago

What are you doing to achieve the compression? Huffman coding (or a similar symbol code)?

antirez 18y ago
no, you can "add" Huffman coding to this algorithm to get better compression (but it will be much slower). What I used is a modified version of the LZ algorithm family, but instead of a table assembled from the data I'm compressing I use a fixed one. It's basically a simple table-lookup, with two special bytes needed to emit verbatim bytes.

jcl 18y ago

It looks like your encoding routine could get better compression if it weighed alternative encodings more carefully. For example, "not-a-g00d-Exampl333" could be better compressed as a single run of literal characters rather than as several runs of literal characters interspersed with codebook entries. (In this sense, the single letter codebook entries might not be helping your compression ratio.)

antirez 18y ago
jcl yes this is a compromise, if you check smaz_compress it does this kind of checks but only in order to glue together consecutive verbatim outputs into a single one (up to 256 bytes), but does not back-check if a single byte interruption is not worth it. I think this can be an option that can be done in a second-pass way if a given #define is active. Thanks for the useful comment.

chime 18y ago

I was just looking for something like this last weekend. I am making an app in which the URL contains lots of different parameters and it is generated using JS. Compressing this long query-string would be awesome. I haven't looked at your code yet but do you think it would be possible to have a JS library that does just this? Maybe a jQuery plugin?

antirez 18y ago
Hello chime, it should be very simple to port the lib to JS. Given that JS supports hashes you get a much shorter implementation compared to the C one.