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

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)
np.float64(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)
np.float64(0.96)