<h2>Motivation</h2>

<p>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.</p>

<p>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 <code>00..</code>. 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.</p>

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

<h2>The question</h2>

<p>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 <code>1..n</code> bits.</p>

<p>Note: I know there are simple solutions to the hypothetical scenario above (using <code>00..</code> 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".</p>

<p>I've asked the same question on <a href="https://stackoverflow.com/questions/4938930/huffman-terminator-bitstring">Stack Overflow</a>, but decided to post it here, too, because it's a very theoretical question and most likely won't have many real world applications.</p>

<h2>Example</h2>

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

<p><code>001011</code></p>

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

<pre><code>Combination   Decoded symbols
[0, 1]        AABABB
[00,01,1]     ACBC
[0,10,11]     AABC
[00,01,10,11] ACD
</code></pre>

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

<p><code>00101101</code></p>

<p>This is a valid "Huffman terminator" for <code>n=2</code>, 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 <code>n=2</code> because it's the minimal length for the combination <code>[00, 01, 10, 11]</code> to decode each symbol once.</p>

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

<h2>What I'm looking for</h2>

<ul>
<li><p>Algorithms/ideas to find or generate Huffman terminators for a given <code>n</code>. 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.</p></li>
<li><p>Specific Huffman terminators, <code>n=8</code> and <code>n=16</code>, although it might be computational expensive to generate them and they will perhaps be very long.</p></li>
<li><p>Papers/links about this problem (or similar ones) if there are any.</p></li>
</ul>

<h2>Bonus</h2>

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

CC BY-SA 2.5
2011-02-09T01:14:37.863Z
Did you try the following: pick a sufficiently long random bit string, and prove that it is a "Huffman terminator" w.h.p.?
Jukka Suomela
CC BY-SA 2.5
2011-02-09T01:42:51.563Z
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.
Jukka Suomela
CC BY-SA 2.5
2011-02-09T01:46:03.220Z
I verified that `0001011001110100111010011100010101111101110` (the 43-bit string stated in the question) is indeed a Huffman terminator by calculation.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-10T00:58:51.450Z
Out of curiosity, how did you find this 43-bit string?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-10T03:29:05.633Z
@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.
schnaader
CC BY-SA 2.5
2011-02-10T04:53:47.210Z
Thanks.  According to my calculation, there are 25 Huffman codes which consist of codewords of at most 3 bits.  Can you please check the number 50?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-10T12:50:54.783Z
@Tsuyoshi: Yes, there were indeed 25 of them, I even labelled them A-Y. Was in a hurry above and just remembered it was a multiple of 5 :)
schnaader
<ds.algorithms><coding-theory>
Huffman "terminator" bitstring
schnaader
# Huffman "terminator" bitstring

(Asked by: username_0 on 2011-02-08)

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.

**Tags:** ds.algorithms, coding-theory

> **Comments:**
> **username_1**: Did you try the following: pick a sufficiently long random bit string, and prove that it is a "Huffman terminator" w.h.p.?  
> **username_1**: 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.  
> **username_2**: I verified that `0001011001110100111010011100010101111101110` (the 43-bit string stated in the question) is indeed a Huffman terminator by calculation.  
> **username_2**: Out of curiosity, how did you find this 43-bit string?  
> **username_0**: @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.  
> **username_2**: Thanks.  According to my calculation, there are 25 Huffman codes which consist of codewords of at most 3 bits.  Can you please check the number 50?  
> **username_0**: @Tsuyoshi: Yes, there were indeed 25 of them, I even labelled them A-Y. Was in a hurry above and just remembered it was a multiple of 5 :)  

---

## 0 answers

