Skip to content

komm.HuffmanCode

Binary Huffman code. It is an optimal (minimal average length) symbol 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) and complete.

Parameters:

  • pmf (ArrayLike) –

    The pmf $p$ to be considered. Must be a 1D-array of size $|\mathcal{X}|$ of non-negative values that sum to $1$.

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

    The policy to be used when constructing the code. 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. 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 average length.

Examples:

>>> pmf = [0.2, 0.4, 0.2, 0.1, 0.1]

>>> code = komm.HuffmanCode(pmf)
>>> code.codewords
[(1, 0), (0, 0), (1, 1), (0, 1, 0), (0, 1, 1)]
>>> code.average_length(pmf)
2.2

>>> code = komm.HuffmanCode(pmf, policy="low")
>>> code.codewords
[(0, 1), (1,), (0, 0, 0), (0, 0, 1, 0), (0, 0, 1, 1)]
>>> code.average_length(pmf)
2.2

>>> code = komm.HuffmanCode(pmf, assignment="canonical")
>>> code.codewords
[(0, 0), (0, 1), (1, 0), (1, 1, 0), (1, 1, 1)]
>>> code.average_length(pmf)
2.2