-1
$\begingroup$

I'd like to know if this data compression scheme would work or not, and why:

Suppose we have a file. If we treat the bits that make up the file as the binary representation of a number n, we have n (of course, if the first bit is zero we flip every bit so that n is unique). Now we have the number n, and a boolean that informs us whether to flip all the bits of the binary representation of n or not.

My idea was approximating n from below (e.g. finding a relative big number raised to a relative big power, such as 17^6038) and then start to compute arbitrary hashes for all numbers from this approximated n to the real n, counting the number of collisions. When we finally get to n, we have the "collision state" of the hashes and then we output the compressed file, which basically contains information about how to get to the approximation of n (e.g. 17^6038) and the "collision state" for n (note that this "collision state" must also occupy very few bits, so I'm not sure this would be possible).

The decompression procedure would do a very similar process; it will approximate n (e.g. compute ~n as 17^6038) and then start to hash (i.e. apply a function and check the result) every single number (we could also check every 5 numbers or another divisor of n - ~n) until the "collision state" is the same as the specified in the compressed file. Once we match everything, we have n. Then, it would just be a matter of flipping every bit or not (as specified in the compressed file) and outputting to a file.

Could this work? The only problem I can think of is (besides the time required for processing) the number of collisions being extremely huge.

$\endgroup$
  • 1
    $\begingroup$ no.............................. $\endgroup$ – Bulat Jul 7 at 16:11
  • $\begingroup$ (I don't think starting from an approximation promising in general. Representation limited to very few bits can't possibly work.) $\endgroup$ – greybeard Jul 7 at 16:12
2
$\begingroup$

No. Any compression method that does not model its data in some way to prefer some inputs over others is doomed to fail by the pigeonhole principle. Since your algorithm does not prefer one type of data over another it by definition can not meaningfully compress.

$\endgroup$
  • $\begingroup$ The algorithm seems to "prefer" factorizable inputs. For example, given as input the binary string $10^n$ (a one followed by $n$ zeros), it should do a pretty good job of saying "That's $2^n$ and I don't need to do any of that hashing stuff". $\endgroup$ – David Richerby Jul 7 at 18:03
1
$\begingroup$

There are trivially $2^k$ possible binary strings of length $k$, and hence any encoding that is reversible necessarily uses $2^k$ different bit-strings to encode all of these strings (representing files). So clearly any reversible encoding must map at least one binary string of length $k$ to a binary string of length at least $k$, since there are only $2^k-1$ possible binary strings of length less than $k$. Thus no reversible encoding can compress all strings of length $k$. So we don't even need to look at any details of your proposed 'hash function technique' to know that it will fail.

$\endgroup$
  • $\begingroup$ There were no details yet. Thanks for saving my time. It's undeniable though that some numbers (i.e. some files) can be expressed in a very compact way (e.g. 73^704 + 5^801 + 3) $\endgroup$ – DaviFN Jul 7 at 16:58
  • 1
    $\begingroup$ @DaviFN: Yes, but you can easily calculate how few files can be represented by bit strings of length $k$. The point is that it is misleading to think that the larger files you can encode by a short string, the better the compression. We can encode an infinite string (such as the digits of π) by a finite program, but once you fix an encoding you can only encode the same number of objects with the same number of strings... $\endgroup$ – user21820 Jul 7 at 17:36
  • $\begingroup$ What if the encoding isn't fixed, but varies depending on the file? $\endgroup$ – DaviFN Jul 7 at 17:42
  • 1
    $\begingroup$ @DaviFN you then need bits to choose an encoding, and it's exactly the same as having just one encoding. Actually, it goes again and again by people who can't het the pigeon principle. The real compression algos employ special features of real data, f.e. they compress sequences of zero bytes becuae such sequnces are common in many binary files. $\endgroup$ – Bulat Jul 7 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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