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/...
user avatar
76 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 ...
user avatar
  • 141k
48 votes
Accepted

Is there a known maximum for how much a string of 0's and 1's can be compressed?

Kolmogorov complexity is one approach for formalizing this mathematically. Unfortunately, computing the Kolmogorov complexity of a string is an uncomputable problem. See also: Approximating the ...
user avatar
  • 141k
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 ...
user avatar
  • 141k
39 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 ...
user avatar
  • 596
36 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. ...
user avatar
  • 12.3k
35 votes
Accepted

Data compression using prime numbers

always compress random data sets by more than 50% That's impossible. You can't compress random data, you need some structure to take advantage of. Compression must be reversible, so you can't ...
user avatar
35 votes

Is there a known maximum for how much a string of 0's and 1's can be compressed?

For any given string there is a compression scheme that compresses it to the empty string. Hence it is not meaningful to ask how much a single string can be compressed, but rather how much a ...
user avatar
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 ...
user avatar
  • 70.9k
34 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 ...
user avatar
30 votes
Accepted

Using base 80 for compressing files

While you will need fewer 80-based numbers than 2-based numbers (bits) to encode the same file, the only way to store these 80-based numbers on a computer is to encode them as bits. So you do not gain ...
user avatar
  • 6,519
27 votes

Is there a known maximum for how much a string of 0's and 1's can be compressed?

Here's a simple scheme that can compress arbitrary bit strings lossless, with the smallest result being just one bit: IF the string is an identical match for the recording of Beethoven's 9th ...
user avatar
  • 25.2k
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 ...
user avatar
  • 141k
27 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. ...
user avatar
24 votes
Accepted

Enumerate all non-isomorphic graphs of a certain size

Probably the easiest way to enumerate all non-isomorphic graphs for small vertex counts is to download them from Brendan McKay's collection. The enumeration algorithm is described in paper of McKay's [...
user avatar
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 ...
user avatar
  • 141k
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}$ ...
user avatar
  • 141k
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....
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 ...
user avatar
17 votes
Accepted

Are there any compression algorithms based on PI?

Your suggestion doesn't make much sense, for many reasons. First of all, when trying to compress a large file, say a file of size $16$ bytes, you will have to find a place in the binary expansion of $\...
user avatar
17 votes

Data compression using prime numbers

I'm going to defer to Tom van der Zanden who seems to have read the paper and discovered a weakness in the method. While I didn't read the paper in detail, going from the abstract and the results ...
user avatar
  • 18.9k
17 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: ...
user avatar
  • 1,282
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 ...
user avatar
  • 592
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 ...
user avatar
  • 6,940
14 votes

Are there any compression algorithms based on PI?

Based on Yuval's answer, with a slightly different explanation and an example to help illuminate the problem. Theory Take a file $16$ bytes long ($128$ bits). The compression algorithm follows: ...
user avatar
14 votes
Accepted

Is there a generalization of Huffman Coding to Arithmetic coding?

Let's look at a slightly different way of thinking about Huffman coding. Suppose you have an alphabet of three symbols, A, B, and C, with probabilities 0.5, 0.25, and 0.25. Because the probabilities ...
user avatar
  • 18.9k
13 votes

Data compression using prime numbers

You ask: Is this really feasible as the authors suggest it? According to the paper, their results are very efficient and always compress data to a smaller size. Won't the dictionary size be ...
user avatar
12 votes
Accepted

Compression type that can be searched

Compressed self-indexes such as the FM Index allow arbitrary substring searches in near entropy-compressed space. These are essentially compressed suffix arrays or suffix trees, which have a lot of ...
user avatar
  • 1,254
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....
user avatar
  • 842
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 ...
user avatar

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