Newsgroups: comp.compression
Path: utzoo!utgpu!watserv1!watmath!looking!brad
From: brad@looking.on.ca (Brad Templeton)
Subject: Re: Is there better lossless compression than LZW?
Organization: Looking Glass Software Ltd.
Date: Sun, 02 Jun 91 21:31:16 GMT
Message-ID: <1991Jun02.213116.3069@looking.on.ca>
References: <1991May29.155853.13716@looking.on.ca> <1991Jun2.085929.12871@unislc.uucp>

I investigated such ideas and I think there are a few problems.

First of all, to avoid confusion of terms, LZ compressions refers to two
algorithms.   One is a general algorithm where you have backpointers into
the previous text.  The whole of the previous text (or the last N bytes)
is your dictionary, so there is not a question of "adapting faster" in
such an algorithm.   THe laster LZ algorithm, and its descendants, such
as LZW (a variant designed for speed) M-W and All-Prefix coding do have
"how fast they adapt" as an important factor.

Your algorithm is similar to LZ1, but instead of backpointers you use
tags.   Tag a string when it goes out, and then refer to it when you need to.
Problem is that tag+referral can be larger than just a backpointer referral.
How long are the end-token and start-token codes?   Just as important, since
they exist in the same token-space as regular entries in the alphabet, how
much longer do they make all the other codes.
(ie. if you use 1 bit for a tag code, you add 1 bit to all the regular
tokens in the alphabet)

It's tricky.  I'm not saying it's impossible, but I would like to see more
evidence that it can be done.

Remember as well that you have to deal with the fact that a new entry can
often consists of the tail of one reference and the head of another reference.

ie. if you have two dictionary entries "the boy " and "who fell" how do you
tag the string "boy who" if it first appears in the transmission of the
two entries together?   How do you do this without using space?
-- 
Brad Templeton, ClariNet Communications Corp. -- Waterloo, Ontario 519/884-7473