95
The following are both plausible messages, but have a completely different meaning:
SOS HELP = ...---... .... . .-.. .--. => ...---.........-...--.
I AM HIS DATE = .. .- -- .... .. ... -.. .- - . => ...---.........-...--.
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 ...
37
Quoting David Richerby from the comments:
Since ⋅ represents E and − represents T, any Morse message without spaces can be interpreted as a string in $\{E,T\}^*$
Further, since A, I, M, and N are represented by the four possible combinations of two morse characters (⋅-, ⋅⋅, --, -⋅, respectively), any message without spaces can also be interpreted as a ...
35
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 (...
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 ...
29
This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long...
Morse Code isn't "officially" binary, ternary, quaternary, quinary, or even 57-ary (if I count correctly). Arguing about which one it is without context is not productive. It is up to you to define which of those five ...
28
Wow, great question! Let me try to explain the resolution. It'll take three distinct steps.
The first thing to note is that the entropy is focused more on the average number of bits needed per draw, not the maximum number of bits needed.
With your sampling procedure, the maximum number of random bits needed per draw is $N$ bits, but the average number of ...
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)...
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
Morse code is a prefix ternary code (for encoding 58 characters) on top of a prefix binary code encoding the three symbols.
This was a much shorter answer when accepted. However, considering the
considerable misunderstandings between users, and following a request
from the OP, I wrote this much longer answer. The first "nutshell"
section gives you the gist ...
18
Here is a concrete encoding that can represent each symbol in less than 1 bit on average:
First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111.
I've not said what happens if there is ...
17
It is enough to observe that certain short combinations of letters give ambiguous decodings. A single ambiguous sequence suffices, but I can see the following:
ATE ~ P
EA ~ IT
MO ~ OM
etc. As David Richerby notes in the comments, any letter is equivalent to a string of Es and Ts, which makes Morse Code ambiguous as a way of encoding arbitrary sequences of ...
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 ...
16
The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $\tfrac{8}{10}$, and $B$ and $C$ with probability $\tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't ...
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 ...
13
Let $\mathcal{D}$ be the following distribution over $\{A,B,C\}$: if $X \sim \mathcal{D}$ then $\Pr[X=A] = 4/5$ and $\Pr[X=B]=\Pr[X=C]=1/10$.
For each $n$ we can construct prefix codes $C_n\colon \{A,B,C\}^n \to \{0,1\}^*$ such that
$$
\lim_{n\to\infty} \frac{\operatorname*{\mathbb{E}}_{X_1,\ldots,X_n \sim \mathcal{D}}[C_n(X_1,\ldots,X_n)]}{n} = H(\mathcal{...
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 ...
12
What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern.
This is known as enumerative coding, and it's one of the oldest deployed compression algorithms. Probably the simplest algorithm is from Thomas Cover. It's based on the simple observation that if you have a word that is $n$ bits long,...
12
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. (Obviously, the compressor must be very large, or be drawing on a very large library.)
The compressor will inherently be less efficient at dealing with any file ...
12
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 in 'out-of-band' information - such as the list that needs to be maintained in order to decode the move-to-front transform.
11
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 particular model, you can't compress data better than the Shannon entropy of probabilities produced by this particular model.
But if you apply another model, ...
11
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 always apply a compression algorithm to data, but there's no guarantee that you'll get something smaller out at the end.
If you're interested in this, there's a ...
10
Morse Code is actually a ternary code, not a binary code, so the spaces are necessary. If spaces were not there, a lot of ambiguity would result, not so much with the entire message, but with individual letters.
For example, 2 dots is an I, but 3 dots is an S. If you are transcribing and you hear two dots, do you immediately write "I" or do you wait until ...
10
Here's the Kolmogorov complexity argument that @YuvalFilmus mentions in his answer.
Your input here is a sed script of some size plus an input file of some size. Say the total size of the sed script plus the file is $n$ bits.
There can be only $2^n$ inputs of size $n$ bits. Even if I let you have a sed script of less than $n$ bits (and don't charge you ...
10
First of all, you're right: Multimedia files are represented (more or less) as random files. The reason for that is that those files are already compressed (lossy). Note that mp3, for example, is nothing but a compression algorithm!
A consequence is that further compression will not yield any noticeable compression (and indeed, lossless compression on ...
10
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 > \cdots > c_1$ to
$$ N = \sum_{i=1}^k \binom{c_i}{i}.$$
This number has a simple interpretation. If we order these sequences lexicographically, then $N$ counts ...
Only top voted, non community-wiki answers of a minimum length are eligible
