paq8px

[Gotty]

No, there is not.
It's an experimental compressor: too slow, too much memory use. Impractical. So no one is banging on the door that it should be easily embedded into other software. So it has a simple interface (command line), no API, no DLL version.
What is your use case? What's on your mind?
(Warning: it's not recommended for any production use.)

[moisesmcardona]

Is there any DLL implementation of paq8px ?

There's no DLL implementation, but if you want to integrate it into a software, you can call it via command line like I do in PAQCompress. Then you can parse the console output. The only downside is that it will not report the real progress due to it using redirected output.

[aev]

Thanks for clarifying.
I was impressed at the high compression ratio of this compressor.
And I wanted to use it as an alternative to LZMA2, Brotli, ZSTD to compress small utf-8 text blocks (1-64 kb) ...

[Gotty]

- Replaced the RNG with a simpler and faster one (which is equally strong for our use case) - 0.7% speedup
- Removed HASHCONFIGCMD support (set hash magic numbers from command line)
- Tuned hash multipliers such that m-1 is divisible by 4
- ContextMap2 now supports any many contexts; context flags can now be set per contexts (vs. per model)
- Improved SparseBitModel
- Small improvements in DmcModel/DmcForest
- Tuned some states in StateTable; Enhanced probabilistic increment
- Separated hashed contexts from StationaryMap into a new map: LargeStationaryMap (with collision detection)
- Improved StationaryMap: we store exact counts now

[Darek]

Scores of my test corpus for paq8px v198 - in general nice gains for almost all files - about 2KB in total.
Now, the paq8 series takes 22 records of 28 files for my testbed. Left 6 records only for cmix serie.

[Gotty]

(In the header of the summary table it's "paq8sk v198", it should be "paq8px v198")

[Darek]

Yes, sorry, my error. Updated.

[Darek]

Here are 4 corpuses scores for paq8px v198. In general - the best scores of all testsets. For Silesia - there's about only 50KB loss to best ever cmix v18 score (with preprocessing).
Still there are some previous versions best scores especially for Silesia corpus.

There are even something strange which happens with tarball files for Calgary.tar and Canterbury.tar files which lost huge between paq8px v192 and paq8px v193 versions. They "lost" 15KB and 8KB of the previous score.

[Gotty]

Many thanx for your efforts, Darek!

[LucaBiondi]

Paq8px v198 Vs. v197

compression level -9





=> Globally Size reduced of 38KB
=> Globally time reduced from 54286 seconds to 52820 seconds.

Improved compression of all data types, expecially:
JPG gain -10K
TXT gain -11K
ISO gain -8.5K


Version Paq8px v198 compression level -9/-10/-11 comparison





Luca

[Gotty]

- MatchModel: removed SmallStationaryContextMap, slightly improved the StateMap-based contexts
- Set MatchModel CM scale to 64 for a small gain
* Improvements in IndirectModel; introducing LargeIndirectContext
- Added 1 (binary) context to SparseBitModel
- Increased (doubled) memory use of SparseModel and IndirectModel
- NormalModel now includes the BlockType in its contexts
* Introducing probabilistic hash replacement strategy for ContextMap, ContextMap2 and LargeStationaryMap
- Other small fixes and cosmetic changes

Two highlights:

* Improvements in IndirectModel; introducing LargeIndirectContext
What happened to SparseModel in v197 the same happened to IndirectModel in this version - complete review / rewrite. Noticeable gain for most files. Also noticeable speed loss due to the new contexts added.

* Introducing probabilistic hash replacement strategy for ContextMap, ContextMap2 and LargeStationaryMap
The problem with the hash replacement strategy up until now was that it had the tendency to keep "large count" context statistics for long time. For semi-stationary files it was a good strategy as contexts in such files are usually long-term. But for mixed-content files (for example those having multiple block types) this led to memory-pressure as statistics for obsolete contexts would not be evicted from the hash table and new, low-count contexts would be overwritten instead. The current change addresses this issue. As a result expect a gain for larger mixed-content files (such as silesia/mozilla), small-gain / no gain / small loss for semi-stationary files (such as silesia/dickens and enwik*). The solution may be further tuned, but I think for now it is somewhat "balanced" between these two type of files. As a rare sufferer, Silesia/webster (being a large semi-stationary file) loses some KBs.
As this new strategy also performs move-to-front it has a small speed-benefit: frequently accessed hash items are found in the front of a hash bucket and so finding them needs less iterations. This speed-gain cannot completely cancel out the speed loss from the IndirectModel improvements, so v199 is still slower than v198.

paq8px_v196 -8 mozilla: 6955820
paq8px_v197 -8 mozilla: 6919615 (-36K) <- rewritten SparseModel
paq8px_v198 -8 mozilla: 6915818 (-3K
paq8px_v199 -8 mozilla: 6879971 (-35K) <- rewritten IndirectModel + probabilistic hash replacement

Multimedia files are not (really) affected (images, audio, jpg).

[moisesmcardona]

Hey Gotty, I compiled paq8px, but this time I got the following warnings:

H:/repos/paq8px/ContextMap.cpp: In member function 'set':
H:/repos/paq8px/ContextMap.cpp:25:29: warning: writing 1 byte into a region of size 0 [-Wstringop-overflow=]
   25 |     p[1 + ((c >> 5U) & 1U)] = 1 + ((c >> 4U) & 1U);
      |                             ^
H:/repos/paq8px/HashElementForContextMap.hpp:19:15: note: at offset 0 to object 'bit' with size 1 declared here
   19 |       uint8_t bit;
      |               ^
H:/repos/paq8px/ContextMap.cpp:26:29: warning: writing 1 byte into a region of size 0 [-Wstringop-overflow=]
   26 |     p[3 + ((c >> 4U) & 3U)] = 1 + ((c >> 3U) & 1U);
      |                             ^
H:/repos/paq8px/HashElementForContextMap.hpp:19:15: note: at offset 0 to object 'bit' with size 1 declared here
   19 |       uint8_t bit;
      |               ^
H:/repos/paq8px/ContextMap.cpp:29:29: warning: writing 1 byte into a region of size 0 [-Wstringop-overflow=]
   29 |     p[1 + ((c >> 2U) & 1U)] = 1 + ((c >> 1U) & 1U);
      |                             ^
H:/repos/paq8px/HashElementForContextMap.hpp:19:15: note: at offset 0 to object 'bit' with size 1 declared here
   19 |       uint8_t bit;
      |               ^
H:/repos/paq8px/ContextMap.cpp:30:29: warning: writing 1 byte into a region of size 0 [-Wstringop-overflow=]
   30 |     p[3 + ((c >> 1U) & 3U)] = 1 + (c & 1U);
      |                             ^
H:/repos/paq8px/HashElementForContextMap.hpp:19:15: note: at offset 0 to object 'bit' with size 1 declared here
   19 |       uint8_t bit;
      |               ^
[100%] Built target paq8px

Is this of any concern?

UPDATE: Also happens in Linux on WSL. Previous versions did not gave those warnings. GCC version is 10.2.1 in Linux and 10.2.0 in MSYS.

[Gotty]

It looks like a gcc 10+ issue. Most likely a harmless false positive warning. See for example: https://github.com/tarantool/tarantool/issues/5564
GCC 9.3.0 and VS 2019 has no warning.

[CompressMaster]

@LucaBiondi
Could you post also column names? Because its little bit confusing what number belong to what column - original size/compressed size/time/ etc.
It will be useful for others. Thanks.

[moisesmcardona]

It looks like a gcc 10+ issue. Most likely a harmless false positive warning. See for example: https://github.com/tarantool/tarantool/issues/5564
GCC 9.3.0 and VS 2019 has no warning.

Thanks! Also found out that it is not doing a proper static executable even with -static added to the linker settings.

ldd paq8px.exe
        ntdll.dll => /c/WINDOWS/SYSTEM32/ntdll.dll (0x7ffedb650000)
        KERNEL32.DLL => /c/WINDOWS/System32/KERNEL32.DLL (0x7ffeda8f0000)
        KERNELBASE.dll => /c/WINDOWS/System32/KERNELBASE.dll (0x7ffed9170000)
        msvcrt.dll => /c/WINDOWS/System32/msvcrt.dll (0x7ffed95f0000)
        SHELL32.dll => /c/WINDOWS/System32/SHELL32.dll (0x7ffed9cc0000)
        msvcp_win.dll => /c/WINDOWS/System32/msvcp_win.dll (0x7ffed94e0000)
        ucrtbase.dll => /c/WINDOWS/System32/ucrtbase.dll (0x7ffed8c60000)
        USER32.dll => /c/WINDOWS/System32/USER32.dll (0x7ffeda9b0000)
        win32u.dll => /c/WINDOWS/System32/win32u.dll (0x7ffed8f60000)
        GDI32.dll => /c/WINDOWS/System32/GDI32.dll (0x7ffedb040000)
        gdi32full.dll => /c/WINDOWS/System32/gdi32full.dll (0x7ffed9050000)
        zlib1.dll => /trunk/msys64/mingw64/bin/zlib1.dll (0x7ffeb55e0000)

Whereas before (v197 and before) it wasn't complaining about it.

[moisesmcardona]

Another update: Did `pacman -Syu`, deleted cached CMakeFiles and now it did a static build. I noticed my v198 builds required libwinpthreads for some reason, and v199 required zlib1 but not libwinpthreads. Checked v197 and it was fine, so something in my environment messed up something. My compiles of paq8pxd didn't suffer from this issue. Good news is I got it solved on my end.

[Darek]

Scores of paq8px v199 on my testset. Another 10KB of gain!
However exe files (G.EXE, I.EXE and J.EXE) got loses comparing to veriosn 198. Also both WAV file and textual files (for non LSTM option) got some loses.

[Darek]

My testbed score for SOLID compression (paq8px with list) got firtst time score below 10'000'000 bytes for paq8px v199!!!!
Score for paq8px v199: 9'992'701 bytes = 24,74% of original size! Thank you ALL!

And Happy New Year to everyone!!!! Let it will be better year than 2020!

[Sebastianpsankar]

What about a compression algorithm that can compress gigabytes to less that 1 Mb or even gb's to kb's?

[Sebastianpsankar]

I've invented an algorithm that can compress I 10 gb to 10 kb... What are you comments?

[Sebastianpsankar]

0
Thanked 0 Times in 0 Posts
I've invented an algorithm that can compress I 10 gb to 10 kb... What are you comments?
Edit / DeleteEdit Post Quick reply to this messageReply Reply With QuoteReply With Quote

[Gotty]

Sebastianpsankar,
Please let's discuss your idea in the thread you started, not here.

[Gotty]

Let's close the year 2020 with v200.

- Speed improvements in ContextMap and ContextMap2
- In ContextMap2 updating bit histories for bits 2-7 was deferred for the first byte; now it is deferred for the first 3 bytes (both speed and compression improvement)
- Small speed improvement in Bucket16

This version intends to compensate the speed loss of v199 and still have a bit better compression ratio.
The highlight of this version is extending the lazy update from 1 byte to 3 bytes in ContextMap2. What does it mean?

A lot of contexts happen only once and so they are not useful as they provide no help for the prediction. Even if they don't happen again, paq8px needs to memorize their statistics in the hope that they will be useful. As statistics for newer and newer contexts will slowly fill up every hash bucket, the statistics of these happened-only-once contexts will be evicted after some time as commanded by our hash replacement strategy. So no problem. Or is it? It's actually a problem: when the hash buckets are full, every new context needs to overwrite some existing context. Some of these new contexts will happen again, and they will be useful for the prediction, but many of them will not be useful at all. At the first encounter however there is no way we can tell if a new context will be useful or not. So we must store them. Even if the hash buckets are full. So useful contexts may be overwritten by useless contexts. That's not good.

In Contextmap and ContextMap2 bit and byte statistics for every (new) byte context would take up 7+7+7 bytes (in 3 different hash buckets). It means that we will overwrite statistics in 3 hash elements when these buckets are full. Can we do some trick not to use 3 hash buckets on the first encounter and so not to lose our older (and probably more mature) statistics stored there? Yes, we can.

Paq8px inherited an ingenious trick form paq8l: let's just not store all the bit statistics in all the 3 buckets on the first encounter, let's just store the byte itself in the first hash bucket. When the same context is encountered for the second time, let's update the 2nd and 3rd hash buckets with the proper statistics as we would have done it at the first encounter. This trick seriously reduces the pollution caused by happened-only-once contexts.

In this version we now "extend" this trick: we defer updating the 2nd and 3rd hash bucket not just for the first but also for the next two bytes: anyway we store these bytes in the first bucket, so they come free. The only downside is that during prediction we need to somehow reconstruct the bit-statistics in the 2nd and 3rd hash buckets. So instead of updating the hash table we are updating a temporary location used just for this reconstruction. It is actually faster since it's cache-friendly: instead of looking up the hash bucket and reading/writing statistics there (that's a cache-killer), we do the same (the reconstruction) in a fixed location (and that is cache friendly). Luckily better compression with speed improvement are coming hand in hand in v200.

The above described solution helps when hash tables are full so don't expect much change with smaller files - improvement is more prominent in case of larger files.

[Darek]

Scores of my testset for paq8px v200 - according to scores total score is slightly worse than paq8px v199, however some bigger files (G.EXE, H.EXE and K.WAD) got some but also small gains.
Timigs are:

G.EXE (std) -> v199 = 402,47s, v200 = 368,58s = 8,4% of gain
G.EXE (lstm) -> v199 = 1121,92s, v200 = 1044,18s = 6,9% of gain

K.WAD (std) -> v199 = 2308,10s, v200 = 2065,35s = 10,5% of gain
K.WAD (lstm) -> v199 = 6885,19s, v200 = 6278,32s = 8,8% of gain

[Gotty]

>>according to scores total score is slightly worse than paq8px v199
Yes, in your testset there are no files that benefit from the change in v200 -true. The big ones (K.WAD and L.PAK) are famous for being "special".
In maximumcompression and silesia you will find files that benefit from v200. (Not in calgary nor cantenbury - they are too small.)

Thank you for the speed tests!

[Darek]

Scores of 4 Corpuses for paq8px v199 and paq8px v200.

Great gain for Silesia. The paq8px v200 is slightly better than paq8px v199, got 43'036 bytes of gain compared to paq8px v198 and (unfortunatelly) is still 4'758 bytes worse than best cmix v18 score (with precomp)... but it's very, very close now! MaximumComprssion got about 2KB of gain. Other corpuses remain in similar place.

[kaitz]

MC
​

                         paq8px_v200   paq8pxd_v94
​file             size        -s8               -s8
A10.jpg         842468        624597        620980
AcroRd32.exe   3870784        823707        831293
english.dic    4067439        346422        347716
FlashMX.pdf    4526946       1315382       1334877
FP.LOG        20617071        215399        201621
MSO97.DLL      3782416       1175358       1190012
ohs.doc        4168192        454753        451278
rafale.bmp     4149414        468156        468757
vcfiu.hlp      4121418        372048        264060
world95.txt    2988578        313915        311700
Total                        6109737       6022294

[Gotty]

- IndirectContext improvement: using a leading bit to distinguish context bits from empty (unused) bits
- LSTM model: Applied the new IndirectContext improvements
- MatchModel improvements: 
  - moved context hashes from NormalModel to Shared so MatchModel can also use them
  - using more candidates in hashtable (3 instead of 1)
  - using the improved IndirectContext
  - refined contexts
  - tuned NormalModel contexts wrt MatchModel context lengths

[CompressMaster]

My quick test on A10.jpg from MaximumCompression corpus using the -7 switch:
Total input size: 842 468 bytes
Compressed size: 624 693 bytes

btw, pure hypothetical question: when you will expect to reach compression of A10.jpg below 150 000 bytes?

[Darek]

My quick test on A10.jpg from MaximumCompression corpus using the -7 switch:
Total input size: 842 468 bytes
Compressed size: 624 693 bytes

btw, pure hypothetical question: when you will expect to reach compression of A10.jpg below 150 000 bytes?

In my opinion - in 2077

By the way - paq8pxd v95 got score 618'527 bytes for A10.jpg file with option -x9