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

Groups > comp.compression > #1980 > unrolled thread

Generating data that can be compressed with a known ratio

Back to article view | Back to comp.compression

Contents

  Generating data that can be compressed with a known ratio Ian Collins <ian-news@hotmail.com> - 2013-06-23 10:59 +1200
    Re: Generating data that can be compressed with a known ratio glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-06-22 23:24 +0000
    Re: Generating data that can be compressed with a known ratio SG <sgesemann@gmail.invalid> - 2013-06-23 01:45 +0200
    Re: Generating data that can be compressed with a known ratio hitchmanr@gmail.com - 2013-06-24 11:53 -0700
      Re: Generating data that can be compressed with a known ratio glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-06-24 19:15 +0000
        Re: Generating data that can be compressed with a known ratio hitchmanr@gmail.com - 2013-06-24 13:44 -0700
          Re: Generating data that can be compressed with a known ratio Ian Collins <ian-news@hotmail.com> - 2013-06-25 10:18 +1200
            Re: Generating data that can be compressed with a known ratio hitchmanr@gmail.com - 2013-06-24 16:57 -0700
              Re: Generating data that can be compressed with a known ratio Ian Collins <ian-news@hotmail.com> - 2013-06-25 13:58 +1200
    Re: Generating data that can be compressed with a known ratio Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2013-06-27 10:08 +0300

#1980 — Generating data that can be compressed with a known ratio

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.

Any ideas?

-- 
Ian Collins

[toc] | [next] | [standalone]

#1981

Ian Collins <ian-news@hotmail.com> wrote:
> 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).

Choose letter randomly from an appropriate sized alphabet.

If your data has other correlations, then some algorithms
will find them, and others won't, so the compression will be
different.

For random data from an N character alphabet, on a system using
bytes, the compression will be log(N)/log(256). 

-- glen

[toc] | [prev] | [next] | [standalone]

#1982

Am 23.06.2013 00:59, schrieb Ian Collins:
> 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.
> 
> Any ideas?

How about this:

goal: compressed filesize = 80%

=> 0.8 bits of entropy per source file bit

=> solve 0.8 = -(p*log2(p)+(1-p)*log2(1-p)) for p

   p=0.24300385...

Generate randon bits, a zero with probability p and a one with
probability 1-p

LZ and LZW are supposed to aproach the entropy 0.8 (asymptotically)
IIRC. But the compressors will likely produce some overhead which could
be accounted for to some degree.

Cheers!
SG

[toc] | [prev] | [next] | [standalone]

#1983

If it's a filesystem compressor, it's probably byte-oriented and doesn't perform entropy coding, so a stream of random bytes selected from a small subset of possible bytes will be incompressible.

Try generating a random string of bytes, and then repeating it some number of times. A string of 100 random bytes repeated 5 times should be compressed ~5x, disregarding overhead. That same string repeated 4.5 times (with half the string last time) will be around ~4.5x compression. Tweak as needed, varying string lengths, maybe shuffling them around as well.

[toc] | [prev] | [next] | [standalone]

#1984

hitchmanr@gmail.com wrote:
> If it's a filesystem compressor, it's probably byte-oriented and 
> doesn't perform entropy coding, so a stream of random bytes 
> selected from a small subset of possible bytes will 
> be incompressible.

Byte oriented compression algorithms, like LZW, work fine on
random strings of a subset of the possible bytes. Repeated
strings appear appropriately more likely as the alphabet
size is reduced.

-- glen

[toc] | [prev] | [next] | [standalone]

#1985

On Monday, June 24, 2013 12:15:13 PM UTC-7, glen herrmannsfeldt wrote:> 
> 
> Byte oriented compression algorithms, like LZW, work fine on
> random strings of a subset of the possible bytes. Repeated
> strings appear appropriately more likely as the alphabet
> size is reduced.
> 
> -- glen

By "byte oriented", I mean compressors that read and emit series of bytes (Snappy, LZ4, LZNT1), rather than series of bits, since they tend to be the only ones fast enough to be used for transparent compression.

[toc] | [prev] | [next] | [standalone]

#1986

hitchmanr@gmail.com wrote:
> On Monday, June 24, 2013 12:15:13 PM UTC-7, glen herrmannsfeldt
> wrote:>
>>
>> Byte oriented compression algorithms, like LZW, work fine on random
>> strings of a subset of the possible bytes. Repeated strings appear
>> appropriately more likely as the alphabet size is reduced.
>
> By "byte oriented", I mean compressors that read and emit series of
> bytes (Snappy, LZ4, LZNT1), rather than series of bits, since they
> tend to be the only ones fast enough to be used for transparent
> compression.

The algorithms used by ZFS are LZJB, ZLE, and gzip.

Thank's to everyone who has replied, I've probably got enough pointers 
to start fiddling.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#1987

On Monday, June 24, 2013 3:18:39 PM UTC-7, Ian Collins wrote:
> The algorithms used by ZFS are LZJB, ZLE, and gzip.

LZJB is almost identical to LZNT1 (used by NTFS). There are only so many ways to encode LZ77 in a byte-stream, I suppose.

Snappy: Byte tag + optional extra data to indicate whether following bytes are literal or copy sequence
LZ4: Encode pairs of sequences of literals and a copy operation.
LZNT1/LZJB: Tag byte indicating whether next 8 elements are 1 byte literals or 2 byte copies. 2 byte copy: LZJB: 6 bit match length, 10 bit match offset; LZNT1: adjust length/offset sizes based on amount of uncompressed data processed.

ZLE is an (almost useless?) RLE transform that only compresses zeros.

[toc] | [prev] | [next] | [standalone]

#1988

hitchmanr@gmail.com wrote:
> On Monday, June 24, 2013 3:18:39 PM UTC-7, Ian Collins wrote:
>> The algorithms used by ZFS are LZJB, ZLE, and gzip.
>
> LZJB is almost identical to LZNT1 (used by NTFS). There are only so
> many ways to encode LZ77 in a byte-stream, I suppose.
>
> Snappy: Byte tag + optional extra data to indicate whether following
> bytes are literal or copy sequence LZ4: Encode pairs of sequences of
> literals and a copy operation. LZNT1/LZJB: Tag byte indicating
> whether next 8 elements are 1 byte literals or 2 byte copies. 2 byte
> copy: LZJB: 6 bit match length, 10 bit match offset; LZNT1: adjust
> length/offset sizes based on amount of uncompressed data processed.
>
> ZLE is an (almost useless?) RLE transform that only compresses
> zeros.

Useful if there plenty of sparse files.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#1992

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.
> 
> Any ideas?

On top of all the other answers given (reduce the alphabet, and 
bias the bit distribution), assuming your files are long, the 
easiest *dumb* solution is to just generate the appropriate ratio 
of known incompressible data from a decent PRNG, and intersperse 
chunks of that with chunks of trivially compressible data (runs of
0, say). If might take a short while for the model to learn its in
a run of zeros, but the overhead shouldn't be too much (also, the
incompressible data may expand by a bit, as that's what compression
functions do, and that would need to be taken into consideration if
you want accuracy.)

However, it's probably better to just use a corpus of real world
files, as that's what people using the algorithm in the real world
will be doing.

Phil
-- 
If "law-abiding citizens have nothing to fear" from privacy-invading 
technologies and policies, then law-abiding governments should have
nothing to fear from whistleblowers.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web