{"thread":{"id":"7013","subject":"Re: pack v4 status","startedAt":"2007-02-28T10:04:56Z","lastAt":"2007-02-28T10:04:56Z","messageCount":1,"participants":["linux@horizon.com"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"35794","messageId":"20070228100456.13486.qmail@science.horizon.com","threadId":"7013","inReplyTo":null,"subject":"Re: pack v4 status","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2007-02-28T10:04:56Z","receivedAt":"2007-02-28T10:04:56Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"Just a minor note:\n\nI you want to have an arbitrary-sized string table without special cases,\nthe standard binary Huffman tree construction algorithm can be extended\nquite simply to a radix-256 tree, so every code is an integer number\nof bytes long.\n\nTake the input strings, and sort them in order of frequency of appearance.\nPad them at the end with dummy strings (frequency = 0) until the number\nequals 1 mod 255.\n\nThen take the last (least frequent) 256 strings off the list, and\nreplace them with a single prefix whose frequency is the sum of all of\nthe components.  Each of the selected strings will be encoded as the\nprefix (whose code has not yet been decided) plus 256 possible byte values.\nInsert the new prefix into the list in sorted order.\n\nRepeat until the list has only one entry, which is represented by a\nzero-length prefix.  (Since each step replaces 256 entries by 1 entry,\nthe number of entries never changes mod 255, so the algorithm always will\nconverge to one entry.)\n\n\nThis is generally encoded more compactly as a \"canonical Huffman tree\".\nFor each string, forget the actual encoding decided on here, and just\nremember the number of bytes assigned to encode it; this is the only\nnumber you need to record to reconstruct the tree for decoding.\nThen count the number of strings to be encoded with 1, 2, 3... bytes.\n\nTo decode, read one byte.  If the byte is less than the number of 1-byte\nstrings, its value is the string's position in the 1-byte string table.\n\nIf the byte is >= the number of 1-byte strings, subtract the number of 1-byte\nstrings, multiply by 256, and add a following byte.  This is the position in\nthe 2-byte string table.\n\nIf the value is >= the number of 2-byte strings, subtract, multiply by\n256, and add another trailing byte.  This is the position in the 3-byte\nstring table.  Repeat as necessary.\n\n\nThere are elaborations on this to bound the maximum number of bytes\nrequired; see the zlib source for details.\n\nIf you have a significant number of unique (frequency == 1) strings,\nyou can encode them in-line after a common \"unique string\" prefix\n(which can have a frequency greater than 1).\n\n\nI'm not sure if you can follow all that (it helps to understand Huffmann\ntrees already), but I can explain at greater length if necessary.\nThe important thing is that it's quite straightforward and provides\na general solution.\n"}]}