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/...
- 80.2k
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 ...
D.W.♦
- 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 ...
D.W.♦
- 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 ...
D.W.♦
- 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 ...
- 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.
...
- 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 ...
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 ...
- 270k
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 ...
- 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 ...
- 1,044
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 ...
- 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 ...
- 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 ...
D.W.♦
- 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. ...
- 1,651
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 [...
- 949
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.♦
- 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}$ ...
D.W.♦
- 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....
- 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 ...
- 473
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 $\...
- 270k
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 ...
- 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:
...
- 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 ...
- 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 ...
- 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:
...
- 241
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 ...
- 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 ...
- 279
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 ...
- 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....
- 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 ...
- 80.2k
Only top scored, non community-wiki answers of a minimum length are eligible