f



Re: A Random Data Compression method -draft #7

There with the eggs down my throat and stummie it's now time for the move to 
front to perform it's miracles ;) :)

Let's see... where's my input:

Random input:

 1  2  3  4  5  6  7  8  9  10 11 12
11 10 10 01 01 10 11 01 01 01 01 01

Ok... man...

Now for the table which will always stay the same as according to the 
original mtf algo:

[0, 10, 110, 111]

OK, now for the initial table for the values:

[00, 01, 10, 11]

And now the encoding begins:

1: 11 -> 111   table-> [11, 00, 01, 10]
2: 10 -> 111   table-> [10, 11, 00, 01]
3: 10 -> 0     table-> [10, 11, 00, 01]
4: 01 -> 111   table-> [01, 10, 11, 00]
5: 01 -> 0     table-> [01, 10, 11, 00]
6: 10 -> 10    table-> [10, 01, 11, 00]
7: 11 -> 110   table-> [11, 10, 01, 00]
8: 01 -> 110   table-> [01, 11, 10, 00]
9: 01 -> 0     table-> [01, 11, 10, 00]
10: 01 -> 0     table-> [01, 11, 10, 00]
11: 01 -> 0     table-> [01, 11, 10, 00]
12: 01 -> 0     table-> [01, 11, 10, 00]

Final result: 6x1 + 1x2 + 5x3 bits = 23 bits.

Input was 24 bits, 1 bit saved therefore... not bad.
Much better than huffman code at least for this short code.

Perhaps recursive encoding might provide further compression, let's try:
Endings will be padded with zero's.

Output from last round:

 1  2  3  4  5  6  7  8  9 10 11 12
11 11 11 01 11 01 01 10 11 00 00 00

table[00,01,10,11]

1: 11->111  table->[11,00,01,10]
2: 11->0    table->[11,00,01,10]
3: 11->0    table->[11,00,01,10]
4: 01->110  table->[01,11,00,10]
5: 11->10   table->[11,01,00,10]
6: 01->10   table->[01,11,00,10]
7: 01->0    table->[01,11,00,10]
8: 10->111  table->[10,01,11,00]
9: 11->110  table->[11,10,01,00]
10: 00->111  table->[00,11,10,01]
11: 00->0    table->[00,11,10,01]
12: 00->0    table->[00,11,10,01]

Result of round2: 5x1 + 2x2 + 5x3 = 24 bits.

Back to square one again ! ;) :)

Unless we leave last code at 1 bit hehe.

Now purely for my own interest I will give the bubble to front a try to see 
how it performs:

Random input:

 1  2  3  4  5  6  7  8  9  10 11 12
11 10 10 01 01 10 11 01 01 01 01 01

table[00, 01, 10, 11]

1: 11->111   table->[00,01,11,10]
2: 10->111   table->[00,01,10,11]
3: 10->110   table->[00,10,01,11]
4: 01->110   table->[00,01,10,11]
5: 01->10    table->[01,00,10,11]
6: 10->110   table->[01,10,00,11]
7: 11->111   table->[01,10,11,00]
8: 01->0     table->[01,10,11,00]
9: 01->0     table->[01,10,11,00]
10: 01->0     table->[01,10,11,00]
11: 01->0     table->[01,10,11,00]
12: 01->0     table->[01,10,11,00]

BubbleToFront Result: 5x1 + 1x2 + 6x3 = 25 bits

Slightly worse... then input.

Let's do bubble to front one more time just to see what happens:

 1  2  3  4  5  6  7  8  9 10 11 12 13
11 11 11 11 01 10 10 11 01 11 00 00 00

table[00,01,10,11]

1: 11->111   table->[00,01,11,10]
2: 11->110   table->[00,11,01,10]
3: 11->10    table->[11,00,01,10]
4: 11->0     table->[11,00,01,10]
5: 01->110   table->[11,01,00,10]
6: 10->111   table->[11,01,10,00]
7: 10->110   table->[11,10,01,00]
8: 11->0     table->[11,10,01,00]
9: 01->110   table->[11,01,10,00]
10: 11->0    table->[11,01,10,00]
11: 00->111  table->[11,01,00,10]
12: 00->110  table->[11,00,01,10]
13: 00->10   table->[00,11,01,10]

Result for round 2 of bubble: 3x1 + 2x2 + 8x3 = 31 bits

A big increase for bubble... so bubble is d.e.a.d for this case at least ;) 
:)

Pretty cool... maybe in next post I try his switch idea in table form ;) :)

Bye,
  Skybuck. 


0
Skybuck
1/10/2011 8:55:56 PM
comp.compression 4675 articles. 0 followers. Post Follow

0 Replies
464 Views

Similar Articles

[PageSpeed] 2

Reply: