🚀 go-pugleaf

> ...
> We have not discussed different ways to code the output numbers. Huffman
> coding and arithmetic coding both produce quite respectable improvements
> over and above the compression of the basic Y method. Little is known
> about the best way to code a sequence from a dynamically expanding
> alphabet; ...

When I read the Miller-Wegman paper a couple of years ago I had the
following idea: rather than trying to compress the coding of a
dynamically expanding alphabet, keep the codeword size fixed at the
maximum size needed for a full dictionary, and use currently undefined
codewords to encode *implicit digrams*.  That is, any codeword that is
greater than the current dictionary size stands for a particular
digram.  So in effect, the dictionary starts out containing all
possible digrams (such as AA, AB, etc.), or as many as will fit, and
then as each new entry is made to the dictionary, it replaces one of
these implicit entries.  So when the dictionary is fairly new, and
most of the input would be represented as a single character per
codeword, most of it can be represented as two characters per codeword
instead (if the codeword is about two characters big). While this
shouldn't be as effective as clever coding of the expanding dictionary
alphabet, it has the advantage of being computationally cheap.

There are various ways this could be incorporated in the encoding.
The least disruptive is to output an implicit digram codeword only
where you would have otherwise output two consecutive single-character
codewords whose implicit digram currently exists (implicitly) in the
dictionary.

Other ways would consider it a real dictionary entry in the sense that
you would match it normally rather than after determining that there
are two consecutive single-char codes, but I'm sure this would have
implications that could be problematic.

Forgive me if this is an old (or bad) idea -- I haven't been following
this field very closely.
--
David B Rosen, Cognitive & Neural Systems         Internet: rosen@cns.bu.edu
Center for Adaptive Systems                  Bitnet: rosen%kenmore AT BUACCA
Boston University.                 UUCP: {harvard,uunet}!bu.edu!bucasb!rosen
"Says who?                  I speak for nobody, except occasionally myself."