Solved

# Lossless compression from n to (n-1) bytes

Posted on 1998-06-26

I need a lossless compression algorithm/program to make a n-bytes sequence to be a (n-1) bytes sequence. For example:

5-bytes sequence represented by: ABCDE,

compressed to 4-bytes sequence, represented by: KLMN.

KLMN must be able to be uncompressed back to ABCDE.

Or to compress a n-bits sequence to be a (n-1) bits sequence, for example 01010101 compressed to 1101101.

It doesn't need to be exactly (n-1) bits/bytes, it can be (n-2), (n-3) or less, the less the better.

For n, it can be any number (e.g. 100 bytes compressed to 99 bytes).

And the bytes/bits sequence must be able to be compressed with this method in any byte sequence combination, this is the one I know is the limitation of most-used compression technique such as RLE, LZW and Huffman.

I've tried to use a XOR and several boolean logic method to do it:

For example, I have 4 bytes: A,B,C,D, and I compressed it to 3 bytes:

A xor B = AB

A xor C = AC

A xor D = AD

To uncompress it:

AB xor AC xor AD = ABCD

ABCD xor AB = CD

But then I keep end up with a cyclic XOR operation, which cannot result the uncompressed byte. I've also tried the other combinations, but didn't give any result.

I know here's not a general algorithm topic area (which I can't find one), but since Pascal is widely used to learn an algorithm, I think I can get good answers here. For a start, I offered 30 points, but for a solution (prefereably a good one), I will change it to 300 or more points.