[Haskell-cafe] Toy compression algorithms

Andrew Coppin andrewcoppin at btinternet.com
Wed Jul 11 14:57:19 EDT 2007

ajb at spamcop.net wrote:
> G'day all.
> Andrew Coppin wrote:
>>> Actually, LZW works surprisingly well for such a trivial little
>>> algorithm... When you compare it to the complexity of an arithmetic
>>> coder driven by a high-order adaptive PPM model (theoretically the best
>>> general-purpose algorithm that exists), it's amazing that anything so
>>> simple as LZW should work at all!
> Not really.  LZW is basically PPM with a static (and flat!) frequency
> prediction model.  The contexts are build in a very similar way.

Yes - but making it use a non-flat model opens a whole Pandora's Box of 
fiddly programming. ;-)

(It's not "hard" as such - just frustratingly fiddly to get correct...)

More information about the Haskell-Cafe mailing list