Skip to content

komm.HuffmanCode

Binary Huffman code. It is an optimal (minimal expected rate) fixed-to-variable length code for a given probability mass function. For more details, see Say06, Sec. 3.2.

Notes

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

Parameters:

  • pmf (ArrayLike) –

    The probability mass function of the source.

  • 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'.

Examples:

>>> pmf = [0.7, 0.15, 0.15]

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

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