/***
 *
 *
 * 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%

Back to LZP