paq8gen - sequence compressor

[Gotty]

A new member of the paq8* family - specialized (but not limited) to (genomic) sequencing data.

~ 6x faster than paq8px

- Forked form paq8px_v200 (https://github.com/hxim/paq8px)
- Removed most models except MatchModel, NormalModel, WordModel, DMCForect/DMCModel, LSTMModel
- Removed most transformations except EOL
- Removed most detections except Text
- Removed all pre-training
- Removed most command line options except Adaptive Learning Rate (A), LSTM model (L)
- Removed some NormalModel mixer contexts, removed the fast order 1 model
- Renamed WordModel to LineModel, removed all contexts except some linemodel ones
- Increased NormalModel contexts from 14->24
- Increased MatchModel minimum match length: 5->16, stepsize: 2->8
- Tuned mixer scaling factor: 940, 80 -> 2048, 256

This release does not perform any transformations for the FASTA or the 2bit formats, yet. Please do your transformations before compressing.
Suggested transformation in case of FASTA (multi FASTA): 1) create two sections: one with titles another with sequence data, 2) remove line breaks from sequence data.

Although ...
- it supports the usual -1..-12 compression levels, it looks like high levels are not really needed - compression is almost the same at lower memory levels as on higher ones (in case of the FASTA format at least).
- it contains the LSTM model, it seems to have no benefit on this kind of data.
- it still has the -a command line switch (Adaptive Learning Rate), it seems to have no benefit on this kind of data.

Source: https://github.com/GotthardtZ/paq8gen
Windows binaries: https://github.com/GotthardtZ/paq8gen/releases/tag/v1

Contributions and tweaks are welcome.

[Gotty]

- Added 10 contexts and 2 mixer context sets to LineModel

Source: https://github.com/GotthardtZ/paq8gen
Windows binaries: https://github.com/GotthardtZ/paq8gen/releases/tag/v2

[Gotty]

Attached some test files that may help development/testing:

coronavirus.fasta.preprocessed.full
-> Proprocessed coronavirus.fasta (original obtained form https://coronavirus.innar.com/)
-> Descriptions (lines starting with ">") are moved to the front, fixed length line breaks are removed (reversible transformation).

coronavirus.fasta.preprocessed.descriptions_only.0
-> Only the description lines. This is exactly the coronavirus.fasta file without the sequence data. This is also the 1st part of coronavirus.fasta.preprocessed.full.

coronavirus.fasta.preprocessed_seq_only.6
coronavirus.fasta.preprocessed_seq_only.7
coronavirus.fasta.preprocessed_seq_only.8
-> Only the sequence data: the first ~ 1MB, 10 MB, 100 MB of coronavirus.fasta ignoring the description lines.

[Gotty]

coronavirus.fasta.preprocessed_seq_only.8 100'003'453 bytes

paq8px_v200.exe -8    116775 bytes
paq8gen_v1.exe  -8    109364 bytes
paq8gen_v2.exe  -8    107662 bytes

coronavirus.fasta.preprocessed.full 1'317'937'667 bytes

paq8px_v200.exe -12L   (not planned to run - something similar is running at mpais on the 2bit version)
paq8gen_v1.exe  -12    1'118'915 bytes   23275.12 sec
paq8gen_v2.exe  -12    1'085'007 bytes   25974.80 sec

[Gotty]

Summary for paq8gen_v1:

Size optimized exe in zip archive: 48'801 bytes
Transform source code in zip archive: 1'423 bytes
Compressed archive: 1'118'915 bytes
Total: 1’169’139 bytes
It's just below LILY (which is 1,169,683). Wow, that's very close.
Let's wait for v2. Or maybe v3.

[mpais]

LILY        1.082.639 bytes, decompressed in 240s

I think a specialized compressor would make a lot more sense Gotty, paq8 is just too slow.
LILY isn't even optimized for this and is 2 orders of magnitude faster without any speed optimizations (not my forte).
A compressor designed for the fasta format with similar techniques should go below 1.000.000 for the full entry (including the decompressor size).

Time to make a small decoder for undoing the preprocessing and reclaim #1 spot

[Darek]

- Added 10 contexts and 2 mixer context sets to LineModel

Source: https://github.com/GotthardtZ/paq8gen
Windows binaries: https://github.com/GotthardtZ/paq8gen/releases/tag/v2

@Gotty: Link to Windows binaries provides still to verision 1. Of course you can rename "v1" to "v2" and it works.

Question, maybe silly, sorry but I'm curious: Is this kind of compression, or this particular compressors: LILY and paq8gen) could help in some actual COVID data maintenance or it's general idea to reduce space of genom files?

[Gotty]

@Gotty: Link to Windows binaries provides still to verision 1. Of course you can rename "v1" to "v2" and it works.

Thank you, Darek! The link for v2 is fixed

Question, maybe silly, sorry but I'm curious: Is this kind of compression, or this particular compressors: LILY and paq8gen) could help in some actual COVID data maintenance or it's general idea to reduce space of genom files?

Don't know. Better ask it in the main thread.

[Gotty]

I think a specialized compressor would make a lot more sense Gotty, paq8 is just too slow.
LILY isn't even optimized for this and is 2 orders of magnitude faster without any speed optimizations (not my forte).
A compressor designed for the fasta format with similar techniques should go below 1.000.000 for the full entry (including the decompressor size).

I realized that you started running paq8px_v200, and thought why not remove all the noisy models first, and give a little boost to the important ones (matchmodel and normalmodel). So here it is - now you may play with this one instead. New year's present
Paq8gen is also not optimized, just tweaked a little bit. Even the size optimized exe is a full version - just compiled with size optimization flags - it contains all the screen output, too. It's not really a proper entry (I didn't send it).
Yes, a specialized compressor would make more sense (from practical point of view). My intention is to see if we are hitting the limit or is it still some gap to fill.

[mpais]

I realized that you started running paq8px_v200

Not my brightest idea, I'll give you that

Yes, a specialized compressor would make more sense (from practical point of view). My intention is to see if we are hitting the limit or is it still some gap to fill.

As I stated in the challenge thread, in this format the best submissions in terms of ratio will probably be worthless because they'll simply be a closed-source "generator" for this specific file.

Simply analysing the sequence names and integrating that knowledge into the decompressor/transform should allow for another 2KB of reduction in the payload (for LILY, probably less for paq8gen).

Each of the 44918 sequence names starts with ">" and ends with a space followed by a new line (#10).

The length of these names is either 10 (almost always), 6 (17 times) or 11 (only once). Using a simple RLE encoding reduces it to 42 bytes, plus whatever small increase in the decompressor for the required instructions to decode it. Or one can simply hardcode it and be done with it. So 3 x 44918 bytes can already be reduced to maybe 100 or less.
Now consider that for each sequence name of length L (excluding the space), it's [L-2] byte is always "." unless L = 6, in which case it's always "_". That means we can also skip that byte, so it's now 4 x 44918 bytes that we get almost for free.

It's not that this sort of analysis isn't fun, but I don't see the point.

[Gotty]

Updated results with v2.

[Gotty]

Summary for paq8gen_v2:

Size optimized exe in zip archive: 49'284 bytes
Transform source code in zip archive: 1'423 bytes
Compressed archive: 1'085'007 bytes
Total: 1’135’714 bytes.

(It's still not a proper entry. Still adjusting.)

[Gotty]

Simply analysing the sequence names and integrating that knowledge into the decompressor/transform should allow for another 2KB of reduction in the payload (for LILY, probably less for paq8gen).

Each of the 44918 sequence names starts with ">" and ends with a space followed by a new line (#10).

The length of these names is either 10 (almost always), 6 (17 times) or 11 (only once). Using a simple RLE encoding reduces it to 42 bytes, plus whatever small increase in the decompressor for the required instructions to decode it. Or one can simply hardcode it and be done with it. So 3 x 44918 bytes can already be reduced to maybe 100 or less.
Now consider that for each sequence name of length L (excluding the space), it's [L-2] byte is always "." unless L = 6, in which case it's always "_". That means we can also skip that byte, so it's now 4 x 44918 bytes that we get almost for free.

Yes.
See the descriptions ripped out from the original file above.
It can be crunched as follows:

coronavirus.fasta.preprocessed.descriptions_only.0 : 583867 bytes

paq8gen_v1  -8:  5995 bytes   9 sec
paq8gen_v2  -8:  4621 bytes  12 sec
paq8px_v200 -8:  4153 bytes  89 sec

The gen version is far from the px version, simply because it traded most of its power for speed in this area. When tuning gen v2, I was trying to get some back, but still half a KB is there.
I believe (as you do) it is still possible to make a specialized generator for the descriptions, that would beat the px version, but probably can't go too much below.

[mpais]

I made a new transform, incorporating what I described and a remap for the bases, the gain with LILY is a little over 4KB.
So clearly not much, but I expect the best specialized entries to go below 900.000 bytes, at which point every KB would count.

I haven't tested it on paq8gen_v2, I'm still waiting for paq8px_v200 to finish (still 10% to go, already over 1.032.000 bytes, so just a waste of time).

[suryakandau@yahoo.co.id]

Paq8gen2fix1
using -8 option on coronavirus.fasta.preprocessed_seq_only.8 100'003'453 bytes the result is
107242 bytes Time 6263.59 sec, used 1734 MB (1818943501 bytes) of memory

[CompressMaster]

~ 6x faster than paq8px

Edit: compression also better?

[suryakandau@yahoo.co.id]

Paq8gen2fix1
using -8 option on coronavirus.fasta.preprocessed_seq_only.8 100'003'453 bytes the result is
107242 bytes Time 6263.59 sec, used 1734 MB (1818943501 bytes) of memory

using -11 option on coronavirus.fasta.preprocessed.full the result is
1084951 bytes Time 70279.10 sec, used 13017 MB (13649570713 bytes) of memory

[Gotty]

Thank you, Surya for your efforts.

1) I suspect that the NestModel you re-included from paq8px does not help compression. It is modelling brackets, braces and the appearance of some other characters in text files but the target file (coronavirus.fasta.preprocessed.full) has no such things as it is not a normal text file.
After removing NestModel from your solution:

paq8gen -8 coronavirus.fasta.preprocessed_seq_only.8
107250 bytes (+8 bytes)

paq8gen -12 coronavirus.fasta.preprocessed.full
1079516 bytes (-? bytes)

It's a fluctuation, not a compression gain. NestModel probably hurts compression on the long run. The "full' file I run on level 12 and you on level 11 so it is not directly comparable.

2) You added two new contexts in LineModel, but you indicated in the header file that you added three: nCM = 14+2+1; That's inconsistency.

3) You added a mixer context which may have 256 different values but you indicated the range as 512: m.set(line0 & 0xff, 512); 4) Also line0 is a multiplicative hash, in this case the top bits should be used, not the bottom ones. The top ones are strong, the bottom ones are weak. Is there a reason you added the bottom ones?

5) In your attachment there are several source files you re-included from paq8px that are not in actual use. Please don't include such files when trying to releasing a new version. Also you forgot to modify PAQ8PX to PAQ8GEN in the re-included NestModel.hpp (see the last line of the source code).

6) When you include a new source file (NestModel.cpp and NestModel.hpp in this case), you must maintain the visual studio solution file (naturally with visual studio) and the CMakeLists file (with a text editor). Now the solution can't be compiled with either visual studio or using the CMakeLists file, only the batch file you're using.

7) You MUST use git when contributing. Don't post source code in the forum, do a pull request instead.

Altogether your suggested new version does not seem to be significantly better than v2. Especially when taking into account the fact that the newly compiled size-optimized exe when zipped takes more space then before and the gain you have with compressing the target file is not enough to make it worth. I'll run more tests to find which of the two new contexts in LineModel help. Probably the one with firstChar helps enough to make it worthwhile as it separates the descriptions from the sequences a bit better then before.

[Gotty]

Edit: compression also better?

General compression: no.
Sequence compression: yes.

[suryakandau@yahoo.co.id]

Thank you, Surya for your efforts.

1) I suspect that the NestModel you re-included from paq8px does not help compression. It is modelling brackets, braces and the appearance of some other characters in text files but the target file (coronavirus.fasta.preprocessed.full) has no such things as it is not a normal text file.
After removing NestModel from your solution:

paq8gen -8 coronavirus.fasta.preprocessed_seq_only.8
107250 bytes (+8 bytes)

paq8gen -12 coronavirus.fasta.preprocessed.full
1079516 bytes (-? bytes)

It's a fluctuation, not a compression gain. NestModel probably hurts compression on the long run. The "full' file I run on level 12 and you on level 11 so it is not directly comparable.

2) You added two new contexts in LineModel, but you indicated in the header file that you added three: nCM = 14+2+1; That's inconsistency.

3) You added a mixer context which may have 256 different values but you indicated the range as 512: m.set(line0 & 0xff, 512); 4) Also line0 is a multiplicative hash, in this case the top bits should be used, not the bottom ones. The top ones are strong, the bottom ones are weak. Is there a reason you added the bottom ones?

5) In your attachment there are several source files you re-included from paq8px that are not in actual use. Please don't include such files when trying to releasing a new version. Also you forgot to modify PAQ8PX to PAQ8GEN in the re-included NestModel.hpp (see the last line of the source code).

6) When you include a new source file (NestModel.cpp and NestModel.hpp
in this case), you must maintain the visual studio solution file (naturally with visual studio) and the CMakeLists file (with a text editor). Now the solution can't be compiled with either visual studio or using the CMakeLists file, only the batch file you're using.

7) You MUST use git when contributing. Don't post source code in the forum, do a pull request instead.

Altogether your suggested new version does not seem to be significantly better than v2. Especially when taking into account the fact that the newly compiled size-optimized exe when zipped takes more space then before and the gain you have with compressing the target file is not enough to make it worth. I'll run more tests to find which of the two new contexts in LineModel help. Probably the one with firstChar helps enough to make it worthwhile as it separates the descriptions from the sequences a bit better then before.

1. You are correct that nestmodel can hurt compression so in the future I remove it
2. I will check it again in nCM how many context I have inserted
4. When I use line0 only in mixer context, the process is stopped so I use it with &0xff
5. I will remove them
6. I compile it using Min gw only

[moisesmcardona]

Hey Gotty, excellent work with this compressor. Just wanted to tell you the -a flag doesn't actually work.

paq8gen_v2.exe -9a the_file_to_compress
paq8gen archiver v2 (c) 2020, Matt Mahoney et al.
Invalid compression switch: a

The -l flag works fine.

[suryakandau@yahoo.co.id]

i have improved paq8gen2. source code https://github.com/skandau/paq8genome
i can not upload it all so i compress it and upload it

[Gotty]

No-no, it's not how git works.

1) Log in to your github account (and delete that repository you created - it's useless)
2) Visit my repository (https://github.com/GotthardtZ/paq8gen)
3) Click "Fork" in the top right corner. Now you will have a copy of my repository under your account (https://github.com/skandau/paq8gen).
4) Visit your repository (https://github.com/skandau/paq8gen), notice the green "Code" button. That reveals the link to your repository.
5) On your pc create an empty folder, open a command prompt, navigate to this empty folder and issue this command: git clone https://github.com/skandau/paq8gen.git
6) To make git easier for you and to have an IDE, download and install Visual Studio Community Edition (https://visualstudio.microsoft.com/vs/community);in the "Individual components" tab select "Git for Windows" and (optionally) "GitHub extension for Visual Studio".
7) After installation is successful, open the solution file with Visual Studio (simply click on the paq8gen.sln file in windows explorer).
8 ) Make any changes you want in the paq8gen source, or just overwrite the source files in this folder with the one you already have.
9) Test your changes.
10) Commit your changes in the "Team Explorer" window in Visual Studio. (You may need to learn more about it - so do some googling. Learn about staging the changes, unstaging, viewing commit history, comparing commits, pushing and pulling.)
11) Push your changes to your repository with Visual Studio.
12) Log in to your github account again. Create a pull request to my repository.

There are other ways to make it work: you can do it via the command line too and there are many other excellent tools like gitextensions or sourcetree but I'd go with Visual Studio in your case as it is simple enough and has and IDE, a debugger, etc. And you won't forget to update the VS solution file

[Gotty]

Hey Gotty, excellent work with this compressor. Just wanted to tell you the -a flag doesn't actually work.

Thank you moisesmcardona, fixed. (I also noticed it yesterday when I was trying re-testing with it.)

[suryakandau@yahoo.co.id]

here is a little modification of paq8gen..
just testing it for fun on coronavirus.fasta.preprocessed.full and coronavirus.fasta.un-wrapped using -8 option, the result is:
coronavirus.fasta.preprocessed.full
Total input size : 1317937667
Total archive size : 1111982
Time 76408.30 sec, used 1715 MB (1798534789 bytes) of memory
coronavirus.fasta.un-wrapped
Total input size : 1317937667
Total archive size : 1119174
Time 76799.55 sec, used 1715 MB (1798534848 bytes) of memory

[Gotty]

What is you intention? Would you like to contribute to paq8gen?

[suryakandau@yahoo.co.id]

yes i want to contribute to paq8gen but i am still struggling with how to make pull request on github. i am sorry about upload the paq8gen to this forum. in the above result i just want to know which is the smaller output, preprocess.full or un-wrapped.

[suryakandau@yahoo.co.id]

here is an error message when i upload the source of paq8gen to github

[Gotty]

Please delete your paq8gen repository in github.
Follow the points 1) 2) 3) above in my email.

[suryakandau@yahoo.co.id]

the link https://visualstudio.microsoft.com/vs/community/ is page not found.