paq8gen - sequence compressor

[Gotty]

Also, it's funny seeing how you find and tackle the same things as I do, like the low precision problem (you really went scorched earth on that one, 28 bits of precision? ).

It's funny indeed. LILY and paq8gen are always head to head. So following that pattern, now paq8gen must go under 600K. OK. Don't know how on earth it's gonna be, yet. Feel free to add your magic there.

If you're serious about the sars-cov-2 benchmark, why not just create a new branch of paq8gen on the repo dedicated to it, instead of polluting the main version with a bunch of #defines?

I'm not that serious about squeeze the last bits from the exe. (You can see it's not my priority.) Pushing compression further is what I'm into. When enhancing paq8gen I'm also checking my changes against two other corpus: what I call the small DNA corpus (https://encode.su/threads/2105-DNA-Corpus) and the large one: https://tinyurl.com/DNAcorpus (referenced from GeCo3: https://github.com/cobilab/geco3). So for me it's a threefold challenge.
Paq8gen is far from a proper genomic sequence compressor, yet: it should support a line-unwrapping transform and reordering sequence names and sequences automatically for example. Or look for palindromes... Or anything I haven't even heard of
If you've got ideas and have some time - feel free to join and let's make it a good entropy estimator in the genomic-compression field.

[Gotty]

I don't have personal reason with mpais, I just see the result of paq8gen is better than lily.

Oh, I thought it could be more.
OK, I'm glad then!

[Gotty]

Back to the ACGT-alphabet-reordering.
These are the results from the small DNA corpus:



There is no clear winner which reordering is the "general best". There are some green areas though.

Meanwhile I found the optimal alphabet-transform for the sars-cov-2 challenge: it's GCAT (meaning: 'G'->0; 'C'->1; 'A'->2; 'T'->3).
It's followed closely by GCTA, CGAT, CGTA). Hmm... So G likes to be together with C and A with T. Looks like we've got something - see: https://en.wikipedia.org/wiki/Comple...cular_biology)

But it does not really match with the results from the small DNA corpus. The difference in compression is significant.
Who's got some insight?

[Shelwien]

The difference between bytewise and bitwise model is that after occurrence of some symbol,
a bytewise model increases the probability of only this symbol, while decreasing all others.
While bitwise model also increases the probability of some groups of other symbols with a matching prefix.
So we can view the alphabet permutation as an approximation of non-binary APM.
This would mean that optimal permutations can easily be different not only for different files, but even for different contexts.
(Which can be even practically implemented by building symbol probability distributions from binary counters
separately for each context, then converting these distributions to a common binary tree for mixing and coding.)

Btw, alphabet permutation is not limited to permutations of 0..3 even for target files with only 4 symbols.
A code like {0001,0010,0100,1000} would have a different behavior than any of 0..3 permutations.

[mpais]

So following that pattern, now paq8gen must go under 600K.

As I said in the challenge thread, I expect paq8gen to get down to 57x.xxx, at least, so no pressure

If you've got ideas and have some time - feel free to join and let's make it a good entropy estimator in the genomic-compression field.

The thing is, I don't think anyone in that field would even use it.

Maybe innar, Kirr and JamesB have a different opinion on that, but it seems people in that field just cook up their own flawed compressors (see the benchmark that Kirr put together, especially his comments on each compressor) as long as it suits their particular workflow. For archiving and transmitting the large datasets they use, paq8gen is just too slow. And judging by innar's comments, it seems the field is not convinced of the use of compression algorithms as a way to find similarities between sequences. That's why I don't see the point in continuing working on LILY for this either.

I'd rather work on something fun and useful, work is boring enough as it is, which is why I proposed fairytale in the first place, it would have kept me busy writing open-source versions of LILY, EMMA, LEA, etc. Alas, that ship has sailed, so maybe it's time for a new hobby.

[Gonzalo]

I'd rather work on something fun and useful, work is boring enough as it is, which is why I proposed fairytale in the first place, it would have kept me busy writing open-source versions of LILY, EMMA, LEA, etc. Alas, that ship has sailed, so maybe it's time for a new hobby.

You want to work on Fairytale? No-one is stopping you, to be fair

Maybe there aren't a lot of people on board just yet but you know that can change in a heartbeat. I know I for one would test the hell out of the thing. Maybe I'm not a developer, but that hasn't stopped me from collaborating on lots of projects. Just look at all the bugs I've found in precomp, for instance...

[spaceship9876]

I'm not sure if this is relevant or not: https://jpeg.org/items/20201226_jpeg...ouncement.html

[mpais]

You want to work on Fairytale? No-one is stopping you, to be fair

Sure, but no one helped either. We've discussed this before, writing a full blown archiver as ambitious as that, on my free time, is delusional. There's a reason most of us here write single file compressors. An archiver needs to implement a lot more functionality (adding content to an existing archive, deleting content from an archive, partial extraction, etc) and we wanted to do it in an OS and ISA independent way, i.e., it should just work out of the box on Windows, Linux, MacOS, etc, and on x86, ARM, MIPS, RISC-V, etc. That is way above my skill level.

Anyway, that is off-topic and I don't want to derail the thread. Gotty is doing a fine work on paq8gen, the paq8 legacy is in good hands.