Storing the degree 32 data more compactly

[fingolfin]

Perhaps you already have plans for this, but it seems the degree 32 data takes up 1.4 GB, yet I think this can be reduced by at least a factor 3, possibly more (and that is not yet even considering the option of storing everything gzip compressed).

Some suggestions follow; if you are interested, I would also be willing to help implementing them; after all, I could use some of the techniques for my SGL extension anyway.

1. dat32/trans32.grp takes up 17 MB but could be reduced to less than 20 kb. Namely, we notice that in TRANSSIZES[32] there are only 487 distinct entries in that array. So we only need to store a list of pairs [n,count], and count indicates how often n occurs in TRANSSIZES[32]. From this one, can reconstruct the array during loading.

2. Indeed, TRANSSIZES[32] also takes up 21 MB of RAM. This could also be reduced, by replacing all read access to TRANSSIZES with calls to a help function TRANSsizes (this change would also make future HPC-GAP support easier). This helper function can return TRANSSIZES[deg] for most degrees, but for degree 32 we can do something different.

3. The various dat32/trans32*.g files are 2-3 MB each. They mostly consist of degree 32 permutations. As they are stored in cycle notation. I sampled some of the files, and it seems that on average, over 94 bytes are used to store each permutation (the minimum, if all 32 points are moved, is 88 bytes for a full cycle; add 1 byte for each cycle in the cycle decomp). But we can do much better: We can store permutations as strings of length 32 (almost a factor 3 better):

gap> perm;
(1,23,9,31,20,8,27,15)(2,24,10,32,19,7,28,16)(3,21,11,30,17,5,26,13)(4,22,12,29,18,6,25,14)
gap> List(ListPerm(perm, 32), n->IdentifierLetters[n]);
"LMJKONQPTUSR23014567@A89CBDEGFIH"

To further reduce the overhead (avoding quotes and commas) one can simply concatenate these strings.

Of course one can do even better: 32 values fit exactly into 5 bits, times 32, makes 160 bits or 20 bytes. But then you'd have to be willing to store binary data. If one instead uses base64 encoding, one could store these 160 bits in 26 ASCII character and with base122 it gets down to 23 characters. Implementing this is quite easy, and should reduce the data size by a factor in the ballpark of 88/23 = 3.82.

[fingolfin]

I implemented idea 1 in PR #6, and also wrote a prototype for 3. Turns out I was a bit too optimistic, I only reduced the data to a bit under 800 MB (still nice, though). The reason for that is that I missed the fact that also TRANSPROPERTIES is in there. But that is immediately an opportunity in itself, as that structure contains highly redundant data. By exploiting that, I am confident that one can still get down to below 600 MB, perhaps better.

[fingolfin]

I have a prototype now which results in a final size of dat32 of 425 MB. This is without gzip. If I also gzip the files, it goes down to 108 MB.

[hulpke]

@fingolfin
These are files which were automatically created and -- to avoid errors I rather kept them large then starting to fiddle with the creator code. (The original format is a magma data base file which we anyhow could not read.
If you are confident in the changes, I'd be happy to merge.

[fingolfin]

I am confident in the changes in so far as they were (a) generated by a script, and then (b) the output was compared to the original file (by reading first the one, copying the data to a different global variable, then reading the other, and then comparing the new and old data).

I could also provide the scripts I used to make the compression. Perhaps they could be of use for future cases?

[fingolfin]

I need to pick this up again. For the record, here are some file size stats from my prototype:

$ du -hs dat32*
1.4G	dat32
248M	dat32-gz
425M	dat32-new
108M	dat32-new-gz

So the .tar.gz will be less than half as big as it is now, and uncompressed it still saves a gigabyte or so. (and there is still room for improvement, I think).

The -gz directories contain every file compressed separately via gzip -9; that is less efficient than compressing a whole archive, but on the up side it means that GAP can access the files as they are, so one could ship them like that to users (except on Windows, where we currently don't support this).

The "compression" right now is transparent to the rest of the package: i.e. reading a "compressed" file will produce the same result as reading one of the existing data files. This means that each file contains code for decompressing. I could change that, which would save some more storage, but then requires changes to the loading code.

One major chance for improvement which I have not yet investigated would be to replace HexStringBlistEncode and BlistStringDecode by something more clever. That could provide another factor of 2 or so (for non-gz version, that is).