93
The following are both plausible messages, but have a completely different meaning:
SOS HELP = ...---... .... . .-.. .--. => ...---.........-...--.
I AM HIS DATE = .. .- -- .... .. ... -.. .- - . => ...---.........-...--.
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 ...
43
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 ...
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
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 ...
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
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 (...
28
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)...
21
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
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 ...
15
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 ...
14
I have no way to learn (say) $m_1$ unless I know $m_2$.
That is exactly the problem - if you re-use the same key, and someone has access to one message you encrypted in both plaintext and encrypted form, they can use that to find your key:
$$
(m_2 \oplus k) \oplus m_2 = k
$$
As an alternative scenario, if you use the same key over and over, the ...
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
The central concept here is Kolmogorov complexity, and more specifically compressibility. To get a intuitive feeling of compressibility, consider two strings $A \in \mathbb{B}^*$ and $B \in \mathbb{B}^*$, where $\mathbb{B} = \{ 0,1 \}$. Let
$A = 1010$ $1010$ $1010$ $1010$, and
$B = 1011$ $0110$ $0111$ $1001$.
Note that $|A| = |B| = 16$. How could ...
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
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 ...
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
It's insecure precisely due to the reason you mention - there is some information leakage.
Basically, if you have any assumptions about plaintexts (english text, files with known structure, etc), it leads to an easy statistical analysis. Probably using it twice doesn't change the practicality of the attack significantly, but using it many times with a non-...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
