Skip to content

komm.HuffmanCode

Binary Huffman code. It is an optimal (minimal expected rate) fixed-to-variable length code for a given pmf $p$ over $\mathcal{X}$. For more details, see Say06, Sec. 3.2.

Notes

Huffman codes are always prefix-free (hence uniquely decodable).

Parameters:

  • pmf (ArrayLike) –

    The pmf $p$ to be considered. It must be a one-dimensional array of floats of size $|\mathcal{X}|$. The elements must be non-negative and sum to $1$.

  • source_block_size (int) –

    The source block size $k$. The default value is $k = 1$.

  • policy (Literal['high', 'low']) –

    The policy to be used when constructing the code. It must be either 'high' (move combined symbols as high as possible) or 'low' (move combined symbols as low as possible). The default value is 'high'. It affects the codeword lengths only in the presence of ties.

  • assignment (Literal['tree', 'canonical']) –

    The strategy used to assign the codewords, once the Huffman tree is built. It must be either 'tree' (read the codewords off the paths of the tree, bit $\mathtt{1}$ being assigned to the less probable of the two merged nodes, as in classic textbook presentations) or 'canonical' (the canonical code with the resulting lengths). The default value is 'tree'. It affects neither the codeword lengths nor the rate.

Examples:

>>> pmf = [0.8, 0.1, 0.1]

>>> code = komm.HuffmanCode(pmf)
>>> code.enc_mapping
{(0,): (0,),
 (1,): (1, 0),
 (2,): (1, 1)}
>>> code.rate(pmf)
1.2

>>> code = komm.HuffmanCode(pmf, 2)
>>> code.enc_mapping
{(0, 0): (0,),
 (0, 1): (1, 0, 1),
 (0, 2): (1, 1, 0),
 (1, 0): (1, 1, 1),
 (1, 1): (1, 0, 0, 1, 0, 0),
 (1, 2): (1, 0, 0, 1, 0, 1),
 (2, 0): (1, 0, 0, 0),
 (2, 1): (1, 0, 0, 1, 1, 0),
 (2, 2): (1, 0, 0, 1, 1, 1)}
>>> code.rate(pmf)
0.96

>>> code = komm.HuffmanCode(pmf, 2, assignment="canonical")
>>> code.enc_mapping
{(0, 0): (0,),
 (0, 1): (1, 0, 0),
 (0, 2): (1, 0, 1),
 (1, 0): (1, 1, 0),
 (1, 1): (1, 1, 1, 1, 0, 0),
 (1, 2): (1, 1, 1, 1, 0, 1),
 (2, 0): (1, 1, 1, 0),
 (2, 1): (1, 1, 1, 1, 1, 0),
 (2, 2): (1, 1, 1, 1, 1, 1)}
>>> code.rate(pmf)
0.96