# Can data be compressed through this hash function technique?

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.

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

• 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". – David Richerby Jul 7 '19 at 18:03
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.
• @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... – user21820 Jul 7 '19 at 17:36