Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!ncar!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.compression
Subject: Re: Modeling vs encoding (Re: Lempel-Ziv v/s huffman encoding)
Message-ID: <2394:Apr103:30:5391@kramden.acf.nyu.edu>
Date: 1 Apr 91 03:30:53 GMT
References: <46466@ut-emx.uucp> <1991Mar31.000653.4598@zorch.SF-Bay.ORG> <12546@pt.cs.cmu.edu>
Organization: IR
Lines: 14

In article <12546@pt.cs.cmu.edu> tgl@g.gp.cs.cmu.edu (Tom Lane) writes:
  [ in an otherwise accurate summary ]
> Similarly, second-order models code each symbol using knowledge of the
> two preceding symbols, third-order models three preceding symbols, etc.
> With each order step, the amount of state needed to represent the model's
> statistics grows by a factor of N.

False. As my travesty program shows, the amount of state needed is at
most the size of the text times the order; I discovered later that the
necessary state was simply linear in the size of the input. That doesn't
mean the same scheme is practical for compression, only that high-order
models are actually rather cheap in memory.

---Dan