Basic Examples (1) 

Enumerate all 16 proper six-bit binary codes corresponding to non-equivalent compact Huffman trees with 8 leaves in a "BitVector" data structure:

In[1]:=

Out[1]=

Scope (3) 

List all 16 six-bit binary codes that satisfy the proper conditions given enumeration data in bit vector:

In[2]:=

Out[3]=

Find the compact Huffman tree for the proper 8-bit code {1, 1, 0, 1, 0, 0, 0, 1}:

In[4]:=

Out[4]=

Demonstrate the process for constructing the tree corresponding to the code {1, 1, 0, 1, 0, 0, 0, 1} as described in Details & Options above:

In[5]:=

Out[5]=

Applications (1) 

DistinctCompactBinaryHuffmanCode provides a way to generate random trees with certain constraints. For instance, for n=22, instead of generating all 175586 24-leaf distinct compact Huffman trees at once, we randomly generate an index first and access the corresponding binary code from the bit vector:

In[6]:=

Out[6]=

In[7]:=

In[8]:=

Out[9]=

In[10]:=

Out[10]=

Properties and Relations (3) 

There is one-to-one correspondence between proper n-bit binary codes and (n+2)-leaf non-equivalent compact Huffman trees. For example when n=6:

In[11]:=

Out[14]=

All trees above have 8=6+2 leaves:

In[15]:=

Out[15]=

All trees above have one depth greater than the number of ones in the binary code:

In[16]:=

Out[16]=

Possible Issues (4) 

The number of n-bit proper codes and the corresponding trees grow rapidly with bit length n. For instance a 60-bit code has more than 7.7 trillion candidates. Therefore use "CountOnly" to bypass the enumeration function and avoid binary code generation:

In[17]:=

Out[17]=

DistinctCompactBinaryHuffmanCode returns unevaluated for large bit-code length:

In[18]:=

Out[18]=

Only binary code is supported:

In[19]:=

Out[19]=

The following example does not meet the proper conditions described above in Details & Options. Reading from left to right, we have a run of one zero and a next run of 6 zeros. Since 6 > 2·1+1, this binary code fails to correspond to a compact Huffman tree:

In[20]:=

Out[20]=

The concept of equivalence for compact Huffman trees is not the same as graph isomorphism. The following two trees are considered equivalent Huffman trees (Even and Lempel, 1972), but obviously they are not isomorphic in graph-theoretical sense:

In[21]:=

Out[22]=

In[23]:=

Out[23]=

Neat Examples (2) 

Plot a large graph from the 12-dimensional proper codes. Points are connected if their Hamming distances meet a predefined value:

In[24]:=

In[25]:=

If the target Hamming distance is 1:

In[26]:=

Out[26]=

If the target Hamming distance is 2:

In[27]:=

Out[27]=

Visualize the compact codes with ArrayPlot:

In[28]:=

In[29]:=

Out[29]=