/*** * * * The following is an excerpt from an email sent to me * by Dr Peter Fenwick (of the University of Auckland, NZ) * * December 15, 1995 * ***/

I thought I should bring you up to date on my current work, which is after all derived from your LZP stuff. Basically I have extended your LZP idea, that the most recent matching context is a good predictor of the next symbol. If that first symbol is wrong, I search back at the same order for the next different symbol and offer that as a second suggestion, and so on for the 3rd, 4th, .... suggestions. When the search reaches the oldest known context, I drop down an order and repeat. If all else fails I use an MTF list as the order 0 estimator. The whole system uses the LZ-based context finder which we discussed earlier. The output for a symbol is the number of tries before the answer is correct. It has a very skew distribution and can be handled by the methods I developed for block-sorting. If you go back to Shannon's 1951 paper, your LZP method is basically his first method, while mine is his second method. The probabilities of succeeding on the 1st, 2nd, 3rd... symbol are very similar indeed to the symbol probabilities coming out of the MTF stage in block sorting. For "paper1" the corresponding probabilities are - symbol rank 0 1 2 3 4 5 6 7 block-sort 58.3% 11.3% 5.5% 3.7% 2.8% 2.3% 1.8% 1.6% "shannon" 58.8% 11.6% 5.8% 3.8% 2.7% 2.0% 1.6% 1.4%

Charles Bloom / cb at my domain

Send Me Email