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

Groups > sci.physics > #588781 > unrolled thread

Compression of random binary data

Back to article view | Back to sci.physics

Contents

  Compression of random binary data jonas.thornvall@gmail.com - 2016-07-11 10:50 -0700
    Re: Compression of random binary data xxein1@att.net - 2016-07-11 13:12 -0700
    Re: Compression of random binary data Sergio <invalid@invalid.com> - 2016-07-11 15:42 -0500
    Re: Compression of random binary data Double-A <double-a3@hush.com> - 2016-07-11 13:58 -0700
      Re: Compression of random binary data Poutnik <poutnik4nntp@gmail.com> - 2016-07-11 23:12 +0200
    Re: Compression of random binary data "nuny@bid.nes" <Alien8752@gmail.com> - 2016-07-11 15:20 -0700
      Re: Compression of random binary data Sergio <invalid@invalid.com> - 2016-07-11 21:29 -0500
    Re: Compression of random binary data Lofty Goat <rlwatkins@gmail.com> - 2016-07-11 17:48 -0500
    Re: Compression of random binary data Fabian Russell <fb@zen.info> - 2016-07-11 23:39 +0000
      Re: One _never_ knows if data is truly random or not. Fabian Russell <fb@zen.info> - 2016-07-12 14:33 +0000
        Re: One _never_ knows if data is truly random or not. Poutnik <poutnik4nntp@gmail.com> - 2016-07-12 18:37 +0200
      Re: One _never_ knows if data is truly random or not. benj <benj@nobody.net> - 2016-07-12 19:26 -0400
    Re: Compression of random binary data Sylvia Else <sylvia@not.at.this.address> - 2016-07-12 15:20 +1000
      Re: Compression of random binary data Double-A <double-a3@hush.com> - 2016-07-12 13:29 -0700
        Re: Compression of random binary data Sylvia Else <sylvia@not.at.this.address> - 2016-07-13 16:29 +1000
    Re: Compression of random binary data Michael J. Strickland <michael06582@comcast.net> - 2016-07-14 00:54 -0400

#588781 — Compression of random binary data

What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data? 

I only know that Shanon theorised it could not be done, but were there any proof? 

What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset. 

Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation. 

Now the inpretator or program must know the rules. And i have very good rules to make it happen. 

[toc] | [next] | [standalone]

#588810

On Monday, July 11, 2016 at 1:50:49 PM UTC-4, jonas.t...@gmail.com wrote:
> What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data? 
> 
> I only know that Shanon theorised it could not be done, but were there any proof? 
> 
> What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset. 
> 
> Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation. 
> 
> Now the inpretator or program must know the rules. And i have very good rules to make it happen.

xxein:  You can reduce 6 digits of binary to 2 of decimal but it would have no universal practicality.  Think about it.  Storage and transmission format.  Sequencing.  Retrievability.  Parsing.  Analysis.  Statistical evaluation.  You name it.
Bitmap or jpeg?  Data loss.  Is that a tank or a house?

In other words, what can you do with it?  Cyphers perhaps, but it will be translated to binary along the way anyway - and binary ciphers, properly implemented, are already the most secure.

Shoot!  Now you've awakened the cipher monster in me again.

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

#588814

On 7/11/2016 12:50 PM, jonas.thornvall@gmail.com wrote:
> What kind of statistic law or mathematical conjecture  or is it even
> a physical law is violated by compression of random binary data?

compression means smaller, smaller means you threw out bits, so you dont 
have the same sequence as when you started.  In some apps that is OK, 
like video, audio.

In most others it is not.

there is a code that throws out sequential 1's or o's and does 
compression on binary data, it is lossless.

>
> I only know that Shanon theorised it could not be done, but were
> there any proof?

got a URL for Shannon doing that ? I dont think he did.


> What is to say that you can not do it if the symbolic representation
> is richer than the symbolic represenatation of the dataset.

no gain there

>
> Isn't it a fact that the set of squareroots actually depict numbers
> in a shorter way than their actual representation.

nope, they introduce more error via truncation

>
> Now the inpretator or program must know the rules. And i have very
> good rules to make it happen.

COBOL interperture ?

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

#588820

On Monday, July 11, 2016 at 10:50:49 AM UTC-7, jonas.t...@gmail.com wrote:
> What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data? 
> 
> I only know that Shanon theorised it could not be done, but were there any proof? 
> 
> What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset. 
> 
> Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation. 
> 
> Now the inpretator or program must know the rules. And i have very good rules to make it happen.


It depends on how homogeneous it is.

Double-A

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

#588822

Dne 11/07/2016 v 22:58 Double-A napsal(a):
> On Monday, July 11, 2016 at 10:50:49 AM UTC-7, jonas.t...@gmail.com wrote:
>> What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data? 
>>
>> I only know that Shanon theorised it could not be done, but were there any proof? 
>>
>> What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset. 
>>
>> Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation. 
>>
>> Now the inpretator or program must know the rules. And i have very good rules to make it happen.
> 
> 
> It depends on how homogeneous it is.
> 
If the binary is truly random, probability for each bit
is 1/2 both both 1 and 0 and one needs in avg 1 bit for encoding one bit.

As result, some of that binary gets longer, and some shorter,
when compressed.

It is proven that there is no lossless compression schema
that would provide smaller results
for all possible inputs,
as there would be possible no mapping
of N input states to N output states.

-- 
Poutnik ( The Pilgrim, Der Wanderer )
Knowledge makes great men humble, but small men arrogant.

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

#588825

On Monday, July 11, 2016 at 10:50:49 AM UTC-7, jonas.t...@gmail.com wrote:
> What kind of statistic law or mathematical conjecture  or is it even a
> physical law is violated by compression of random binary data? 

  When you say "random binary data" do you mean a binary data set that carries no information, or any information-carrying binary data set one might choose at random?

  If the latter it depends on how you compress it but you will almost certainly lose *some* data. In other words you will not be able to recover the original data set in its entirety.

  Sergio mentioned lossless compression schemes that discard sequential strings of ones and zeros (but remembers how many and where they went). Notice that if you do that to random data the result may not be as random as the original. Hence in that case it is "lossy" in that it loses some randomness.


  Mark L. Fergerson

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

#588840

On 7/11/2016 5:20 PM, nuny@bid.nes wrote:
> On Monday, July 11, 2016 at 10:50:49 AM UTC-7, jonas.t...@gmail.com
> wrote:
>> What kind of statistic law or mathematical conjecture  or is it
>> even a physical law is violated by compression of random binary
>> data?

> When you say "random binary data" do you mean a binary data set that
> carries no information, or any information-carrying binary data set
> one might choose at random?
>
> If the latter it depends on how you compress it but you will almost
> certainly lose *some* data. In other words you will not be able to
> recover the original data set in its entirety.
>
> Sergio mentioned lossless compression schemes that discard sequential
> strings of ones and zeros (but remembers how many and where they
> went).

I think a version of that was used by Ma Bell, I think they would count 
up a certian  number of 0s (or 1's) then put in a control character (in 
binary) followed by a count#, then repeat as required, it may have been 
for a system that had "dead time" charastics, and it did compress the 
data, by eliminating portion of the dead time, which is unlike true 
random characteristics.

also it seems to comply with Shannon's "The average length of an encoded 
symbol is greater than or equal to the Entropy."  'average' is the key word.



> Notice that if you do that to random data the result may not
> be as random as the original. Hence in that case it is "lossy" in
> that it loses some randomness.
>
>
> Mark L. Fergerson
>

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

#588828

Not necessarily "random", but there is a limit beyond which data can't 
be compressed losslessly.  The reasoning goes something like this:

If *any* arbitrary stream of bits can be compressed by at least one bit, 
then repeated application of that method eventually yields a bit stream 
with a length of one: a single bit, from which only one bit of 
information can be recovered.

That's not mathematically rigorous, but that and a dose of mathematical 
induction captures the reasoning behind the proof of the existence of a 
limit to lossless data compression.  You can find more by searching for 
the Shannon Coding Theorem, on the Web or in a library.

-- 
Goat

On 07/11/2016 12:50, jonas.thornvall@gmail.com wrote:
> What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data?
>
> I only know that Shanon theorised it could not be done, but were there any proof?
>
> What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset.
>
> Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation.
>
> Now the inpretator or program must know the rules. And i have very good rules to make it happen.
>

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

#588832

On Mon, 11 Jul 2016 10:50:45 -0700, jonas.thornvall wrote:

> What kind of statistic law or mathematical conjecture  or is it even a physical
> law is violated by compression of random binary data? 
> 

Kolmogorov complexity.

If a string F of length N cannot be generated by a program of length
less than N then F is Kolmogorov random.

https://en.wikipedia.org/wiki/Kolmogorov_complexity

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

#588893 — Re: One _never_ knows if data is truly random or not.

On Mon, 11 Jul 2016 17:48:23 -0700, Jeff-Relf.Me wrote:

>
> One _never_ knows if data is truly random or not;
>

That statement implies that true randomness exists but
we, as human observers, cannot describe it. 

Randomness is a human intellectual construct and hence
depends on a particular _definition_.

As a result, there may be different types of randomness
depending on different circumstances.

For most scientific purposes a sequence is random if it
passes a plethora of accepted statistical tests.

Which of the two following sequences is "more" random:

5 1 9 7 2 3 8 4 7 3 

5 4 9 7 7 6 5 3 3 8

A lot of people would claim that the first sequence
appears to be more random because it contains no successive
repeats of the same number and there are no contiguous pairs.

But the second sequence is actually more plausibly the result
of a "random" process because successive repeats and contiguous
pairs (or triples) are not outlawed in randomness.  Indeed, the
first sequence seems less plausible as being random and seems
specially designed to avoid successive repeats as well as contiguous
numbers.  In other words, the first sequence seems to be the result
of a process that takes previous values into account.

Randomness implies only independence and not a particular
patterning.

Neither sequence, however, is long enough to make any valid statistical tests.

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

#588906 — Re: One _never_ knows if data is truly random or not.

Dne 12/07/2016 v 16:33 Fabian Russell napsal(a):
> On Mon, 11 Jul 2016 17:48:23 -0700, Jeff-Relf.Me wrote:
> 
> 
> For most scientific purposes a sequence is random if it
> passes a plethora of accepted statistical tests.
> 
> Which of the two following sequences is "more" random:
> 
> 5 1 9 7 2 3 8 4 7 3 
> 
> 5 4 9 7 7 6 5 3 3 8
> 

It cannot be said, as with just few samples it cannot be determined
if subsequent numbers follow some pattern or are equally probable.

There is up to 100 combinations of neighbor numbers,
but just 10 samples.

If there is 1000-10000 samples, more could be said.

-- 
Poutnik ( The Pilgrim, Der Wanderer )
Knowledge makes great men humble, but small men arrogant.

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

#588969 — Re: One _never_ knows if data is truly random or not.

On 7/11/2016 8:48 PM, Jeff-Relf.Me wrote:
> One _never_ knows if data is truly random or not;
> if _you_ can't compress it, then it's "random" to _you_.
>
>
Nearly all irrational numbers are random, Rolf.

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

#588844

On 12/07/2016 3:50 AM, jonas.thornvall@gmail.com wrote:
> What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data?
>
> I only know that Shanon theorised it could not be done, but were there any proof?
>
> What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset.
>
> Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation.
>
> Now the inpretator or program must know the rules. And i have very good rules to make it happen.
>

If you consider n bits of data, then there are 2^n different 
combinations. If your compression of the data is to be reversible, then 
your compression has to produce 2^n different bit sequences (of varying 
lengths, typically). If your compression produces some sequences that 
are shorter than n bits, then it has to produce others that are longer 
than n bits, otherwise it's impossible to have 2^n different sequences.

If some combinations are much more frequent than others, then you can 
make an overall gain by using shorter sequences for them, at the expense 
of longer sequences for the rarer combinations.

For random data, where each possible combination is equally likely, 
you're not going to come out ahead.

Sylvia.

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

#588944

On Monday, July 11, 2016 at 10:20:58 PM UTC-7, Sylvia Else wrote:
> On 12/07/2016 3:50 AM, jonas.thornvall@gmail.com wrote:
> > What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data?
> >
> > I only know that Shanon theorised it could not be done, but were there any proof?
> >
> > What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset.
> >
> > Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation.
> >
> > Now the inpretator or program must know the rules. And i have very good rules to make it happen.
> >
> 
> If you consider n bits of data, then there are 2^n different 
> combinations. If your compression of the data is to be reversible, then 
> your compression has to produce 2^n different bit sequences (of varying 
> lengths, typically). If your compression produces some sequences that 
> are shorter than n bits, then it has to produce others that are longer 
> than n bits, otherwise it's impossible to have 2^n different sequences.
> 
> If some combinations are much more frequent than others, then you can 
> make an overall gain by using shorter sequences for them, at the expense 
> of longer sequences for the rarer combinations.
> 
> For random data, where each possible combination is equally likely, 
> you're not going to come out ahead.
> 
> Sylvia.


This is true of truly random binary data.  However if any information is being transmitted, then there is a strong likelihood that some combinations will be more frequent that others, and thus compression could be effective. 

Double-A

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

#589027

On 13/07/2016 6:29 AM, Double-A wrote:
> On Monday, July 11, 2016 at 10:20:58 PM UTC-7, Sylvia Else wrote:
>> On 12/07/2016 3:50 AM, jonas.thornvall@gmail.com wrote:
>>> What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data?
>>>
>>> I only know that Shanon theorised it could not be done, but were there any proof?
>>>
>>> What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset.
>>>
>>> Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation.
>>>
>>> Now the inpretator or program must know the rules. And i have very good rules to make it happen.
>>>
>>
>> If you consider n bits of data, then there are 2^n different
>> combinations. If your compression of the data is to be reversible, then
>> your compression has to produce 2^n different bit sequences (of varying
>> lengths, typically). If your compression produces some sequences that
>> are shorter than n bits, then it has to produce others that are longer
>> than n bits, otherwise it's impossible to have 2^n different sequences.
>>
>> If some combinations are much more frequent than others, then you can
>> make an overall gain by using shorter sequences for them, at the expense
>> of longer sequences for the rarer combinations.
>>
>> For random data, where each possible combination is equally likely,
>> you're not going to come out ahead.
>>
>> Sylvia.
>
>
> This is true of truly random binary data.  However if any information is being transmitted, then there is a strong likelihood that some combinations will be more frequent that others, and thus compression could be effective.
>
> Double-A
>

The OP expressly identified the data as being random, so that won't be 
the case.

Sylvia.

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

#589183

On Mon, 11 Jul 2016 10:50:45 -0700 (PDT), jonas.thornvall@gmail.com
wrote:
...
>Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation. 

The square root of 2 requires infinite decimal digits to depict
whereas the number 2 requires 1 decimal digit. To obtain the number
two back would require multiplying these infinite digits by
themselves.

When I was a junior in college, I thought I might have hit on a method
to encrypt any length string of bytes into 1 byte by XORing successive
data bytes together and ending up with a one byte result. I did not
rush out and apply for my Nobel because I quickly realized that while
I had compressed the stream into 1 byte, the decompression algorithm
required all the precursor bytes to function.

Alas, my perpetual motion machine worked fine except it needed an
infinite amount of fuel to start it up - lol.
>
>Now the inpretator or program must know the rules. And i have very good rules to make it happen. 

Mike
---------------------------------------------------
Michael J. Strickland			Reston, VA
---------------------------------------------------

[toc] | [prev] | [standalone]

Back to top | Article view | sci.physics

csiph-web