100
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/randomness, then a more powerful computer just means you can commit more sins per second.
76
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 not silver bullets that can magically measure the true entropy of a source; all they give you is an upper bound on the amount of entropy. (Similarly, the NIST ...
48
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 Kolmogorov complexity.
It's possible to get better results if you analyze the source of the string rather than the string itself. In other words, often the source ...
45
You've got a brilliant new compression scheme, eh? Alrighty, then...
♫ Let's all play, the entropy game ♫
Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some fixed $n$. However, you want to be able to use it for longer messages, so you need some way of differentiating your first message from the second (it cannot be ...
44
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 bits followed by a 0 bit.
If not, write out a 1 bit, then write out the 7z-compression of the file.
This is extremely efficient for files of that particular ...
39
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 entropy stipulates that it only applies when, as Wikipedia puts it, "information due to independent events is additive."
In other words, independent events must ...
36
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.
Herein lies the crux. The Shannon limit is not some universal property of a string of text. It is the property of a string of text plus a model that provides (...
35
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 collection (or distribution) of strings can be compressed to, on average. In general, given a collection of $N$ strings, any compression scheme needs at least $\log_2 N$ ...
34
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 possibly compress everything by 50% because there are far less strings of length $n/2$ than there are of length $n$.
There are some major issues with the paper:
They ...
34
Have a look at how compression algorithms work. At least those in the Lempel-Ziv family (gzip uses LZ77, zip apparently mostly does as well, and xz uses LZMA) compress somewhat locally: Similarities that lie far away from each other can not be identified.
The details differ between the methods, but the bottom line is that by the time the algorithm reaches ...
34
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 with upper limit $c-1$, integer with upper limit $d-1$,... integer with upper limit $m-1$" can always be coded with perfect efficiency.
Take the first ...
30
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 anything.
In fact you actually lose space, since 80 is not a power of 2: You will need 7 bits for each 80-based number, but in these 7 bits you could instead ...
27
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 symphony, fourth movement, in AAC format that is stored on my computer's hard drive, then the output is a single bit '0'.
IF the string is anything else, then the ...
27
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 < 2^{32}$, we have $0 \le f(x,y) < 2^{63} - 2^{31}$, so this maps the set $\{x,y\}$ to a 63-bit number $f(x,y)$. To decode, you can use binary search on ...
27
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. In your case, this will give
0
1
1
1
1
...
This can then with simple run-length encoding be stored in $\mathcal{O}(n)$ space, as there are only $\mathcal{O}(1)...
24
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 memory from one file to another file. In other words, each file is separately compressed, then the compressed files are concatenated into an archive.
Short-term ...
23
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 [1] and works by extending non-isomorphs of size n-1 in all possible ways and checking to see if the new vertex was canonical. It's implemented as geng in McKay'...
23
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}$ possible arrangements of the cards ignoring suits, so that means the state of the entire deck can be stored in 166 bits.
How do you do this compression and ...
22
There are $2^N-1$ binary strings of length less than $N$, and $2^N$ binary strings of length exactly $N$. This means that whatever your compression algorithm is, there must be some string which it can't compress at all, just because the mapping from original string to compressed string must be injective (one-to-one). This is the driving force behind many ...
20
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. From this perspective, we see that your algorithm smuggles in entropy via System.nanoTime() - most definitions of a "deterministic" algorithm would disallow ...
18
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 right.
What you did is using a rather slow method System.nanoTime() to generate rather weak randomness. You measured some
... entropy rate of ~5.3 bits/...
17
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 $\pi$ which agrees with your file. Since the file is $128$ bits long, one would expect this place to be around the $2^{128}$th bit. So it would be rather hard to ...
17
Anything using a BWT (Burrows–Wheeler transform) ought to be able to compress that fairly well.
My quick Python test:
>>> import gzip
>>> import lzma
>>> import zlib
>>> import bz2
>>> import time
>>> dLen = 16
>>> inputData = '\n'.join('{:0{}b}'.format(x, dLen) for x in range(2**dLen))
>>...
16
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 table, it seems like a broadly believable claim.
What they claim is a consistent 50% compression ratio on text files (not "all files"), which they note is around ...
15
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 looks something like this:
[2-9][0-8]\d - [2-9]\d\d - \d\d\d\d
This gives 8*9*10 * 8*10*10 * 10*10*10*10 values. In addition, the fifth and sixth characters can'...
14
Suppose a simple compression algorithm that represents a run of a by storing $(\text{header}, \mathtt{\text{"a"}}, n)$, i.e. some fixed header, the string a, and the number of repetitions $n$. This is a run-length encoding. Then the length of the compressed text would be close to $a + \lg n$ bits for some constants $a$. The corresponding compression ratio ...
answered Sep 9 '13 at 18:42
Gilles 'SO- stop being evil'
41k7 gold badges108 silver badges172 bronze badges
14
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:
Determine where the binary expansion of $\pi$ matches the contents.
Store the offset and number of sequenced bits ($128$).
The offset for the file contents should ...
14
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 are all inverse powers of two, this has a Huffman code which is optimal (i.e. it's identical to arithmetic coding). We will use the canonical code 0, 10, 11 for ...
14
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 meaning of "random", but it's not the only one.
One problem with the output of random processes is that they're hard to distinguish from the outputs of deterministic ...
12
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 enormous?
Yes, of course. Even for their hand-picked example ("THE QUICK SILVER FOX JUMPS OVER THE LAZY DOG"), they don't achieve compression, because the ...
Only top voted, non community-wiki answers of a minimum length are eligible