<< ctxmodel.net

> PPM with optimal parsing? Do you have some info?

Actually its useful for any CM, but I never heard of an actual implementation. Well, its complex and slow, so that's why.

The same thing can be also mentioned as delayed updates or lazy updates or something. Also I think that "order estimation" techniques (LOE etc) from PPM are related.

The idea is that, for example, if the text is generated as a sequence of words (like it usually is), then the best choice would be to parse it into the same sequence of words for modelling. And its actually possible, but usually its not known at the time of processing the symbol, which context fits it best (and there might be several too) - that only becomes clear after gathering more statistics.

Well, its basically the same as the LZ optimal parsing, but with CM its also possible not only to choose whether to include or not the symbol into the "match", but also to "partially include" it, with a fine control of a size of this "part" too. Here I mean different update parameters, of course.

So its one of these advanced techniques which nobody uses and even researches because they could only be useful for something like paq8, and never for fast compressors.


2010-11-30 01:13:46 pmcontext       >
Hi shelwien,
On this site can you also add your description of ppm algorithm,
and its implementation details. may be explaining ppmd/ppms/ppmy
when you have time. it helps a lot in understanding the algorithm clearly. somthings like suballocator, exclusion , information inheritence, binary context , non-masked , masked , see , sse and anything else. it can be like a book about ppm and all your ideas on it.
2010-11-30 17:23:49 Shelwien        >
I think its unlikely, unless I'd really write a new PPM coder for some reason.
ppmd/ppms are Shkarin's works, and in fact are described in
his papers, did you read these?
There're some in /PPMd here.
Also I recommend Witten's "Modeling for text compression".

And ppmy/ash are bytewise CM, not PPM.
2013-08-01 07:25:21                 >
2013-10-04 03:39:58                 >
2014-11-26 22:49:40                 >
2015-01-11 22:53:58                 >

Write a comment:

Name: