23
$\begingroup$

I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data.

Basically it uses prime numbers to uniquely construct a representation of 4-byte data chunks which are easy to decompress given that every number is a unique product of primes. In order to associate these sequences with the primes it utilizes a dictionary.

My question is:

  • 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?
  • Couldn't this be used to iteratively re-compress the compressed data using the same algorithm? It is obvious, and has been demonstrated, that such techniques (where the compressed data is re-compressed as many times as possible, dramatically reducing the file size) are impossible; indeed, there would be no bijection between the set of all random data and the compressed data. So why does this feel like it would be possible?
  • Even if the technique is not perfect as of yet, it can obviously be optimized and strongly improved. Why is this not more widely known/studied? If indeed these claims and experimental results are true, couldn't this revolutionalize computing?
Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ As you observed, the paper is making really strong claims. Always be very suspicious of such claims, especially if the paper is published in an odd venue (amazing papers "revolutionizing computing" should appear in respected well-known venues, right?). $\endgroup$
    – Juho
    Commented Jul 21, 2015 at 10:20
  • 2
    $\begingroup$ it is impossible to "always compress random data" based eg on kolmogorov complexity theory. and a disproof is similar to how you have sketched out. not sure if this is a misinterpretation of the paper or in the original paper. why dont you highlight where that particular claim comes in? $\endgroup$
    – vzn
    Commented Jul 21, 2015 at 15:00
  • 6
    $\begingroup$ "Couldn't this be used to iteratively re-compress the compressed data using the same algorithm?" – Yes. Any algorithm that claims to be able to compress all arbitrary data can be recursively applied to its own output such that any data is compressed to 0 bits. Thus, this claim is impossible. $\endgroup$
    – Jörg W Mittag
    Commented Jul 21, 2015 at 22:46
  • 1
    $\begingroup$ @JörgWMittag I have an algorithm that lets you compress a file repeatedly to a small number of bits, but it's extremely impractical. Also only works with files starting with 1 bit: Treat the entire file as a large binary number, decrement it, then discard leading 0's. To decompress, increment it, adding a leading 1 if necessary. $\endgroup$
    – user20574
    Commented Jul 22, 2015 at 2:19
  • 3
    $\begingroup$ Note to self: Don't bother submitting any papers to any Elsevier journals - ever. $\endgroup$
    – 500 - Internal Server Error
    Commented Jul 27, 2015 at 20:40

5 Answers 5

Reset to default
35
$\begingroup$

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 use 10 test files without any indication of their content. Is the data really random? How were they generated?

  • They claim to achieve compression ratios of at least 50%, while their test data shows they achieve at most 50%.

This algorithm defines a lossless strategy which makes use of the prime numbers present in the decimal number system

  • What? Prime numbers are prime numbers regardless of the base.

  • Issue #1 with decompression: prime factorization is a hard problem, how do they do it efficiently?

  • Issue #2 with decompression (this is the kicker): they multiply the prime numbers together, but doing so you lose any information about the order, since $2\cdot 5 = 10 = 5\cdot 2$. I don't think it is possible to decompress at all using their technique.

I don't think this paper is very good.

Improve this answer
$\endgroup$
11
  • $\begingroup$ From what I understood, they store the order of the strings with same multiplicity in the dictionary. But in random data sets, shouldn't this generate an enormous dictionary, given that there are many 4-byte strings with multiplicity 1 (or equal multiplicity)? $\endgroup$
    – Klangen
    Commented Jul 21, 2015 at 8:56
  • $\begingroup$ @Pickle In their example, the string "@THE" has multiplicity 2. I don't see how they can reconstruct in which two places the word "the" should go. $\endgroup$
    – Tom van der Zanden
    Commented Jul 21, 2015 at 8:59
  • 1
    $\begingroup$ Ah, I see. Good observation. Indeed, that is a major problem. How was this paper accepted to appear in the journal? Shouldn't there be more rigourous peer reviewing? $\endgroup$
    – Klangen
    Commented Jul 21, 2015 at 9:03
  • 4
    $\begingroup$ @Pickle Yes, there should be more rigorous reviewing. That is not always the case though, sometimes inexperienced/lazy/incompetent conference organizers do not manage to find peer reviewers in time. There are multiple occurrences of papers containing randomly generated gibberish being accepted, and one journal even published a paper titled "Get me off your fucking mailing list". $\endgroup$
    – Tom van der Zanden
    Commented Jul 21, 2015 at 9:16
  • $\begingroup$ Hahaha that's amazing. But sad at the same time. $\endgroup$
    – Klangen
    Commented Jul 21, 2015 at 10:53
16
$\begingroup$

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 the same as LZW and about 10% worse than (presumably zero-order) Huffman coding. Compressing text files by 50% is not hard to achieve using reasonably simple methods; it's an undergraduate assignment in many computer science courses.

I do agree that the paper isn't very good as published research, and I don't think it speaks well of the reviewers that this was accepted. Apart from the obvious missing details that makes the results impossible to reproduce (e.g. what the text files were), and no attempt to tie it into the field of compression, there is no sense that they really understand what their algorithm is doing.

The conference web site claims a 1:4 acceptance ratio, which makes you wonder what they rejected.

Improve this answer
$\endgroup$
12
$\begingroup$

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 dictionary contains every 4-byte substring of the text (minus 4 bytes for the one repetition of "THE")... and the "compressed" version of the text has to include the whole dictionary plus all this prime number crap.

  • Couldn't this be used to iteratively re-compress the compressed data using the same algorithm? It is obvious, and has been demonstrated, that such techniques (where the compressed data is re-compressed as many times as possible, dramatically reducing the file size) are impossible; indeed, there would be no bijection between the set of all random data and the compressed data. So why does this feel like it would be possible?

Again you seem to have a good intuitive grasp of the situation. You have intuitively realized that no compression scheme can ever be effective on all inputs, because if it were, we could just apply it over and over to compress any input down to a single bit — and then to nothingness!

To put it another way: Once you've compressed all your .wav files to .mp3, you're not going to get any improvement in file size by zipping them. If your MP3 compressor has done its job, there won't be any patterns left for the ZIP compressor to exploit.

(The same applies to encryption: if I take a file of zeroes and encrypt it according to my cryptographic algorithm of choice, the resulting file had better not be compressible, or else my encryption algorithm is leaking "pattern" into its output!)

  • Even if the technique is not perfect as of yet, it can obviously be optimized and strongly improved. Why is this not more widely known/studied? If indeed these claims and experimental results are true, couldn't this revolutionalize computing?

These claims and experimental results are not true.

As Tom van der Zanden already noted, the "compression algorithm" of Chakraborty, Kar, and Guchait is flawed in that not only does it not achieve any compression ratio, it is also irreversible (in mathspeak, "not bijective"): there are a multitude of texts that all "compress" to the same image, because their algorithm is basically multiplication and multiplication is commutative.

You should feel good that your intuitive understanding of these concepts led you to the right conclusion instantly. And, if you can spare the time, you should feel pity for the authors of the paper who clearly spent a lot of time thinking about the topic without understanding it at all.

The file directory one level above the URL you posted contains 139 "papers" of this same quality, all apparently accepted into the "Proceedings of the International Conference on Emerging Research in Computing, Information, Communication and Applications." This appears to be a sham conference of the usual type. The purpose of such conferences is to allow fraudulent academics to claim "publication in a journal", while also allowing unscrupulous organizers to make a ton of money. (For more on fake conferences, check out this reddit thread or various StackExchange posts on the subject.) Sham conferences exist in every field. Just learn to trust your instincts and not believe everything you read in a "conference proceeding", and you'll do fine.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for stating clearly why this paper is plain crap, and tell how it's even possible that it was written in the first place and that it managed to go through any type of reviewing. $\endgroup$
    – vaab
    Commented Jul 22, 2015 at 8:21
  • $\begingroup$ Thanks for your concise answer. It really is sad when you can't even trust journal entries to be at least reviewed by a peer of some sort. This really sheds a lot of light on the fact that one must be vigilant even when reading "supposed" scientific journal publications. One would think such articles are subject not only to peer "review", but also to a minimal peer "analysis", as would be customary in such fields. I hope this becomes an eye-opener for a number of people. $\endgroup$
    – Klangen
    Commented Jul 22, 2015 at 13:07
  • $\begingroup$ I learned today that there exist at least two U.S. patents on similar "infinite compression algorithms." See gailly.net/05533051.html $\endgroup$
    – Quuxplusone
    Commented Jan 5, 2018 at 21:56
6
$\begingroup$

Entropy effectively bounds the performance of the strongest lossless compression possible. Thus there exist no algorithm that can compress random data sets by always more than 50%.

Improve this answer
$\endgroup$
2
  • 9
    $\begingroup$ There doesn't even exist an algorithm that can compress random datasets by always more than 0.0000001%. $\endgroup$
    – David Richerby
    Commented Jul 21, 2015 at 12:07
  • $\begingroup$ A former colleague wrote such an algorithm. Then came to the obvious conclusion that this couldn’t be right. Then he wrote the decompression algorithm and found he couldn’t reconstruct the original data. (It was just a bug where substantial parts of the compressed string were not written to the output string). $\endgroup$
    – gnasher729
    Commented Dec 19, 2021 at 12:35
1
$\begingroup$

Compression methods, that are restorable, in general find a pattern and re-express it in a simplistic way. Some are very clever, some very simple. At some point there is no pattern. The process(es) have 'boiled' the data set down to it simplest unique pattern. Any attempts at compression from that point forward result in a larger data set, or dilute the uniqueness. In magic number compression schemes there is always a flaw, or a slight of hand, or loss. be wary of any process that claims to out do the latest WinZip or RAR.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ This is factually incorrect. Any string can be compressed by some algorithm: the algorithm for string $s$ maps $s$ to the empty string, the empty string to $s$ and keeps every other string the same. Thus, it is not true that "any attempt at compression from that point forwards results in a larger data set". And what does "dilute the uniqueness" mean? $\endgroup$
    – David Richerby
    Commented Jul 21, 2015 at 21:32
  • 1
    $\begingroup$ @DavidRicherby, then your compression of the empty string produces a larger data set, as claimed by SkipBerne. Still, I think his answer should clarify that he is refering about recompressing the previous output using the same algorithm. $\endgroup$
    – Ángel
    Commented Jul 21, 2015 at 23:03
  • 2
    $\begingroup$ @Ángel SkipBerne's claim is that there exist strings that cannot be compressed by any algorithm ("any attempt at compression from that point forward", my emphasis). That is incorrect for the reason I give: for every string, there exists an algorithm that compresses that string. $\endgroup$
    – David Richerby
    Commented Jul 22, 2015 at 5:53
  • $\begingroup$ The way I interpret it SkipBerne is claiming that for every compression algorithm there is a string which can't be compresed. Which is true. That uncompressible string will be different for different algorithms, of course. $\endgroup$
    – Anonymous Coward
    Commented Jul 22, 2015 at 12:20
  • $\begingroup$ @DavidRicherby You're misplacing the quantifiers — it's reasonably clear that SkipBerne wrote that (for any compression method, there is a point after which there is no compression), not that (there is a point after which for any compression method, there is no compression). This answer is factually correct, but doesn't add anything to the older, better-written answers. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jul 22, 2015 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.