Skip to main content
101 votes

Is von Neumann's randomness in sin quote no longer applicable?

If you're using some hardware source of entropy/randomness, you're not "attempting to generate randomness by deterministic means" (my emphasis). If you're not using any hardware source of entropy/...
David Richerby's user avatar
78 votes
Accepted

Is von Neumann's randomness in sin quote no longer applicable?

Just because you can't see a pattern doesn't mean that no pattern exists. Just because a compression algorithm can't find a pattern doesn't mean that no pattern exists. Compression algorithms are ...
D.W.'s user avatar
  • 162k
44 votes

Efficient compression of simple binary data

Sure, of course there are algorithms. Here is my algorithm: First, check if the file contains ordered binary numbers from $0$ to $2^n-1$, for some $n$. If so, write out a 0 bit followed by $n$ one ...
D.W.'s user avatar
  • 162k
41 votes
Accepted

Do lossless compression algorithms reduce entropy?

A lot of casual descriptions of entropy are confusing in this way because entropy is not quite as neat and tidy a measure as sometimes presented. In particular, the standard definition of Shannon ...
senderle's user avatar
  • 616
38 votes
Accepted

Can data be compressed to size smaller than Shannon data compression limit?

Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by log2 of the reciprocal of the probability. ...
orlp's user avatar
  • 13.6k
34 votes
Accepted

Why are these (lossless) compression methods of many similar png images ineffective?

Have a look at how compression algorithms work. At least those in the Lempel-Ziv family (gzip uses LZ77, zip apparently mostly ...
Raphael's user avatar
  • 72.6k
33 votes

Can random suitless $52$ playing card data be compressed to approach, match, or even beat entropy encoding storage? If so, how?

Here is a complete algorithm which reaches the theoretical limit. Prologue: Encoding integer sequences A 13-integer sequence "integer with upper limit $a-1$, integer with upper limit $b-1$, "integer ...
Martin Kochanski's user avatar
28 votes
Accepted

Efficient compression of simple binary data

This seems to be a clear use case for delta compression. If $n$ is known a priori this is trivial: store the first number verbatim, and for each next number store only the difference to the previous. ...
leftaroundabout's user avatar
27 votes
Accepted

Compressing two integers disregarding order

Yes, one can. If $x<y$, map the set $\{x,y\}$ to the number $$f(x,y) = y(y-1)/2 + x.$$ It is easy to show that $f$ is bijective, and so this can be uniquely decoded. Also, when $0 \le x < y ...
D.W.'s user avatar
  • 162k
24 votes

Why are these (lossless) compression methods of many similar png images ineffective?

Why this happens. There are actually two different effects happening here: Each file compressed independently. Some archive programs -- including zip -- compress each file independently, with no ...
D.W.'s user avatar
  • 162k
23 votes

Can random suitless $52$ playing card data be compressed to approach, match, or even beat entropy encoding storage? If so, how?

Rather than trying to encode each card separately into 3 or 4 bits, I suggest you encode the state of the entire deck into 166 bits. As Martin Kochanski explains, there are fewer than $2^{166}$ ...
D.W.'s user avatar
  • 162k
21 votes

Is von Neumann's randomness in sin quote no longer applicable?

I've always understood the quote to mean that a deterministic algorithm has a fixed amount of entropy, and although the output can appear "random" it can't contain more entropy than the inputs provide....
bmm6o's user avatar
  • 311
18 votes

Is von Neumann's randomness in sin quote no longer applicable?

Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. When you interpret "living in a state of sin" as "doing a nonsense", than it's perfectly ...
maaartinus's user avatar
16 votes

Efficient compression of simple binary data

Anything using a BWT (Burrows–Wheeler transform) ought to be able to compress that fairly well. My quick Python test: ...
TLW's user avatar
  • 1,442
15 votes

Is von Neumann's randomness in sin quote no longer applicable?

I thought I'd chime in on the meaning of "random". Most answers here are talking about the output of random processes, compared to the output of deterministic processes. That's a perfectly good ...
Warbo's user avatar
  • 632
15 votes

Algorithm to convert a fixed-length string to the smallest possible collision-free representation?

As ratchet freak says, you have ten decimal digits, which should give $10^{10}$ possible values. But in practice, there are a few more restrictions. The format of a North American telephone number ...
Draconis's user avatar
  • 7,148
13 votes

Can data be compressed to size smaller than Shannon data compression limit?

It's trivially simple to show that you can compress below the Shannon limit--take a cheating compressor that has a bunch of common files assigned to tokens. Said files are stored as those tokens. (...
Loren Pechtel's user avatar
12 votes

Why are these (lossless) compression methods of many similar png images ineffective?

Firstly, note that the PNG image format is basically raw RGB pixels (with some light filtering) pushed through the DEFLATE compression format. Generally speaking, compressed files (PNG, JPEG, MP3, etc....
Nayuki's user avatar
  • 881
12 votes

How can I explain lossless compression to a misguided audio engineer?

Tell him to write out the integers between 1 and 100, inclusive. Ask him how it can be that your instruction was so much shorter than the list of numbers he wrote out. Did that brevity cause him to ...
David Richerby's user avatar
12 votes
Accepted

Optional prefix code for the naturals

I wrote a paper on this. The short answer is that there is no optimal encoding, nor even an optimal sequence of better and better encodings. Kraft's inequality states that there is a prefix code with ...
Yuval Filmus's user avatar
12 votes

Do lossless compression algorithms reduce entropy?

No, if the algorithm is lossless no steps in the compression sequence can reduce its entropy - otherwise it would not be able to be decompressed/decoded. However, the additional entropy may be stored ...
Luke Schwartzkopff's user avatar
11 votes

Can data be compressed to size smaller than Shannon data compression limit?

You first apply the model to the data, computing the sequence of probabilities, f.e. $1/2$, $1/3$, $1/6$. Then, to encode each symbol with probability $p$, you need $log_2(1/p)$ bits. And given some ...
Bulat's user avatar
  • 1,898
11 votes

I think you can always compress compressed data, is it true?

Here's the problem with that reasoning: If you could always compress data, you could compress the compressed data, then compress that, etc. until you have something that is 0 bytes long. You can ...
Joey Eremondi's user avatar
11 votes

Algorithm to convert a fixed-length string to the smallest possible collision-free representation?

You have 10 base10 digits. This is $10^{10}$ possible values. Encoding this in an alphabet with 64 tokens you need $\lceil \log_{64}(10^{10}) \rceil = 6$ characters. If you encode it in straight ...
ratchet freak's user avatar
10 votes

Compressing two integers disregarding order

As an addition to D.W.'s answer, note that this is a particular case of the Combinatorial Number System, which compactly maps a strictly decreasing sequence of $k$ non-negative integers $c_k > \...
filipos's user avatar
  • 261
9 votes

Efficient compression of simple binary data

PNG encoding does exactly what you want. It works on real life data also, not just extremely organized data. In PNG, each row is encoded with a filter, of which 4 are specified. One of these is "...
Cort Ammon's user avatar
  • 3,351
8 votes
Accepted

Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?

I would suggest a more detailed explanation of mp3 codec. FFT is applied on the time domain signal, so in fact it does not use the result from the MDCT. The input to the psychoacoustic models is in ...
Evil's user avatar
  • 9,465
8 votes

Can random suitless $52$ playing card data be compressed to approach, match, or even beat entropy encoding storage? If so, how?

The number of possible arrangements of the cards ignoring suits is $$\frac{52!}{(4!)^{13}}\text,$$ whose logarithm base 2 is 165.976, or 3.1919 bits per card, which is better than the limit you gave. ...
Martin Kochanski's user avatar
8 votes

Storing N bits on the smallest possible space in a real computer

Represent the string $x$ using the following encoding: $$0, x_k, \dots, 0, x_2, 0, x_1, 1, x_0$$ where $x_0 = x$, $x_{i+1} = \text{len}(x_i)$ is a binary representation of the length of $x_i$ in bits (...
D.W.'s user avatar
  • 162k
7 votes

Why are these (lossless) compression methods of many similar png images ineffective?

The problem is, that (most) compression schemes lack the knowledge over the data you have. Even if you decompress your PNGs to bitmaps and compress them in the tarball, you would not get (...
Jonas's user avatar
  • 71

Only top scored, non community-wiki answers of a minimum length are eligible