Re: pack v4 status

[linux@horizon.com]

Just a minor note:

I you want to have an arbitrary-sized string table without special cases,
the standard binary Huffman tree construction algorithm can be extended
quite simply to a radix-256 tree, so every code is an integer number
of bytes long.

Take the input strings, and sort them in order of frequency of appearance.
Pad them at the end with dummy strings (frequency = 0) until the number
equals 1 mod 255.

Then take the last (least frequent) 256 strings off the list, and
replace them with a single prefix whose frequency is the sum of all of
the components.  Each of the selected strings will be encoded as the
prefix (whose code has not yet been decided) plus 256 possible byte values.
Insert the new prefix into the list in sorted order.

Repeat until the list has only one entry, which is represented by a
zero-length prefix.  (Since each step replaces 256 entries by 1 entry,
the number of entries never changes mod 255, so the algorithm always will
converge to one entry.)


This is generally encoded more compactly as a "canonical Huffman tree".
For each string, forget the actual encoding decided on here, and just
remember the number of bytes assigned to encode it; this is the only
number you need to record to reconstruct the tree for decoding.
Then count the number of strings to be encoded with 1, 2, 3... bytes.

To decode, read one byte.  If the byte is less than the number of 1-byte
strings, its value is the string's position in the 1-byte string table.

If the byte is >= the number of 1-byte strings, subtract the number of 1-byte
strings, multiply by 256, and add a following byte.  This is the position in
the 2-byte string table.

If the value is >= the number of 2-byte strings, subtract, multiply by
256, and add another trailing byte.  This is the position in the 3-byte
string table.  Repeat as necessary.


There are elaborations on this to bound the maximum number of bytes
required; see the zlib source for details.

If you have a significant number of unique (frequency == 1) strings,
you can encode them in-line after a common "unique string" prefix
(which can have a frequency greater than 1).


I'm not sure if you can follow all that (it helps to understand Huffmann
trees already), but I can explain at greater length if necessary.
The important thing is that it's quite straightforward and provides
a general solution.