Disclaimer
Copyright (c) Arturo San Emeterio Campos 1999. All rights reserved. Permission is granted to make verbatim copies of this document for private use only.
 

Download
Download the whole article zipped, with the figures also.
 

Table of contents

Introduction
In this article it's presented all my research till now in lzp. Some standard models are presented and briefly analyzed. Also improvements for any kind of lzp model are presented: deterministic contexts and optimal contexts. The idea of using more than one offset is seen too, though it's not very explored. Enough results are given, so you can choose the more appropriate model for your compressor. This article is mainly focused on models, encoders are briefly discussed too.

This article assumes knowledge of lzp, different implementations of it, and ppm. (at least the theory behind it)

If the tables from this article aren't properly displayed, I could send you or upload to my page the tables in plain text version. Anyway I encourage to view this article in Netscape, instead of Internet Explorer. 800x600 is recommended.
 

Lz
We can classify the compression of text in two big worlds, Markov models and Lz dictionary compressors, both of them do the same: assign less bits to more common events; thus some researchers explained Lz schemes thru Markov eyes. Both schemes are different: one provides high compression, the other one high speed. The question raised in the brains of some researchers.

Time passed and Ross Williams did his approach with lzrw, the idea in theory worked, also lzrw became one of the fastest Lz compressor, though it did not had impressive compression ratios. But it was the first step to the hybrid between contexts coders and Lz.

Charles Bloom did the next step: Lzp. Which seems to be the best approach of Markov and Lz, high speed and high compression, which can be tuned in order to fit your needs. His paper presented lzp and the most important implementations of it. However one can miss an explanation of what's happening behind it or more results. Most of the implementations had in mind speed, however some of them had a very low memory requirements, and one was better than some ppm variants. (but it uses ppmc as a coder for literals, thus dramatically reducing the speed of the whole compressor)

Peter Fenwick did some research on it, but he focused it on symbol ranking.

And then here it comes my work, with the hope that it can further develop lzp.
 

Offset probability
Can we see parsing as a markov model? yes, we can, but this is not the point of this article, (see articles from Ross Williams) let's analyze  them. Let's say we are under an lz77 like model, and we have parsed "baa", this will produce the following phrases with the following probabilities:

Note that lz77 has the suffix property: The suffixes of a phrase in a given dictionary are phrases of the dictionary too. The entropy (under a simple order-0 model) of every phrase is 2.32 bits, and effectively, we can't represent it with less than 2.3 bits, well, in fact we'll need 2 bits for the offset and two bits more for the length of the phrase (which is more than we should assign, one can clearly see that this model isn't the best one), even we could assign a value to every phrase, and thus coding them with only 3 bits.

Phrase Probability "a" 1/5 "b"  1/5 "aa"  1/5 "ba" 1/5 "baa" 1/5

We can see that in a Lz like compressor where all the events have a flat probability (the same probability for all the symbols) the only way to improve the probability of a given symbols (and thus needing less bits to encode it) is having less events to encode. I.e.: If we have a dictionary with 4096 phrases defined on it, we'll need at least ent ( 1/4096 ) = 12 bits but if we reduce the number of phrases down to 1024 phrases, we'll need ent ( 1/1024 ) = 10 bits, and with even less phrases, let's say 200, we'll need ent ( 1/200 ) = 7.643 bits. (ent() means the entropy of a symbol)

A standard version of Lzp solves this problem assigning a probability of 1/2 to every offset from a given context (the other 1/2 is reserved to tell the decompressor that this was a failed match), so it needs ent ( 1/2 ) = 1 bit. In some cases lzp may even assign a probability of 1/1 to a given symbol, but then in the case of no match we  have to encode a 0 match length and a literal. (which may result in degradation of the total compression)
 

Standard Lzp
We should define a standard implementation of lzp. The pseudo code of it will look like the following:

• Loop. For all the symbols in the input.
• Pointer = get_pointer (current_context )
• Pointer = 0?
• Yes
• Encode symbol.
• Put_pointer ( pointer to input )
• Pointer to input ++
• No
• Length = Compare_symbols ( pointer, pointer to input )
• Length = 0 ?
• Yes
• Encode negative flag.
• Encode symbol.
• Put_pointer ( pointer to input )
• Pointer to input ++
• No
• Encode positive flag.
• Encode length
• Put_pointer ( pointer to input )
• Pointer to input = pointer to input + length

Orders
If we want to do good models, we have to know how many of them can we use, in this I'll discuss and analyze different orders (the number of symbols which are used as context). We can use different orders, every of them will give different results, but first we have to define a set of standard orders. The symbol it's assumed to be a byte.

• O1 uses order 1 with direct addressing in a table with 256 symbols.
• O2 uses order 2 with direct addressing in a table with 65535 symbols.
• O2h uses order 2 with hashing in a table with 4096 entries. The hash key used is the following: H =  ( Context ^ ( Context >> 4 ) ^ 0FFFh
• O2hc the same as the above but with context confirmation.
• O3, the order-2 is used with direct addressing in a hash table with 2^16 entries. Every entry contain a pointer to a linked lists with all the contexts which had the same order-2 context (due to direct addressing) so we only need to save there the order-3 byte and a pointer to the data.
• O3h, hashing is used in a table with 2^16 entries. The following hash key is used: H =  ( B1 ^ ( B2 << 7 ) ^ ( B3 << 11 ) )  &  0FFFFh
• O3hc, the same as above but with context confirmation.
• O4, the same as O3 but storing the order-4-3 in the linked lists.
• O5, again the same storing the order-5-4-3.
• O6, this time order-6-5-4-3
• O7, and now thing change, this time we use two linked lists, the first having the order-4-3 and the second the order-7-6-5. (the main hash table contains order-2 with direct addressing)
• O8, the same but storing order-8-7-6-5.

Result of orders
Now that we have defined different contexts, let's see how they perform.
 

Predictions % Bad Good % Matched % O1 544434 87 463592 80842 15 162800 26 O2 432742 69 321783 110959 26 301605 48 O2h 446314 71 340311 106003 24 284535 45 O2hc 401479 64 298006 103473 26 281646 45 O3 360188 57 242612 117576 33 359255 57 O3h 373524 60 253083 120441 32 361928 58 O3hc 331039 53 220359 110680 33 332299 53 O4 314976 50 198489 116487 37 380558 61 O5 275372 44 168923 106449 39 362334 58 O6 235102 38 141649 93453 40 328266 52 O7 166140 27 97888 68252 41 251772 40 O8 161348 26 95427 65921 41 244967 39

1- O1 2 - O2 3 - O2h 4 - O2hc 5 - O3 6 - O3h 7 - O3hc 8 - O4 9 - O5 10 - O6 11 - O7 12 - O8 Numbers for graphics.

A little explanation of this table: Results come from book2. A bad prediction is one which produce no match (0 match length) a good prediction is one which is not bad. (at the right the % of the good predictions, I mean (good/(good+bad))*100) The column "predictions" holds the number of times that under a given contexts we had an offset (and then we have to check for match). At his right there's the %, in respect with the file size of book2. (626,490 bytes) In the column "matched" you have the total bytes that could be matched. (the sum of all match lengths) And at its right the % of bytes matched on all the file. ((matched/file_size)*100)

Let's see some graphics:
 

Here you can see the % of predictions ((predictions/file_length)*100)  As you can see the higher the order, the less predictions, this is due to the zero frequency problem (when we haven't seen any context of the same kind yet). Have in mind that all those tables don't take in account only different orders, but also different ways of accessing them. (I.e.: O2, O2h, and O2hc, all of them use the same order, but the way an offset is stored changes)

This is the % of good predictions ((good_predictions/total_predictions)*100)  Obviously also, the higher the order, the more reliable the predictions are. Higher orders than 8 were not explored, it's a know fact that orders above 8 don't make any real improvement in text compression. (and the resources for accessing them will be higher and it will be far slower too)

That graphic represents the % of matched bytes (as defined above) ((matched_bytes/file_length)*100)

Conclusions: Low orders produce a lot of wrong predictions, and higher orders are very effected by the zero frequency problem. The best trade off (at least for book2) between memory/speed/compression seems to be o4, however order-5 seems good too.

With all this information you should be able to choose the order which best suits your needs.
 

Deterministic contexts and optimal contexts
Some time ago (I mean around June, 1999), in private communication with Charles Bloom, he explained me what deterministic contexts are, they opened a new set of models, which where not done yet. So I started to work on it. Here I present all my approaches.

But first let's define what is a deterministic context: A deterministic context is a context which has not produced any bad prediction. (a bad prediction is defined above)

My first scheme to handle deterministic contexts was only based on this information, however I developed some improved versions of it, which don't use deterministic contexts, so a new term should be introduced. (and I base this in the fact that for lzp they are better than deterministic contexts)

An optimal contexts is a contexts which has produced more good predictions than bad predictions.

Optimal contexts will only be implemented in lzp, at least in this article, however it's probable that they'll work for ppm too.

Before starting to explain the different models, you must know this: a given contexts (let's say "th") can have different offsets which provide different matches. (the context "th" can predict "e ", "ere ", "us ", "an ", "ink "...) the goal of the schemes which I'll present now, is to get the best of them.
 

Implementing deterministic contexts and optimal contexts
Once we know that there are some offsets which work better than others, how can we build our model so it captures it?
Let's think about some facts of lzp: We can't change when a offset is inserted for first time (mainly because we don't have any information about it, and also because we need to fill the table) Then we only have two more cases dealing with offset in a given context: when it's updated and deleted.

1. Updating. For implementing deterministic contexts and optimal contexts, we'll never update offsets. (in a standard versions of lzp as defined before, the offset of a given context is always updated)
2. Deleting. We delete an offset when it has produced a wrong match, this leads the model to adapt to the incoming data, however we could define this as the greedy approach. So here it is where we can capture the best offsets.

1. No deterministic context. (you may choose what value represent them)
2. Deterministic contexts.

• When an offset is written in a given contexts we assign it a no deterministic context flag. (let it prove that it is, this improved compression over treating a new offset as a deterministic context one)
• When an offset produces a good prediction we assign it a deterministic context flag.
• When an offset produces a bad prediction, we check the flag:
• If it's no deterministic context. In this case we update the offset, I mean putting the offset to the current position to the input and a no deterministic context flag in the context.
• If it's deterministic context. We don't update the offset, but change the flag to no deterministic context flag, thus allowing the model to adapt to the incoming input. (else it will keep forever the first deterministic context seen, which is not a good idea)

For optimal contexts there's a main scheme, scheme 1, and then variations of the same, which proved to not be better. (but are presented to show you different ideas)

Optimal contexts scheme 1:

• A given contexts has two values: good_predictions and bad_predictions. Both of them are bytes, I doubt that a given context can produce more than 255 matches without being discarded. (but this should be checked)
• When a new offset (or an updated one) is inserted, both of them are initalized to 0.
• Whenever a good prediction occurs, its variable is incremented. (+1)
• Whenever a bad prediction occurs, its variable is incremented. (bad_predictions+1) And then we check:
• If the number of bad predictions is above than good ones, then the offset is updated.
• If the number of bad predictions is equal or below than the good predictions, nothing is done.

Optimal contexts scheme 2:

• Same as optimal contexts scheme 1, but in this case we update if the number of bad predictions is above or equal to the number of good predictions.

• Same as optimal contexts scheme 2, the difference is that good predictions are initalized to 1.

• Same as optimal contexts scheme 2, good predictions are initialized to 2.

Also there's another question: Are optimal contexts optimal? While this may seem a paradox, this is a serious question. Let's say we have a text like "the ... there ... the...there ... the..." (where "..." means that there is other text) Here we can see that the scheme for optimal contexts does his job, to not discard an optimal context, "th"->"e " (where "th" is the context and "e " the match that it can produce) but while it's an optimal context, it doesn't produce more bytes matches than "th"->"ere " can produce (twice the bytes matched) so the offset "th"->"ere " is optimal while "th"->"e " is not (even if it's an optimal context).

However now the question arises: How to keep track of the bytes matched from offsets in a given context which aren't currently used? This would need to store more than one pointer, and check them. Probably this scheme will not produce a lot better results, and I'm sure that it will be more slower. Another solution could be to save the number of matched bytes in a given context, and also assign to the literals a given length, and then do the same as in optimal contexts, however this remains unexplored. Anyway it doesn't seem possible to do this without needing more speed and memory than optimal contexts do.
 

Results for updating schemes
In all this examples I only care about the model and the probabilities which it produces, while it's not a ppm model which directly has the probability of a symbol, one can at least know how a given coder will perform given the probability distribution.
 

 

Models Bpb Improvement 1- Default 3,659 ... 2- Deterministic contexts 3,552  0,107 3- Optimal contexts s1 3,492  0,167 4- Optimal contexts s2 3,528  0,131 5- Optimal contexts s3 3,512  0,147 6- Optimal contexts s4 3,533  0,126	Bpb of the different models
Bpb of encoded literals	Bpb of encoded match lengths

Note that for implementing this, we have to save in every context one byte (or whatever we use for match lengths) which is the last match length.

Here there are two graphics, the first is the match lengths outputted (at its done in an standard lzp model) and the second is the match lengths which were first differential coded. (note that both of them can be coded with the same routines, so this doesn't add complexity, and it just takes a little bit of time)
 

Note that the scale is logarithmic adjusted, to make it fit in the pic.We can learn more seeing the output:
(click here to go to the end of this table and read conclusions) All the results come from book2.
 
 

Match lenghts

Differential coded

0: 0 1: 52514 2: 24379 3: 13609 4: 8450 5: 5803 6: 4227 7: 3075 8: 2148 9: 1328 10: 952 11: 762 12: 639 13: 478 14: 325 15: 227 16: 232 17: 162 18: 118 19: 115 20: 110 21: 89 22: 83 23: 56 24: 44 25: 39 26: 49 27: 28 28: 41 29: 19 30: 19 31: 14 32: 11 33: 15 34: 13 35: 12 36: 13 37: 10 38: 10 39: 12 40: 9 41: 14 42: 7 43: 5 44: 2 45: 7 46: 9 47: 6 48: 6 49: 7 50: 8 51: 5 52: 5 53: 6 54: 2 55: 2 56: 5 57: 7 58: 2 59: 4 60: 5 61: 4 62: 6 63: 2 64: 3 65: 0 66: 2 67: 1 68: 4 69: 2 70: 1 71: 2 72: 4 73: 0 74: 3 75: 6 76: 1 77: 0 78: 1 79: 2 80: 3 81: 1 82: 2 83: 1 84: 0 85: 0 86: 2 87: 2 88: 4 89: 1 90: 1 91: 3 92: 2 93: 0 94: 8 95: 3 96: 0 97: 0 98: 1 99: 1 100: 0 101: 1 102: 1 103: 0 104: 1 105: 1 106: 0 107: 0 108: 0 109: 0 110: 2 111: 0 112: 0 113: 0 114: 0 115: 0 116: 0 117: 0 118: 1 119: 0 120: 0 121: 0 122: 0 123: 0 124: 0 125: 0 126: 0 127: 0 128: 0 129: 0 130: 0 131: 0 132: 0 133: 1 134: 1 135: 0 136: 0 137: 0 138: 0 139: 0 140: 0 141: 0 142: 0 143: 0 144: 0 145: 0 146: 0 147: 0 148: 0 149: 0 150: 0 151: 0 152: 0 153: 0 154: 0 155: 0 156: 0 157: 0 158: 0 159: 0 160: 0 161: 0 162: 0 163: 0 164: 0 165: 0 166: 0 167: 0 168: 0 169: 0 170: 0 171: 0 172: 0 173: 0 174: 0 175: 0 176: 0 177: 0 178: 0 179: 0 180: 0 181: 0 182: 0 183: 0 184: 0 185: 0 186: 0 187: 0 188: 0 189: 0 190: 0 191: 0 192: 0 193: 0 194: 0 195: 0 196: 0 197: 0 198: 0 199: 0 200: 0 201: 0 202: 0 203: 0 204: 0 205: 0 206: 0 207: 0 208: 0 209: 0 210: 0 211: 0 212: 0 213: 0 214: 0 215: 0 216: 0 217: 0 218: 0 219: 0 220: 0 221: 0 222: 0 223: 0 224: 0 225: 0 226: 0 227: 0 228: 0 229: 0 230: 0 231: 0 232: 0 233: 0 234: 0 235: 0 236: 0 237: 0 238: 0 239: 0 240: 0 241: 0 242: 0 243: 0 244: 0 245: 0 246: 0 247: 0 248: 0 249: 0 250: 0 251: 0 252: 0 253: 0 254: 0 255: 0

0: 92562 1: 10169 2: 3922 3: 2087 4: 1430 5: 882 6: 580 7: 355 8: 219 9: 172 10: 131 11: 88 12: 63 13: 52 14: 39 15: 39 16: 30 17: 19 18: 26 19: 16 20: 15 21: 11 22: 17 23: 12 24: 5 25: 18 26: 8 27: 9 28: 3 29: 2 30: 4 31: 8 32: 5 33: 7 34: 4 35: 4 36: 4 37: 2 38: 7 39: 5 40: 2 41: 3 42: 1 43: 1 44: 1 45: 1 46: 1 47: 3 48: 0 49: 1 50: 0 51: 1 52: 1 53: 1 54: 1 55: 0 56: 1 57: 1 58: 2 59: 4 60: 1 61: 1 62: 1 63: 0 64: 0 65: 1 66: 1 67: 1 68: 1 69: 1 70: 0 71: 0 72: 1 73: 0 74: 0 75: 0 76: 2 77: 0 78: 2 79: 0 80: 0 81: 0 82: 0 83: 1 84: 0 85: 0 86: 2 87: 1 88: 3 89: 1 90: 1 91: 0 92: 1 93: 1 94: 0 95: 0 96: 0 97: 0 98: 0 99: 1 100: 0 101: 0 102: 0 103: 0 104: 0 105: 0 106: 1 107: 0 108: 0 109: 0 110: 0 111: 0 112: 0 113: 0 114: 0 115: 0 116: 0 117: 0 118: 0 119: 0 120: 0 121: 0 122: 0 123: 0 124: 0 125: 0 126: 0 127: 0 128: 0 129: 0 130: 0 131: 0 132: 0 133: 0 134: 0 135: 0 136: 0 137: 0 138: 0 139: 0 140: 0 141: 0 142: 0 143: 0 144: 0 145: 0 146: 0 147: 0 148: 0 149: 0 150: 1 151: 0 152: 0 153: 0 154: 0 155: 0 156: 0 157: 0 158: 0 159: 0 160: 0 161: 0 162: 0 163: 0 164: 0 165: 1 166: 0 167: 0 168: 3 169: 1 170: 0 171: 0 172: 0 173: 0 174: 0 175: 1 176: 1 177: 0 178: 0 179: 1 180: 1 181: 0 182: 0 183: 0 184: 0 185: 1 186: 0 187: 0 188: 0 189: 2 190: 0 191: 0 192: 1 193: 0 194: 0 195: 1 196: 0 197: 2 198: 3 199: 0 200: 0 201: 2 202: 0 203: 0 204: 0 205: 0 206: 0 207: 0 208: 0 209: 1 210: 0 211: 1 212: 0 213: 2 214: 1 215: 2 216: 1 217: 1 218: 8 219: 1 220: 0 221: 2 222: 4 223: 7 224: 1 225: 3 226: 2 227: 2 228: 2 229: 2 230: 4 231: 15 232: 5 233: 7 234: 7 235: 3 236: 12 237: 6 238: 13 239: 7 240: 14 241: 16 242: 25 243: 32 244: 35 245: 45 246: 86 247: 133 248: 153 249: 263 250: 459 251: 713 252: 1219 253: 1754 254: 3301 255: 9029

One can easily see that in most of the cases the same match length occurs (a 0 differential coded byte) or little changes are done, this does not only helps to have a more skewed probabilities (where some symbols have higher probabilities than others) but also gives a very high probability to one symbol, the 0. In the default lzp, the symbol with highest probability is 1 (meaning a match length of value 1) with a probability of 52514 and we have 120441 match lengths, so its entropy is: ent ( 52514/120441 ) = 1,197 bits while when we differential code the match lengths, the symbol with highest probability, 0, has an entropy of: en ( 92562/120441) = 0,379 bits. One can clearly see why it's worth to use differential coding in match lengths, and it only adds one byte more fore every context.

I haven't checked to discard the offset if the match was below than the previous, so I don't know whatever it works better or worser. But probably it will hurt compression. (I don't think it's a good idea to discard matches)

Charles also proposed me another idea, to output the number without caring about the sign (I mean all the values are positive, so -1 becomes 1), and then a bit with the sign, this idea has not been tested, however I think that it will not get better results than the one presented by me, because positive numbers have higher probabilities, thus mixing them and output a bit more, will not be better. In case you want to implement this, I recommend first outputting the number itself, and in case that it's 0 (in most of the cases) don't output the flag after it.
 

More than one offset
It's clear than lzp in its quest for choosing only one offset, is losing the chance of more matches, so I thought, that it will be worth to analyze how lzp performs with more than one offset.

I'll present the results for lzp o2, which keeps track of 2 , 4 or 8 offsets, not the last offsets, but rather the last best offsets, a simple mtf scheme, can easily do that. This is a greedy approach too, it reads the offset 0 first and goes till the last one, whenever it gets one which gives a match, it uses it, without testing if this is the best one. (I mean the offset which gives the longest match)
 

Using one offsets (default mode)
times used % Entropy Offset 0 110959 100 0	Good 110959 25 Bad 321783 75 Predictions  432742 69 Matched 301605 48
Using two offsets
% Entropy Offset 0 93155 61 0,7235 Offset 1 60656 39 1,3424 Total 153811 18603	Good 153811 40 Bad 231997 60 Predictions 385808 62 Matched 394491 63
Using four offsets
% Entropy Offset 0 80306 40 1,3058 Offset 1 52505 26 1,9188 Offset 2 37536 19 2,403 Offset 3 28184 14 2,8164 Total 198531 46899	Good 198531 58 Bad 146518 42 Predictions 345049 55 Matched 479970 77
Using height offsets
% Entropy Offset 0 74500 31 1,6909 Offset 1 48304 20 2,316 Offset 2 34151 14 2,8163 Offset 3 25688 11 3,2271 Offset 4 19633 8 3,6149 Offset 5 15512 6 3,9548 Offset 6 12461 5 4,2708 Offset 7 10288 4 4,5472 Total 240537 81155	Good 240537