# Tag Info

### 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
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 ...
• 141k
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 ...
• 141k

### 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 ...
• 141k
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
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
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 ...

### 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
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

### 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
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

### 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
Accepted

• 270k

### 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

### 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

### 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

### 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

### 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
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

### 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
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