Re: Compression test on permutations

On Apr 24, 5:59 am, biject <davvid_a_sc...@xxxxxxxxx> wrote:
Actually a trival change to arb255 would compress this type of file
the best.

It's even simpler than that. All you need to do is some multiplying
and adding to encode a variable base 1684 bit number for each block.
Start with zero. Add the first value 0..255. Multiply by 256. Add
the next 0..254 choice for the next value. Multiply by 255. And so
on. You generate an integer that uniquely codes the permutation.

A multiple precision multiply and add is very easy to implement in
this case, since the multiplier is always 256 or less. In fact, I
just wrote it and it works quite nicely. Below is the encoding of the
reverse permutation, 255..0, which gives the largest integer.

This approach is also optimal. Most arithmetic coders make
approximations to keep the arithmetic simple, which will cost a few
bits more.

Mark


ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff 7f
45 9e 13 83 5c ca de bb e0 ff 79 b5 61 95 86 17
8b 80 80 ad 7c 7b e6 4b c4 6c 9b 4d eb 1e 0e 5d
df e5 73 3e d4 7b ab e9 b8 40 a6 ce ce cf f6 94
1a a0 c5 07 c0 1c f5 81 07 1c 31 bf e9 cd 37 4f
80 5c 7f 68 41 42 0d e0 d7 71 65 6d 56 2a a6 a0
a9 37 5b 68 93 48 b8 35 9b b1 5a 01 4e 5b 7e ac
35 27 9f 1d a1 65 e3 ab a0 ee f8 11 6b 69 b6 05
be e0 23 97 f3 d7 23 be db 40 2f 91 93 93 32 f3
a4 1a 4f 52 b5 e5 c2 b8 b4 33 1f f3 be ea 52 1a
fa c3 16 a5 dc 3b eb e6 7f 18 89 58 d1 eb 9a fa
df 98 b5 02 7e 63 27 7d a7 ea 3b 74 bb 15 7c f5
78 f5 0f

.