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

Groups > comp.programming > #3511 > unrolled thread

compressable data

Back to article view | Back to comp.programming

Contents

  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

#3511 — compressable data

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]

#3512

Am 22.06.2013 14:52, 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?

Maybe you should also post to comp.compression.

M. K. Shen

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

#3618

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.

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

#3621

On Sunday, July 7, 2013 2:44:57 PM UTC+1, Tim Rentsch wrote:
> 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).
> 
> 
> 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 long as the added redundancy is done using a deterministic
> algorithm, it should be possible to calculate a theoretical 
> compression factor.
> 
If we know that the distribution is a non-random selection from the character
set a-z (say), but the order is random, then we can devise an optimal
or near-optimal Huffman compressor. Similarly if we know that the distribution
consists of a random selection of N concatenated strings from a set. Similarly
if we can build a Markov model so that symbol A predicts the following symbol
with some accuracy.

There are lots of models. But real data, like English text, shows virtually 
all of these characteristics. The character set is non-random, the words 
are non-random, and both at the character and at the word level there is 
a Markov chain type relationship. So it's very hard to say what the real 
entropy of text is.

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

#3622

<malcolm.mclean5@btinternet.com> wrote

<new stuff at end>
in message news:319e8d2f-c636-4d3f-9820-00d28ed2a95d@googlegroups.com...
> On Sunday, July 7, 2013 2:44:57 PM UTC+1, Tim Rentsch wrote:
>> 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).
>>
>>
>> 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 long as the added redundancy is done using a deterministic
>> algorithm, it should be possible to calculate a theoretical
>> compression factor.
>>
> If we know that the distribution is a non-random selection from the 
> character
> set a-z (say), but the order is random, then we can devise an optimal
> or near-optimal Huffman compressor. Similarly if we know that the 
> distribution
> consists of a random selection of N concatenated strings from a set. 
> Similarly
> if we can build a Markov model so that symbol A predicts the following 
> symbol
> with some accuracy.
>
> There are lots of models. But real data, like English text, shows 
> virtually
> all of these characteristics. The character set is non-random, the words
> are non-random, and both at the character and at the word level there is
> a Markov chain type relationship. So it's very hard to say what the real
> entropy of text is.

There is a wonderful, fascinating, and very readable, book on the entropy of 
English, _Silicon Dreams_ by Robert W Lucky.
As I understand it, he thinks Lempel-Ziv compression is as good as it gets 
for English text.  It seems entirely possible that Lempel-Ziv is buried in 
gzip.  LZW (remember the patent problems?) stands for Lempel-Ziv-Welch.

On the OPs question, I have to insert words into the question in order for 
it to have any meaning to me. Generate data.  Generate *real* data?  What is 
data?  Is a journal article on some obscure branch of medicine or chemistry 
data?  Is rap music data?  By changing the definition of data, I change the 
compression ratio.  But the OP, as I read it, wants it to be constant.  I 
sense a problem. 

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

#3624

On Tuesday, July 9, 2013 7:33:52 PM UTC+1, osmium wrote:
> <malcolm.mclean5@btinternet.com> wrote
> 
> On the OPs question, I have to insert words into the question in order for 
> it to have any meaning to me. Generate data.  Generate *real* data?  What is 
> data?  Is a journal article on some obscure branch of medicine or chemistry 
> data?  Is rap music data?  By changing the definition of data, I change the 
> compression ratio.  But the OP, as I read it, wants it to be constant.  I 
> sense a problem.
>
With real data, it's very hard to define the entropy. But with random data,
non-randomised by some rule, it can be relatively easy. So data which consisted 
of a discretised normal Markov model (so character i + 1 = character[i] + (int) randgauss(), with wrap ) has a known entropy, and can be ideally compressed
with a predictive algorithm with a single byte of state.
 

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

#3625

<malcolm.mclean5@btinternet.com> wrote:

> On Tuesday, July 9, 2013 7:33:52 PM UTC+1, osmium wrote:
>> <malcolm.mclean5@btinternet.com> wrote
>>
>> On the OPs question, I have to insert words into the question in order 
>> for
>> it to have any meaning to me. Generate data.  Generate *real* data?  What 
>> is
>> data?  Is a journal article on some obscure branch of medicine or 
>> chemistry
>> data?  Is rap music data?  By changing the definition of data, I change 
>> the
>> compression ratio.  But the OP, as I read it, wants it to be constant.  I
>> sense a problem.
>>
> With real data, it's very hard to define the entropy. But with random 
> data,
> non-randomised by some rule, it can be relatively easy. So data which 
> consisted
> of a discretised normal Markov model (so character i + 1 = character[i] + 
> (int) randgauss(), with wrap ) has a known entropy, and can be ideally 
> compressed
> with a predictive algorithm with a single byte of state.

It looks like we disagree on what the meaning of "data" is; to me, data has 
meaning.  What I see you discussing is random bits. If there is no means of 
converting bits to something else, (by talking to a programmer, for example) 
it is just bits - no meaning - no data. 

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

#3646

malcolm.mclean5@btinternet.com writes:

> On Sunday, July 7, 2013 2:44:57 PM UTC+1, Tim Rentsch wrote:
>> 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).
>> 
>> 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 long as the added redundancy is done using a deterministic
>> algorithm, it should be possible to calculate a theoretical 
>> compression factor.
> 
> If we know that the distribution is a non-random selection from
> the character set a-z (say), but the order is random, then we can
> devise an optimal or near-optimal Huffman compressor.  Similarly
> if we know that the distribution consists of a random selection of
> N concatenated strings from a set.  Similarly if we can build a
> Markov model so that symbol A predicts the following symbol with
> some accuracy.
>
> There are lots of models.  But real data, like English text, shows
> virtually all of these characteristics.  The character set is
> non-random, the words are non-random, and both at the character
> and at the word level there is a Markov chain type relationship.
> So it's very hard to say what the real entropy of text is.

These comments have no bearing on my statement.  It is possible
to calculate a theoretical compression factor without resorting
to any scheme along such lines.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web