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

Groups > comp.programming > #3622

Re: compressable data

Show key headers only | View raw

<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. 

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