Path: alijku02!03-newsfeed.univie.ac.at!01-newsfeed.univie.ac.at!Austria.EU.net!EU.net!newsfeed.internetmci.com!news.msfc.nasa.gov!elroy.jpl.nasa.gov!ames!waikato!auckland.ac.nz!news

From: Charles Bloom <cbloom@mail.utexas.edu>

Newsgroups: comp.compression.research

Subject: PPMZ algorithm description

Date: 6 Jun 1996 06:52:46 GMT

Organization: Clariion

Lines: 180

Sender: compression@cs.aukuni.ac.nz (comp.compression.research moderator)

Approved: compression@cs.aukuni.ac.nz

Message-ID: <4p5v7u$p7h@net.auckland.ac.nz>

Reply-To: Charles Bloom <cbloom@mail.utexas.edu>

NNTP-Posting-Host: kiwi.cs.auckland.ac.nz

X-Newsreader: NN version 6.5.0 #4 (NOV)









PPMZ v7.3 Algorithm Description

June 5 1996

by Charles Bloom

cbloom@mail.utexas.edu

 

---

 

This discussing presumes a familiarity with PPMC,PPM*,and PPMD+.

 

PPMD+ is described at:

 

        http://www.cs.waikato.ac.nz/papers/pe_for_ppm/

 

PPM* information is availabe at:

 

 

If you don't know PPMC, run for the hills.

 

---

 

PPMZ v7.3 source code, reports, and this text are available at:

 

http://wwwvms.utexas.edu/~cbloom/src/indexppm.html

 

I will soon (one week) be adding an extremely detailed statistics

report (about 100k long!!!) to this page.

 

---

 

PPMZ includes several coders, all of which are made of several

fundamental PPM components.  For example, the primary coder consists

of :

 

Order-12        PPMdet

Order-8         PPMZ

Order-5-4       PPMQ

Order-3-2-1     PPMC

Order-0-(-1)    Frequency model with full exclusion

 

There is certain confusion of nomenclature which I will try to alleviate

here:

        PPMQ,PPMZ, and PPMdet are all Escape Probability Estimation algorithms

        PPMZ v7.3 is the name of the executable

        in PPMZ v7 , PPMQ was merged into PPMZ as a special case,

                so PPMQ is actually implemented as a kind of PPMZ.

                The same was done to PPMC.

        PPMQ is also the name of the PPMQ-Second-Level-Statistics-Manager

                which is an algorithm abstraction

---

 

Now a brief (amazing) introduction to PPM statistics :

        about 50% of characters coded by PPM are coded by a

                deterministic context

        about 90% of characters coded by a deterministic context

                are successfully matched

 

deterministic contexts are those that predict only a single character.

It is extremely difficult to estimate the statistics of a deterministic

context

 

---

 

PPMdet :

 

PPMdet is an unbounded-length context coder (like PPM*) which accepts only

deterministic contexts with a count >= 2 .  This faccilitates extremely

simple data structure maintenance :

 

1. every context seen is added to an LZ77-style hash-lookup table, using

   a reverse pointer

2. each context contains a Minimum Match Length, which is initially set to

   the "Order" of the PPMdet (12 in PPMZ v7.3)

3. To match a context, the current context must match to at least MinMatchLength

   The Length of mutual match is MatchLength.

4. If the new character is successfully predicted, the character count

   is updated.

5. Otherwise the old context MinMatchLength is set to MatchLength + 1

   as is the new context.  Thus, both context minmatchlengths are

   extended so that both remain deterministic, and a longer match length

   is required.

   Perhaps adding a NumExtensions field would improve probability

   estimation.

6. Since every context is deterministic, every context has an escape count

   of 1.

7. Statistics are passed through the PPMQ-Second-Level-Statistics-Manager

        (which will be described later)

8. Matches can be very slow in PPMdet, so efficient LZ77 methods are used,

        but are still very slow, and are helped greatly by a

        preliminary pass of RunTransform

                (http://wwwvms.utexas.edu/~cbloom/src/genlib.zip)

9. If a context has not yet seen two characters, it is not coded from,

        and an escape is made without writing one

 

---

 

PPMZ :

 

PPMZ is identical to PPMC (with faster data structures inspired by LZ77)

except that deterministic contexts (contexts with one character in them

AFTER exclusion has been applied) and contexts with two characters in them

AFTER exclusion has been applied use the PPMQ-Second-Level-Statistics-Manager

to encode escapes.

 

---

 

PPMQ :

 

PPMQ is identical to PPMZ except that only deterministic contexts

use the PPMQ-Second-Level-Statistics-Manager to encode escapes.

 

---

 

PPMQ-Second-Level-Statistics-Manager : (SLSM)

 

This the core of PPMdet/Z/Q

 

The driving idea is that if a context has a PPMC-Escape-Count of

3 and a PPMC-Total-Count of 6, then it might not ACTUALLY have a

50% probability of escaping.  For example, deterministic contexts

almost always have a much lower chance of escaping than PPMC

would predict.  However, the difference is not a simple linear

scaling, and it also varies greatly from file to file.

 

LZP and ACB capture this variance in the statistics of match

lengths (trans,etc. have longer match length, paper1,etc. have

distributions which tail-off very rapidly after length=1).  SLSM

captures this information in its statistics tables.

 

when PPMC-Total-Count = 2 and PPMC-Escape-Count == 1

 

then Actual-Escape-Frequency =

 

        paper1 : 50% (same)

        trans  : 25% (2 times lower)

 

This information is tracked in the SLSM by keeping a second-level

array of statistics which translates the Stored PPMC statistics

into Actual Coding statistics.

 

This is done by create a hash value from the PPMC-Tot & Esc

counts.  This hash is used as an index into a table.  The table

contains the actual number of escapes and non-escapes done by

other contexts with the same hash (and order).  This actual number

done is used for coding.

 

All of this operationg is done through the PPMZ_Write_Escape function

call.

 

---

 

Future improvements :

 

PPMZ v7.3 consists primarily of a small modification of the work done by

Bill Teahan on PPMD+ : PPMZ handles deterministic contexts very well (almost

as well as possible).  It is projected that all the things Bill Teahan found

to improve PPMD+ will also improve PPMZ, so the following things will be

tried :

 

0. There are several constants in PPMdet.c and PPMZ.c relating to statistics

   management (i.e. DT_INC, and the DT_HASH values) which have not

   been significantly tuned.  It is estimated that severe optimal tuning

   of parameters & startup-values would result in about 0.01 bpb improvment,

   but would require too damn much work.

 

1. Recency scaling.

 

2. Switching to Random and Semi-Random models (i.e. geo, obj1)

 

3. LZP and ACB teach that string matching can occasionally be an improvement

   over PPM (because string matching inherently handles the deterministic

   problem).  Thus, adding a string-matching functionality to PPMdet, ala

   LZP, might improve performance on trans, pic, prog* etc. while hopefully

   not hurting too much on other files.

 

4. Semi-Adaptive PPMZ-Coder switching.  Version 8 of PPMZ will quickly

   detect which coder to use and then do so.



