Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!crdgw1!uunet!mcsun!ukc!stl!concurrent!info
From: info@concurrent.co.uk (Information Server)
Newsgroups: comp.compression
Subject: Re: Markov compressor availability? (was SAKDC availability?)
Keywords: Markov sakdc data compression algorithm ppm ppmc
Message-ID: <1027@sl10c.concurrent.co.uk>
Date: 4 Jun 91 15:32:12 GMT
References: <817@spam.ua.oz>
Reply-To: jrc@concurrent.co.uk (John Connett)
Organization: Concurrent Computer Corp (ESDG), Slough, U.K.
Lines: 23

In article <817@spam.ua.oz> ross@spam.ua.oz.au (Ross Williams) writes:
[...]
    SAKDC is at this stage not very accessible or portable.
[...]
    As  far  as I  am  aware,  SAKDC gives  the  best  compression of  ANY
    algorithm in existence (if you can  do better - scream out!). Evidence
    for this can be  found in my book and the Bell book.  Table B-1 of the
    Bell  book gives  the compression  performance on  the Calgary  (Bell)
    corpus for 18 algorithms. The best  compression is given by the Markov
    algorithms of  which PPMC is the  best, yielding 2.48 bits  per symbol
    (the next closest is  2.74). From the O20000 column of  Table 39 of my
    book (and omitting the files  paper3..paper6 as Bell Cleary and Witten
    did)  SAKDC yielded  2.464 bits  per symbol.  This was  using a  large
    amount of  memory. For  a small  amount of  memory (200  nodes), SAKDC
    yields about 18% (absolute) better  compression than PPMC (3.344b/s vs
    4.784b/s (includes paper3-paper6)).
[...]

Are there any freely available implementations of PPM, PPMC or any other
Markov algorithm compressors?

John Connett
jrc@concurrent.co.uk