6
$\begingroup$

Motivation

Imagine a huffman compressed file that gets downloaded partially, like in P2P software, so we allocate disk space for the whole file first and then start downloading random file chunks. One of the huffman codes (but we don't know which) is an end code, so if this code is decoded, we stop. Assuming the file consists of several huffman compressed streams, we can try to decompress some of them before the download finished.

The way the disk space is preallocated is important now: Let's assume we have the start of a huffman stream, but it isn't complete, so we run into the preallocated disk space. Usually, this space is all 0, so we'd keep decoding symbols with huffman code 00... If this isn't our end code, we don't notice the "invalid" data and f.e. if there's 2 GB of preallocated space, we're doing much useless decoding.

So we'd like to preallocate the space in a way to make decoding stop as soon as possible.

The question

I'm looking for the shortest bitstring that acts as a "Huffman terminator", meaning if we decode this string, we'll decode every Huffman code at least once, so we'll definitely receive an end code. This should work for every combination of Huffman codes of length 1..n bits.

Note: I know there are simple solutions to the hypothetical scenario above (using 00.. as an end code, using P2P segment data to detect chunks not downloaded yet), but this is just an example scenario to show a theoretical use of a "Huffman terminator" bitstring, I'm not interested in solving this scenario, but looking for algorithms/ways/ideas to generate/find bitstrings that act as "Huffman terminator".

I've asked the same question on Stack Overflow, but decided to post it here, too, because it's a very theoretical question and most likely won't have many real world applications.

Example

Let's look at the possible Huffman code combinations for n = 2: [0, 1], [00, 01, 1], [0, 10, 11], [00, 01, 10, 11]. Now let's start with a bitstring that contains every possible bit sequence of length 1..n (0, 1, 00, 01, 10, 11):

001011

Decoding with the different Huffman code combinations gives (huffman codes are assigned to symbols A..D):

Combination   Decoded symbols
[0, 1]        AABABB
[00,01,1]     ACBC
[0,10,11]     AABC
[00,01,10,11] ACD

This is a good start and it already decodes every Huffman code for the first three ones, but if we decode it with [00, 01, 10, 11], we're missing symbol B (Huffman code 01). So let's just append this to our bitstring:

00101101

This is a valid "Huffman terminator" for n=2, 8 bits in length. If we'd preallocate our disk space with this byte, we'd be sure to terminate all huffman codes that won't exceed 2 bits. We even know there won't be shorter terminator strings for n=2 because it's the minimal length for the combination [00, 01, 10, 11] to decode each symbol once.

I also found a "Huffman terminator" for n=3, 0001011001110100111010011100010101111101110 (43 bits), but I'm not 100% sure if it's correct and I don't know if it's the shortest one.

What I'm looking for

  • Algorithms/ideas to find or generate Huffman terminators for a given n. My attempt would be similar to the example: generating a start string and appending bits as needed to satisfy all different Huffman code combinations. But I'm sure there are better ways.

  • Specific Huffman terminators, n=8 and n=16, although it might be computational expensive to generate them and they will perhaps be very long.

  • Papers/links about this problem (or similar ones) if there are any.

Bonus

Bonus points for finding "Huffman terminators" that also work if we start at bit position 1..n, so it even terminates if data was decoded before and we won't arrive and start a new huffman code at the first bit.

$\endgroup$
  • $\begingroup$ Did you try the following: pick a sufficiently long random bit string, and prove that it is a "Huffman terminator" w.h.p.? $\endgroup$ – Jukka Suomela Feb 9 '11 at 1:14
  • 1
    $\begingroup$ And a bit more concrete idea: Take any Huffman code. Represent the Huffman decoder as a directed graph $G$ such that each node has two out-edges, one with label "0" and one with label "1" (you can construct the graph by taking the Huffman tree and adding extra edges from the leaf nodes to the children of the root nodes). Now if you take a random bit string and feed it to the decoder, it corresponds to a random walk in digraph $G$. You should be able to apply results related to hitting times of random walks + the probabilistic method to prove that a Huffman terminator of certain length exists. $\endgroup$ – Jukka Suomela Feb 9 '11 at 1:42
  • 1
    $\begingroup$ I verified that 0001011001110100111010011100010101111101110 (the 43-bit string stated in the question) is indeed a Huffman terminator by calculation. $\endgroup$ – Tsuyoshi Ito Feb 9 '11 at 1:46
  • $\begingroup$ Out of curiosity, how did you find this 43-bit string? $\endgroup$ – Tsuyoshi Ito Feb 10 '11 at 0:58
  • $\begingroup$ @Tsuyoshi: Like in the example, I started with a bit string that contains every bitstring of length 1..3 - this is the beginning, 000101100111 - after that, I checked all the huffman code combinations (there were about 50 IIRC) and appended missing huffman codes. $\endgroup$ – schnaader Feb 10 '11 at 3:29

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.