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: Fri, 24 May 91 18:49:23 GMT
Message-ID: <1991May24.184923.6648@looking.on.ca>
References: <2722@pdxgate.UUCP> <6200@ns-mx.uiowa.edu>

In article <6200@ns-mx.uiowa.edu> jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) writes:
>But by far the best lossless compression is achieved by arithmetic codes,
>especially when used with mulitple state source models.  Arithmetic codes
>can code individual source characters in fractional bits (something that
>a Huffman code can't do), but they are generally slow, and when used with
>multiple state source models, they get quite big as well.  See:

I don't know about "but by far the best."   Arithmetic codes give you
one half bit per token better compression, which on 0 order byte models
is around 10% better, and on 2nd or 3rd order models such as the ones you
describe, this drops just just a few percent.   Not that it isn't good to
get every drop out, but sometimes the speed penalty isn't worth it.

So on to the related question, what are the best (non-patented) algorithms
for fast implementation of arithmetic coding, with alphabet sizes in the
300 token range?


Note that good application of LZ1 algorithms (the ones used in PKZIP, ARJ
and LHARC are such) can give, in reasonable time, compression levels
superior to LZW or AP and not far off C-W and high order multiple state
or markov models.

And of course, compressors designed for the general class of data can often
do better than such compressors.
-- 
Brad Templeton, ClariNet Communications Corp. -- Waterloo, Ontario 519/884-7473