Paq8pxd dict

[kaitz]

https://circle.ubc.ca/bitstream/hand...pdf?sequence=3 "Byron Knoll"
In 3.2.1 Mixtures of Experts author describes expert networks.
Is this something actualy usable in paq8?

And at page 19. there is usage of Extended Kalman Filter.

There is link to sample apps. but it's dead.

[Shelwien]

http://cs.ubc.ca/~knoll/PAQ8-demos.zip ?
seems to work for me

[kaitz]

http://cs.ubc.ca/~knoll/PAQ8-demos.zip ?
seems to work for me

I did something wrong. No it is working. Thanks.

[Alexander Rhatushnyak]

https://circle.ubc.ca/bitstream/hand...pdf?sequence=3

This is interesting. Doesn't Table 4.4 show that MULTINOMIAL NAIVE BAYES + TFIDF would compress ~1.3% better than paq8 ?

[Matt Mahoney]

1.3% better than paq8l -5 (uses 233 MB memory). Don't know about -8 (1643 MB). The data set is 48 MB with 20 classes, so each compression is 80% of 1 class, or only 2 MB. -8 probably wouldn't make much difference.

[kaitz]

Hi

Nothing special.
Results below. (enwik8 probably suffers a few kb)
Almost a year from last version.

E:\O\PAQ\paq8px_v5>paq8pxd_v5 -8        xml
Creating archive xml.paq8pxd with 1 file(s)...


File list (13 bytes)
Compressed from 13 to 15 bytes.


1/1  Filename: xml (5345280 bytes)
Block segmentation:
 0           | text      |   5345279 bytes [0 - 5345278] (wrt: 3541932)
 1           | default   |         1 bytes [5345279 - 5345279]
Compressed from 5345280 to 264394 bytes.


Total 5345280 bytes compressed to 264419 bytes.
Time 601.73 sec, used 1633426312 bytes of memory


E:\O\PAQ\paq8px_v5>paq8pxd_v5 -8 world95.txt
Creating archive world95.txt.paq8pxd with 1 file(s)...


File list (21 bytes)
Compressed from 21 to 24 bytes.


1/1  Filename: world95.txt (2988578 bytes)
Block segmentation:
 0           | text      |   2988578 bytes [0 - 2988577] (wrt: 1855618)
Compressed from 2988578 to 335447 bytes.


Total 2988578 bytes compressed to 335481 bytes.
Time 323.69 sec, used 1633424256 bytes of memory


E:\O\PAQ\paq8px_v5>paq8pxd_v5 -8 reymont
Creating archive reymont.paq8pxd with 1 file(s)...


File list (17 bytes)
Compressed from 17 to 19 bytes.


1/1  Filename: reymont (6627202 bytes)
Block segmentation:
 0           | text      |   6501239 bytes [0 - 6501238] (wrt: 5389242)
 1           | default   |    125963 bytes [6501239 - 6627201]
Compressed from 6627202 to 792270 bytes.


Total 6627202 bytes compressed to 792299 bytes.
Time 921.97 sec, used 1633426308 bytes of memory


E:\O\PAQ\paq8px_v5>paq8pxd_v5 -8 samba
Creating archive samba.paq8pxd with 1 file(s)...


File list (16 bytes)
Compressed from 16 to 18 bytes.


1/1  Filename: samba (21606400 bytes)
Block segmentation:
 0           | default   |    279004 bytes [0 - 279003]
 1           | text      |   1658664 bytes [279004 - 1937667] (wrt: 1030585)
 2           | default   |    131757 bytes [1937668 - 2069424]
 3           | text      |   2661772 bytes [2069425 - 4731196] (wrt: 1688039)
 4           | default   |   1092855 bytes [4731197 - 5824051]
 5           | text      |    725004 bytes [5824052 - 6549055] (wrt: 562999)
 6           | default   |    420432 bytes [6549056 - 6969487]
 7           | jpeg      |      8020 bytes [6969488 - 6977507]
 8           | default   |    461300 bytes [6977508 - 7438807]
 9           | text      |    678792 bytes [7438808 - 8117599] (wrt: 551048)
 10          | default   |      9673 bytes [8117600 - 8127272]
 11          | text      |  13132289 bytes [8127273 - 21259561] (wrt: 9262568)
 12          | default   |    346838 bytes [21259562 - 21606399]
Compressed from 21606400 to 2851718 bytes.


Total 21606400 bytes compressed to 2851746 bytes.
Time 2745.04 sec, used 1794596602 bytes of memory


E:\O\PAQ\paq8px_v5>pause

[Matt Mahoney]

Big gains on nci and reymont. Now #1.
http://mattmahoney.net/dc/silesia.html
Haven't tested decompression yet. Compression took about 8 hours running overnight.

Edit: decompression verified OK.

 1,958,431 dickens.paq8pxd
10,230,693 mozilla.paq8pxd
 2,060,447 mr.paq8pxd
   845,771 nci.paq8pxd
 1,418,268 ooffice.paq8pxd
 2,069,961 osdb.paq8pxd
   792,299 reymont.paq8pxd
 2,851,746 samba.paq8pxd
 3,776,327 sao.paq8pxd
 4,907,348 webster.paq8pxd
 3,587,975 x-ray.paq8pxd
   264,419 xml.paq8pxd
 34,763,685 bytes

[Matt Mahoney]

Results on enwik8. http://mattmahoney.net/dc/text.html#1350
Takes about 3 hours to compress or decompress.

[kaitz]

"Fast Autocorrelated Context Models for Data Compression"
arxiv.org/pdf/1305.5486.pdf

[kaitz]

Work in progress.
Image model uses some parts from Tangelo. Is ca 25% faster and about same compression level.
Text comression is between v4 and v5.

E:\O\PAQ\paq8px_v7>paq8pxd_v7 -8 big_building.pgm
Creating archive big_building.pgm.paq8pxd with 1 file(s)...


File list (27 bytes)
Compressed from 27 to 29 bytes.


1/1  Filename: big_building.pgm (39053009 bytes)
Block segmentation:
 0           | hdr       |        17 bytes [0 - 16]
 1           | 8b-image  |  39052992 bytes [17 - 39053008] (width: 7216)
Compressed from 39053009 to 16095182 bytes.


Total 39053009 bytes compressed to 16095221 bytes.
Time 910.16 sec, used 1642291355 bytes of memory


E:\O\PAQ\paq8px_v7>paq8pxd_v5 -8 big_building.pgm
Creating archive big_building.pgm.paq8pxd with 1 file(s)...


File list (27 bytes)
Compressed from 27 to 29 bytes.


1/1  Filename: big_building.pgm (39053009 bytes)
Block segmentation:
 0           | hdr       |        17 bytes [0 - 16]
 1           | 8b-image  |  39052992 bytes [17 - 39053008] (width: 7216)
Compressed from 39053009 to 16112333 bytes.


Total 39053009 bytes compressed to 16112372 bytes.
Time 1290.55 sec, used 1633888539 bytes of memory

E:\O\PAQ\paq8px_v7>paq8pxd_v7 -8 nci
Creating archive nci.paq8pxd with 1 file(s)...


File list (14 bytes)
Compressed from 14 to 16 bytes.


1/1  Filename: nci (33553445 bytes)
Block segmentation:
 0           | text      |  33553445 bytes [0 - 33553444] (wrt: 30692222)
Compressed from 33553445 to 849020 bytes.


Total 33553445 bytes compressed to 849046 bytes.
Time 3356.14 sec, used 1641812872 bytes of memory


E:\O\PAQ\paq8px_v7>paq8pxd_v7 -8 enwik8
Creating archive enwik8.paq8pxd with 1 file(s)...


File list (18 bytes)
Compressed from 18 to 18 bytes.


1/1  Filename: enwik8 (100000000 bytes)
Block segmentation:
 0           | utf-8     | 100000000 bytes [0 - 99999999] (wrt: 61756014)
Compressed from 100000000 to 16665626 bytes.


Total 100000000 bytes compressed to 16665654 bytes.
Time 9443.38 sec, used 1641812869 bytes of memory

[kaitz]

New:
changes in wrt, use 0-9 ind dict if count is larger then a-zA-Z
8-bit image model changes
base64 changes
contextmap from Tangelo
fixes in DMC model
cleanup of unused varibles
fixes in wordmodel
etc.

Will test enwik9, and report when its done.
Its better on most cases then paq8pxd_v4

Update:

paq8pxd_v7 -8 enwik8 
16606773 bytes. Time 9445.34 sec, used 1633432453 bytes of memory

paq8pxd_v7 -8 enwik9Creating archive enwik9.paq8pxd7 with 1 file(s)...


File list (19 bytes)
Compressed from 19 to 17 bytes.


1/1  Filename: enwik9 (1000000000 bytes)
Block segmentation:
 0           | utf-8     |1000000000 bytes [0 - 999999999] (wrt: 625961246)
Compressed from 1000000000 to 134791881 bytes.


Total 1000000000 bytes compressed to 134791909 bytes.
Time 93751.00 sec, used 1633432453 bytes of memory

Edit:07.02.2014
paq8pxd_v7 -8

 
dicke 1958670
mozil 10225591
mr    2060950
nci   842128
ooff  1418474
osdb  2070242
reym  792311
samba 2852966
sao   3776512
webst 4903850
x-ray 3588190
xml   264643
      34754527

[Matt Mahoney]

I posted your results. http://mattmahoney.net/dc/text.html#1348

[TDCorbin]

I've been having problems compressing files larger than 2^31 - 1 bytes. For the sake of completeness, I'm using GNU/Linux 3.11.2-201.x86_64.

Although you're splitting the datum into 2GB blocks, there are still a few subtle flaws in the code (that I can tell anyway). Specifically, during the "Detector" phase (according to your comment headers), there are many instances of longs, i.e., the length of the file, being downcasted into integers. This obviously causes problems when the length of the file is greater than 2^31 - 1, e.g., when you're looping over the data using an int as opposed to a long, or when the downcasting affects the signed-ness of the int.

detect/6 and compressRecursive/7 are the only two functions I focused on, but I'll infer the same holds elsewhere.

May somebody confirm this?

Edit: Quick Update.
Compressing a random 5GB XML file appears to be "fine". But this may be attributed to the downcasting leaving the sign bit unscathed.

If this isn't easily confirmable, I'll upload a sample document somewhere.

Thanks.

[Stephan Busch]

I can confirm that paq8pd_v7 contain bus. It doesn't compress APP corpus of Squeezechart (Out of memory error after compressing half of the input and 7GB of Ram were available). There were further errors with some of the other corpora.

[kaitz]

I want to write AVX2 supported train and dot_product. For some reason it does not work.
Can someone help to figure out what am i doing wrong. This is my first attempt at all.

static int dot_product (const short* const t, const short* const w, int n) {
  assert(n == ((n + 15) & -16));
  __m256i sum = _mm256_setzero_si256 ();
  while ((n -= 16) >= 0) { // Each loop sums 16products
    __m256i tmp = _mm256_madd_epi16 (*(__m256i *) &t[n], *(__m256i *) &w[n]); // t[n] * w[n] + t[n+1] * w[n+1]
    tmp = _mm256_srai_epi32 (tmp, 8); //                                        (t[n] * w[n] + t[n+1] * w[n+1]) >> 8
    sum = _mm256_add_epi32 (sum, tmp); //                                sum += (t[n] * w[n] + t[n+1] * w[n+1]) >> 8
  }
  
  sum = _mm256_add_epi32 (sum, _mm256_srli_si256 (sum, 16));
  
  sum = _mm256_add_epi32 (sum, _mm256_srli_si256 (sum, 8)); // Add eight sums together ...
  sum = _mm256_add_epi32 (sum, _mm256_srli_si256 (sum, 4));
  __m128i low = _mm256_castsi256_si128(sum);
  return _mm_cvtsi128_si32 (low); //                     ...  and scale back to integer
}


static void train (const short* const t, short* const w, int n, const int e) {
  assert(n == ((n + 15) & -16));
  if (e) {
    const __m256i one = _mm256_set1_epi16 (1);
    const __m256i err = _mm256_set1_epi16 (short(e));
    while ((n -= 16) >= 0) { // Each iteration adjusts 16 weights
      __m256i tmp = _mm256_adds_epi16 (*(__m256i *) &t[n], *(__m256i *) &t[n]); // t[n] * 2
      tmp = _mm256_mulhi_epi16 (tmp, err); //                                     (t[n] * 2 * err) >> 16
      tmp = _mm256_adds_epi16 (tmp, one); //                                     ((t[n] * 2 * err) >> 16) + 1
      tmp = _mm256_srai_epi16 (tmp, 1); //                                      (((t[n] * 2 * err) >> 16) + 1) >> 1
      tmp = _mm256_adds_epi16 (tmp, *(__m256i *) &w[n]); //                    ((((t[n] * 2 * err) >> 16) + 1) >> 1) + w[n]
      *(__m256i *) &w[n] = tmp; //                                          save the new eight weights, bounded to +- 32K
    }
  }
}

[Matt Mahoney]

The original PAQ used a mixer size that was rounded up to a multiple of 8, which was enough for SSE2. But I guess you checked that.

[nburns]

I've been having problems compressing files larger than 2^31 - 1 bytes. For the sake of completeness, I'm using GNU/Linux 3.11.2-201.x86_64.

That just happens to be an interesting number. It's the largest Mersenne prime that you can represent with a 32-bit integer.

[kaitz]

My AVX2 attempt seems to be correct. Decompresses OK. Problem was that mixer tx and wx must be aligned to 32 byte.

[kaitz]

• base64 uses memory for encode/decode about 30% faster
• large file support (over 2GB)
• indirect model changes
• wordmodel changes
• file segmentation data is written uncompressed (at file end)
• sparseModel1 changes
• no .pbm .pgm .ppm .rgb .tga image detection
• separate encoder decode/encode

Included avx2 and sse2 versions are not compatible. Was not able to find out why.

Edit: removed attachment

[comp1]

• base64 uses memory for encode/decode about 30% faster
• large file support (over 2GB)
• indirect model changes
• wordmodel changes
• file segmentation data is written uncompressed (at file end)
• sparseModel1 changes
• no .pbm .pgm .ppm .rgb .tga image detection
• separate encoder decode/encode

Included avx2 and sse2 versions are not compatible. Was not able to find out why.

Fantastic! Time to do some testing!

[Matt Mahoney]

Testing under Wine 1.6, Ubuntu 64 bit: paq8pxd_v8sse2.exe with no arguments prints a help message, then anything I type in the shell window afterward is no longer echoed to the screen. When trying to compress, I get error: tmpfile: permission denied. (Old problem I should have fixed, I know). Tried to compile but g++ 4.8.2 says _atoi64() is undefined. AVX2 version gives an illegal instruction error as expected a non-AVX2 processor.

[kaitz]

Tried to compile but g++ 4.8.2 says _atoi64() is undefined.

source code line 5539 should be

#if defined(WINDOWS) || defined(_MSC_VER)
    #define atoll(S) _atoi64(S)
    #endif

Only source.

[Matt Mahoney]

Source compiles OK with g++ in both Windows and Linux (with lots of warnings). Testing now...

[kaitz]

I am wondering. uses paq9a HT.

842468 bytes A10.jpg
              Csize  Time  Mem
paq8pxd_v7 -8 636600 18.25 1861096056 
paq8pxd_v8 -8 636568 18.66 1861101420
paq8pxd_v8 -8 636634 16.28 1835935676 (different hashtable)


2599224 bytes DSCN2691.JPG
              Csize   Time  Mem
paq8pxd_v7 -8 1861453 67.84 1861096051
paq8pxd_v8 -8 1861474 67.34 1861101415
paq8pxd_v8 -8 1861474 58.52 1835935671 (different hashtable)


http://compression.ca/act/act-jpeg.html
1114198 bytes DSCN3974.jpg
              Csize  Time  Mem
paq8pxd_v7 -8 826086 24.36 1861096051
paq8pxd_v8 -8 826108 25.74 1861101415
paq8pxd_v8 -8 826106 21.13 1835935671 (different hashtable)

[Stephan Busch]

Could anyone please post compiled binaries?

[kaitz]

It seems that there is a serious bug that prevents last version to work properly. It compresses JPEG file but at the beginning of another program crashes. Like two files in tar container. Crashes on beginning of second jpeg file. Also, it seems to me that more than 2GB can not be compressed with this version. pos (int) in buf is not wrapped and has probably some side effects and pos is used on some models. In mode -0 i had no problems with large files (to test filtering).

[Matt Mahoney]

Silesia results. Decompression not tested yet. Compression took about 17 hours on a 2 GHz T3200. http://mattmahoney.net/dc/silesia.html

I am still testing LTCB. paq8pxd_v8 -8 enwik8 decompressed OK, 16,607,759. enwik9 just finished compressing in 17 hours on a 2.66 GHz M620 to 134,781,085. I will test decompression before posting.

[Skymmer]

It seems that there is a serious bug that prevents last version to work properly. It compresses JPEG file but at the beginning of another program crashes. Like two files in tar container. Crashes on beginning of second jpeg file. Also, it seems to me that more than 2GB can not be compressed with this version. pos (int) in buf is not wrapped and has probably some side effects and pos is used on some models. In mode -0 i had no problems with large files (to test filtering).

v8 immediately crashes on one of my WAV test files. Seems works on other files where default model used but didnt tested too much.

[kaitz]

I think i figured out jpeg problem. Line 2744 should be

 jpeg=next_jpeg=0;

Edit:

v8 immediately crashes on one of my WAV test files. Seems works on other files where default model used but didnt tested too much.

Inf wavModel Line 3166 should be

if (!blpos && bpos==1) {

[Matt Mahoney]

paq8pxd_v8 -8 decompression failed on silesia/mozilla. It was still running after 14 hours indicating 326% done so I killed it. The output file was over 167 MB. It differs starting at offset 16003654 with apparently random output, followed by all zeros starting at 21105608 and continuing for the rest of the file. dickens compared OK. I did not test the other silesia files. enwik9 compared OK.