Re: Compression identical to its inverse?
- From: "George Johnson" <matrix29@xxxxxxxxxxx>
- Date: Sun, 2 Dec 2007 22:50:34 -0500
"James Dow Allen" <jdallen2000@xxxxxxxxx> wrote in message
news:03fb7d2d-8e53-427f-9215-92643adce9d5@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
|
| (This is not a practical comment or question,
| but just a puzzle that might intrigue.
| I'd post it to rec.puzzles instead, but readers
| of this group are more likely to have the
| requisite background.)
|
| Show a compression algorithm that is *identical*
| to its corresponding decompression algorithm.
|
| The solution I'm thinking of is quite trivial --
| just a few lines of code -- and could actually
| have practical use on very simple files (or as
| the final bit-coding stage in a compression system).
| Perhaps there are other interesting examples
| of systems with (compression == decompression).
|
| (Of course an algorithm which first determines whether
| input is compressed or uncompressed doesn't count
| as a single compression == decompression algorithm.)
|
|
| Gmail me at jamesdowallen
Sure, they call it a "RESTACKER".
Take 00101000100011111010111010001011
Read ---------------------->>>
Break it chunks of 4 bits (for easy reading
0010 1000 1000 1111 1010 1110 1000 1011
Read ---------------------->>>
Now Stack
0010
1000
1000
1111
1010
1110
1000
1011
Now Read downwards and to the right (or left if you desire) for
reshuffle
| 0010 (or just take the 1st digit, skip 3, take 2nd digit, skip 3,
etc...)
| 1000
| 1000
| 1111
| 1010
| 1110
V 1000
1011
Identical number of bits, just restacked
0111 1111 0001 0100 1001 1101 0001 0001
The entropy (statistically speaking) is also identical because all of
the bits remain unflipped and the shuffle is orderly.
The better trick is to take a Pseudo-Random generator and restack using
that.
One easy to calculate example is to wrap using a number that is greater
than 1/2 the sequence length and a prime number.
The sequence above is 32 digits long.
The next prime number above that is 32 / 2 = 17.
So let's take every 17th number and wrap that. You can choose differing
permutations (without changing the entropy) by adding a number to your prime
for the first locational digit. For example, instead of picking the first
digit as 17, you can add N digits, then add only 17 afterward while shifting
to the righthand direction until you regain your starting point 32
calculations later.
0010100010001111 1 010111010001011
^ 17th digit
0 0 101000100011111010111010001011
^ 34th digit ( 17*2 MOD 32 = 2 )
001010001000111110 1 0111010001011
( 17*3 MOD 32 = 19 ) ^ 51st digit
And so on... with the result being
10101010100011110010110010001011
For inital permutation increment = 0 and right jump = 17
A free Windows BASIC compiler
http://www.justbasic.com/
A simple BASIC program (hopefully you kiddies can read the easiest to
comprehend programming language) for this would be:
A$="00101000100011111010111010001011"
L=LEN(A$)
J=17
P=0
FOR T=1 to L
P=P+J
IF P>32 then P=P-32
PRINT MID$(A$,P,1);
NEXT T
END
REM L = Length of A$ (total number of loops)
REM J = Prime number (Preferably greater than LEN (A$) / 2)
REM P = Starting Location Permutations, change this to change the shuffle
REM T = Basic counting loop to run the length of A$
REM IF-THEN loop checks if P>32 to do the lazy loop wraparound
REM MID$ plucks the digit out of the loop to show the digit.
REM *** Keep it simple so most folks can comprehend. ***
==========
Changing P into a FOR NEXT nest allows you to show the entire run.
RESULT
[P=1][J=17] 01010001000111110101110100010100
[P=2][J=17] 10100010001111101011101000101001
[P=3][J=17] 01000100011111010111010001010010
[P=4][J=17] 10001000111110101110100010100101
[P=5][J=17] 00010001111101011101000101001010
[P=6][J=17] 00100011111010111010001010010100
[P=7][J=17] 01000111110101110100010100101000
[P=8][J=17] 10001111101011101000101001010001
[P=9][J=17] 00011111010111010001010010100010
[P=10][J=17] 00111110101110100010100101000100
[P=11][J=17] 01111101011101000101001010001000
[P=12][J=17] 11111010111010001010010100010001
[P=13][J=17] 11110101110100010100101000100011
[P=14][J=17] 11101011101000101001010001000111
[P=15][J=17] 11010111010001010010100010001111
[P=16][J=17] 10101110100010100101000100011111
[P=17][J=17] 01011101000101001010001000111110
[P=18][J=17] 10111010001010010100010001111101
[P=19][J=17] 01110100010100101000100011111010
[P=20][J=17] 11101000101001010001000111110101
[P=21][J=17] 11010001010010100010001111101011
[P=22][J=17] 10100010100101000100011111010111
[P=23][J=17] 01000101001010001000111110101110
[P=24][J=17] 10001010010100010001111101011101
[P=25][J=17] 00010100101000100011111010111010
[P=26][J=17] 00101001010001000111110101110100
[P=27][J=17] 01010010100010001111101011101000
[P=28][J=17] 10100101000100011111010111010001
[P=29][J=17] 01001010001000111110101110100010
[P=30][J=17] 10010100010001111101011101000101
[P=31][J=17] 00101000100011111010111010001010
As you can see, it is just a bitwise shift and not a permutation shift
Orderly shifts and orderly bitswaps result in no net change in entropy
(no decrease or increase in compressability ratios)
.
- Prev by Date: Re: Using PI for compression...
- Next by Date: Re: Using PI for compression...
- Previous by thread: Re: Compression identical to its inverse?
- Next by thread: LZPM v0.13 - ROLZ-based file compressor
- Index(es):
Relevant Pages
|
