1
$\begingroup$

I want to compress the string 0cc175b9c0f1b6a831c399e269772661. I can do so by storing the string a, and, when decompressing, using a as input for the MD5 hash algorithm to get the original string.

I realize it's impossible to represent $2^{128}$ possible strings with inputs less than 128 bits long, even if MD5 had no collisions. However, a percentage of 128 bit strings could still be compressed using this concept.

Maybe another hash algorithm could be made with this application in mind. It does not need to be secure, irreversible, or computationally difficult. It just needs to represent the largest number of output strings given a string who's length is smaller than the output.

Multiple hashing algorithms could be used to increase the number of possible strings that could be compressed.

Is this idea practical? Could this idea be applied to compress large chunks of arbitrary data such as a file?

Improve this question
$\endgroup$
1
  • $\begingroup$ This degenerates to a dictionary for compression. Feasible for small, known sets of strings, but not a general method. You may be interested in Huffman coding. $\endgroup$
    – Raphael
    Commented Sep 27, 2017 at 5:37

1 Answer 1

Reset to default
2
$\begingroup$

This idea is not practical, because there are some serious problems:

  • You have to calculate all interesting hashes (less than hash length, here 128 bits), which is infeasible.
  • There must be a way to tell apart compressed and not compressed strings, so some kind of terminator or escape sequence must be introduced.
  • Since hash functions are designed with avalanche effect (small change in the input should yield huge difference in the output) there are no shortcuts for computations.
  • The preimage resistance prevents from fast reversing, given hash calculate the input, this also gives another problem, once the data is compressed, the decompression also requires full hash -> input mapping.
  • The hash signature is quite specific, there are almost none naturally occuring natural texts with such substrings.
  • If you want to use them in cascade it will be greedy approach, optimal one would require to calculate all cases to given depth and choose the smallest
  • Multiple hashing algorithms enhance the additional description sequence, now the simple one bit (compressed or not) is not enough, it should also encode which algorithm was used.
  • With collisions, the number of available hashes of given length decreases. The guarantee of better hash increases the complexity (both time and code).

The idea itself may be tempting, but it is not practical enough to be used in the common compression software, this tells quite a lot.

Please see also Compression with PRNG and Collision free hashes to compress and the compression of random data

Improve this answer
$\endgroup$

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.