Any way to reliably compress a short string?

Question

I have a string exactly 53 characters long that contains a limited set of possible characters.

[A-Za-z0-9\.\-~_+]{53}

I need to reduce this to length 50 without loss of information and using the same set of characters.

I think it should be possible to compress most strings down to 50 length, but is it possible for all possible length 53 strings? We know that in the worst case 14 characters from the possible set will be unused. Can we use this information at all?

Thanks for reading.

Answer 1

If, as you stated, your output strings have to use the same set of characters as the input string, and if you don't know anything special about the requirements of the input string, then no, it's not possible to compress every possible 53-character string down to 50 characters. This is a simple application of the pigeonhole principle.

• Your input strings can be represented as a 53-digit number in base 67, i.e., an integer from 0 to 67⁵³ - 1 ≅ 6*10⁹⁶.
• You want to map those numbers to an integer from 0 to 67⁵⁰ - 1 ≅ 2*10⁹¹.
• So by the pigeonhole principle, you're guaranteed that 67³ = 300,763 different inputs will map to each possible output -- which means that, when you go to decompress, you have no way to know which of those 300,763 originals you're supposed to map back to.

To make this work, you have to change your requirements. You could use a larger set of characters to encode the output (you could get it down to 50 characters if each one had 87 possible values, instead of the 67 in the input). Or you could identify redundancy in the input -- perhaps the first character can only be a '3' or a '5', the nineteenth and twentieth are a state abbreviation that can only have 62 different possible values, that sort of thing.

If you can't do either of those things, you'll have to use a compression algorithm, like Huffman coding, and accept the fact that some strings will be compressible (and get shorter) and others will not (and will get longer).

Answer 2

What you ask is not possible in the most general case, which can be proven very simply.

Say it was possible to encode an arbitrary 53 character string to 50 chars in the same set. Do that, then add three random characters to the encoded string. Then you have another arbitrary, 53 character string. How do you compress that?

So what you want can not be guaranteed to work for any possible data. However, it is possible that all your real data has low enough entropy that you can devise a scheme that will work.

In that case, you will probably want to do some variant of Huffman coding, which basically allocates variable-bit-length encodings for the characters in your set, using the shortest encodings for the most commonly used characters. You can analyze all your data to come up with a set of encodings. After Huffman coding, your string will be a (hopefully shorter) bitstream, which you encode to your character set at 6 bits per character. It may be short enough for all your real data.

A library-based encoding like Smaz (referenced in another answer) may work as well. Again, it is impossible to guarantee that it will work for all possible data.

Answer 3

One byte (character) can encode 256 values (0-255) but your set of valid characters uses only 67 values, which can be represented in 7 bits (alas, 6 bits gets you only 64) and none of your characters uses the high bit of the byte.

Given that, you can throw away the high bit and store only 7 bits, running the initial bits of the next character into the "spare" space of the first character. This would require only 47 bytes of space to store. (53 x 7 = 371 bits, 371 / 8 = 46.4 == 47)

This is not really considered compression, but rather a change in encoding.

For example "ABC" is 0x41 0x42 0x43

     0x41        0x42        0x43  // hex values
0100 0001   0100 0010   0100 0011  // binary
 100 0001    100 0010    100 0011  // drop high bit
// run it all together
100000110000101000011
// split as 8 bits (and pad to 8)
10000011   00001010   00011[000]
    0x83       0x0A        0x18

As an example these 3 characters won't save any space, but your 53 characters will always come out as 47, guaranteed.

Note, however, that the output will not be in your original character set, if that is important to you.

The process becomes:

original-text --> encode --> store output-text (in database?)
retrieve --> decode --> original-text restored

Answer 4

If I remember correctly Huffman coding is going to be the most compact way to store the data. It has been too long since I used it to write the algorithm quickly, but the general idea is covered here, but if I remember correctly what you do is:

1. get the count for each character that is used
2. prioritize them based on how frequently they occurred
3. build a tree based off the prioritization
4. get the compressed bit representation of each character by traversing the tree (start at the root, left = 0 right = 1)
5. replace each character with the bits from the tree

Answer 5

Smaz is a simple compression library suitable for compressing very short strings.