Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3618

Re: compressable data

Show all headers | View raw

Ian Collins <ian-news@hotmail.com> writes:

> I'm looking for an algorithm I can use to generate data that will have
> a fixed compress ratio when compressed with an ideal compression
> algorithm (or gzip as a practical compressor).
>
> I want to produce files that will compress by a given percentage in
> order to test performance of a filesystem with compression enabled.

Not sure whether you mean speed performance or space performance,
although maybe that doesn't matter.

> Any ideas?

The following ideas may be obvious.

1. Start with a source of high-quality random numbers (call
this R).  If the quality is high enough, R will not be
compressible at all.  To protect against weaknesses in the
random number generation, you might want to compress R using
a good compression algorithm (eg, LZMA compression), and use
the resulting sequence R' as the input to the next stage.

2. Starting with the random numbers from (1), algorithmically
add some redundancy of known percentage.  There are lots of
possible variations on this theme, as for example:  a. take
in one character, simply output it twice in a row;  b. take
in five characters, output the five, then output again the
first, third, fifth;  c. take in a block of 256 characters,
output the block, then apply a fixed permutation and output
the 256 characters after being permuted;  d. take in a sequence
of K characters, where K cycles deterministically among a
set of 10 fibonacci numbers, output the sequence, then output
two deterministic subsequences, eg, consisting of lengths of
the two preceeding fibonacci numbers, alternating between the
two so they are as evenly distributed in the original sequence
as possible;  e. etc...
   As long as the added redundancy is done using a deterministic
algorithm, it should be possible to calculate a theoretical
compression factor.

3. Assuming what's being measured is space performance, rather
than measuring against a theoretical compression factor, measure
against other compression algorithms known to produce good
results.  For example, starting with the output sequence of stage
(2), do LZMA compression and bzip2 compression on it, and call the
better compression factor of those two the "theoretical"
compression factor.  (I believe LZMA will almost always beat
bzip2, but that's not important.)  Of course you could always
compare against both, the true theoretical limit and the empirical
limit determined by applying other compression algorithms.  As
a practical matter, any algorithm that yields a total size within
one percent of the total size after LZMA compression is one I
would call pretty darn good.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

compressable data Ian Collins <ian-news@hotmail.com> - 2013-06-23 00:52 +1200
  Re: compressable data Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-06-22 15:06 +0200
  Re: compressable data Tim Rentsch <txr@alumni.caltech.edu> - 2013-07-07 06:44 -0700
    Re: compressable data malcolm.mclean5@btinternet.com - 2013-07-09 10:42 -0700
      Re: compressable data "osmium" <r124c4u102@comcast.net> - 2013-07-09 13:33 -0500
        Re: compressable data malcolm.mclean5@btinternet.com - 2013-07-13 08:01 -0700
          Re: compressable data "osmium" <r124c4u102@comcast.net> - 2013-07-13 10:58 -0500
      Re: compressable data Tim Rentsch <txr@alumni.caltech.edu> - 2013-08-02 17:30 -0700

csiph-web