Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "osmium" Newsgroups: comp.programming Subject: Re: compressable data Date: Tue, 9 Jul 2013 13:33:52 -0500 Lines: 52 Message-ID: References: <319e8d2f-c636-4d3f-9820-00d28ed2a95d@googlegroups.com> X-Trace: individual.net wuqnmYP554kAhLkxQVNX8A3BRE3bVHMX5sVhXZf+F77YTKo5Ds Cancel-Lock: sha1:wu/fHGepi0NSXHnwx4ttG4sCsFI= X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.2180 X-RFC2646: Format=Flowed; Original X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 Xref: csiph.com comp.programming:3622 wrote 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 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.