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.