The Lawrence algorithm (1977) is a universal binary variable-to-fixed length source coding algorithm. Here we introduce a modified version of this algorithm and investigate its asymptotic performance. For M (the segment set cardinality) large enough, we show that the rate approaches the best possible rate given the fact that the source parameter, i.e. the probability of a zero, is unknown.The asymptotic bounds show that universal variable-to-fixed length codes can have a significantly lower redundancy than universal fixed-to-variable length codes with the same number of codewords.
You can find a short one-page poster
(35K bytes) describing the problem and results or even download the
Postscript version, (Postscript,
221K bytes).
Also, the full paper
as published in
the IEEE Transactions on Information Theory, vol IT-38, no 2,
pp. 247-253, (1992) is available. This
can also be downloaded in Postscript format, (Postscript, 562K bytes).