compressionhuffman-codeentropyinformation-theory

Optimal way to compress 60 bit string

Given 15 random hexadecimal numbers (60 bits) where there is always at least 1 duplicate in every 20 bit run (5 hexdecimals).

What is the optimal way to compress the bytes?

Here are some examples:

01230 45647 789AA
D8D9F 8AAAF 21052
20D22 8CC56 AA53A
AECAB 3BB95 E1E6D
9993F C9F29 B3130

Initially I've been trying to use Huffman encoding on just 20 bits because huffman coding can go from 20 bits down to ~10 bits but storing the table takes more than 9 bits.

Here is the breakdown showing 20 bits -> 10 bits for 01230

Character   Frequency   Assignment  Space Savings
0           2           0           2×4 - 2×1 = 6 bits
2           1           10          1×4 - 1×2 = 2 bits
1           1           110         1×4 - 1×3 = 1 bits
3           1           111         1×4 - 1×3 = 1 bits

I then tried to do huffman encoding on all 300 bits (five 60bit runs) and here is the mapping given the above example:

Character   Frequency   Assignment  Space Savings
---------------------------------------------------------
a           10          101         10×4 - 10×3 = 10 bits
9           8           000         8×4 - 8×3 = 8 bits
2           7           1111        7×4 - 7×4 = 0 bits
3           6           1101        6×4 - 6×4 = 0 bits
0           5           1100        5×4 - 5×4 = 0 bits
5           5           1001        5×4 - 5×4 = 0 bits
1           4           0010        4×4 - 4×4 = 0 bits
8           4           0111        4×4 - 4×4 = 0 bits
d           4           0101        4×4 - 4×4 = 0 bits
f           4           0110        4×4 - 4×4 = 0 bits
c           4           1000        4×4 - 4×4 = 0 bits
b           4           0011        4×4 - 4×4 = 0 bits
6           3           11100       3×4 - 3×5 = -3 bits
e           3           11101       3×4 - 3×5 = -3 bits
4           2           01000       2×4 - 2×5 = -2 bits
7           2           01001       2×4 - 2×5 = -2 bits

This yields a savings of 8 bits overall, but 8 bits isn't enough to store the huffman table. It seems because of the randomness of the data that the more bits you try to encode with huffman the less effective it works. Huffman encoding seemed to work best with 20 bits (50% reduction) but storing the table in 9 or less bits isnt possible AFAIK.

In the worst-case for a 60 bit string there are still at least 3 duplicates, the average case there are more than 3 duplicates (my assumption). As a result of at least 3 duplicates the most symbols you can have in a run of 60 bits is just 12.

Because of the duplicates plus the less than 16 symbols, I can't help but feel like there is some type of compression that can be used

Solution

  • If I split your question in two parts:

    1. How do I compress (perfect) random data: You can't. Every bit is some new entropy which can't be "guessed" by a compression algorithm.
    2. How to compress "one duplicate in five characters": There are exactly 10 options where the duplicate can be (see table below). This is basically the entropy. Just store which option it is (maybe grouped for the whole line).

    These are the options:

    AAbcd = 1    AbAcd = 2    AbcAd = 3    AbcdA = 4    (<-- cases where first character is duplicated somewhere)
             aBBcd = 5    aBcBd = 6    aBcdB = 7    (<-- cases where second character is duplicated somewhere)
                          abCCd = 8    abCdC = 9    (<-- cases where third character is duplicated somewhere)
                                       abcDD = 0    (<-- cases where last characters are duplicated)

    So for your first example:

    01230 45647 789AA

    The first one (01230) is option 4, the second 3 and the third option 0.

    You can compress this by multiplying each consecutive by 10: (4*10 + 3)*10 + 0 = 430 And uncompress it by using divide and modulo: 430%10=0, (430/10)%10=3, (430/10/10)%10=4. So you could store your number like that:

    1AE 0123 4567 789A
^^^ this is 430 in hex and requires only 10 bit

    The maximum number for the three options combined is 1000, so 10 bit are enough.

    Compared to storing these 3 characters normally you save 2 bit. As someone else already commented - this is probably not worth it. For the whole line it's even less: 2 bit / 60 bit = 3.3% saved.