DMC - turning it from binary PPM to binary CM

[Piotr Tarsa]

Classical Dynamic Markov Coding can be seen as a binary Prediction by Partial Matching. This is because at any given time you hold reference (call it cursor here) to one state. This state contains probability of next bit being 0 (or 1 in alternative implementations) and also pointers to next states. One cursor * one prediction pointed per cursor = 1 prediction per bit. If we change it and start a new cursor at each input byte boundary we will have multiple cursors traversing the DMC binary tree during modelling. Multiple cursors * one prediction pointed per cursor = multiple predictions per bit. After that you do Context Mixing on them. What do you think? Has anyone tried that?

[Gotty]

I tried it with 2-8 contexts when enhancing DMC in paq8px. Didn't work out. Most probably I messed it up.

There are some things to keep in mind: sometimes these cursors will unite/collide. Whenever you detect a collision, you must reset one of the cursors (to point to node 0). Since a collision may happen in the middle of a byte you'll need to wait until you reach a byte boundary to "relaunch" the cursor from node 0.
Initially, at the very beginning all the cursors are pointing to node 0, so they are in a "collision" state. You'll need to let one of them advance to the next node and reset all the others.
I also know that the more cursors you have the more often a node cloning might occur. Cloning costs memory, and DMC is already very memory hungry. For 2 cursors (2 contexts) you'll need a bit less then 2x RAM. When I realized that I gave up. You may circumvent it by using probabilistic cloning: the more the difference between the count and the threshold value is the more probably you would clone it.

I got this far.

ps. I don't consider DMC and PPM similar. However, they are related, that's true.

[Mauro Vezzosi]

Has anyone tried that?

Yes, when I tried to improve the dmcModel on paq8px: I added a second "cursor", but I don't remember if the gain was very small or if it was sometimes better and sometimes worse.

start a new cursor at each input byte boundary

(Gotty already answered to this point, however I leave what I wrote offline)
Check if there is already a cursor in the same position, because a cursor can jump to the first node of the DMC tree and if you also start a new cursor, you will have 2 identical cursor (at least in the first few bytes).
The cursors can also be used to update the model other than predict a bit.

Some my comments about DMC (so they may be wrong):
- I guess that a mixer can't learn exactly how good is a DMC model because the prediction can vary for a specific context, e.g.: if data is "abcdefgh." and we must predict ".", DMC can return a prediction based on "h" or "fgh" or "abcdefgh" even if it already saw "abcdefgh" more times.
- We can try to limit the depth of the DMC tree, it reaches (IIRC) > 200 bytewise order in (IIRC) world.txt.
- Ocamyd is an old compressor and was good at that time, it mixes 3 different DMC model + other models, I tried its update conditions on paq8px unsuccessfully.
New site: https://sites.google.com/site/ocamyd/Home
Old site: http://www.geocities.ws/ocamyd/
You'll find also DMC in Java + brief info about Suzanne Bunton (in her Ph.D. thesis she used a 256-ary alphabet DMC and merged it with PPM).
- Years ago I tried a DMC compressor where the input was an Huffman code instead of 8 bit, IIRC the result was bit worse (maybe it was buggy).
- It was demonstrate that DMC is worse than PPM because PPM is greedy and works with many contexts simultaneously and DMC only 1 per time.
- Today I found this paper: "An Exploration of Dynamic Markov Compression" https://ir.canterbury.ac.nz/bitstrea...pdf?sequence=1 with bit, character and word DMC.

[Gotty]

Extra:

Here is a paper which contains some really interesting ideas, like "getting free nodes by merging nodes", and crosslink: "before allocating a new node, we look for the closest prior history in already-allocated nodes, and if it's "close enough" (as set by a threshold), we make that the next node in our chain." [...] "This produces Markov models with both acyclic joins and repeating loops, and effectively prevents the model from growing without bound, as the model reuses nodes quite effectively (sometimes more than a 300:1 reuse!)."

However couldn't find implementation / more details / results.

http://crm114.sourceforge.net/docs/BitEntropy.txt

[Mauro Vezzosi]

However couldn't find implementation / more details / results.

Take a look here:
http://crm114.sourceforge.net/wiki/d...id=bit_entropy
https://github.com/pmundkur/libcrm11..._bit_entropy.c
( http://crm114.sourceforge.net/wiki/doku.php?id=download )