prefix_coder

Base class for prefix code encoder-decoders for the coding experiments library.

This module provides an abstract base class for implementing prefix codes, which are variable-length codes where no codeword is a prefix of another. This property enables unique decoding without separators between codewords. Common examples include Huffman coding, Shannon-Fano coding, and others.

class codinglab.encoders.prefix_coder.PrefixEncoderDecoder(source_alphabet, channel_alphabet)[source]

Bases: Encoder[SourceChar, ChannelChar], Decoder[SourceChar, ChannelChar], ABC

Abstract base class for prefix code encoder-decoders.

This class implements the common functionality for prefix codes, including encoding, decoding, and maintaining both a code table and a decoding tree. Concrete implementations must define how to build the prefix code tree based on their specific algorithm.

Parameters:
_source_alphabet

Alphabet of source symbols to encode

_channel_alphabet

Alphabet of channel symbols for encoding

_code_table

Mapping from source symbols to their code sequences

_tree

Prefix code tree used for decoding

__init__(source_alphabet, channel_alphabet)[source]

Initialize the prefix encoder-decoder with alphabets.

Parameters:

  • source_alphabet (Sequence[TypeVar(SourceChar)]) – Sequence of source symbols to be encoded

  • channel_alphabet (Sequence[TypeVar(ChannelChar)]) – Sequence of channel symbols available for encoding

Raises:

ValueError – If either alphabet is empty

Return type:

None

encode(message)[source]

Encode a source message using the prefix code.

Parameters:

message (Sequence[TypeVar(SourceChar)]) – Sequence of source symbols to encode

Return type:

Sequence[TypeVar(ChannelChar)]

Returns:

Sequence of channel symbols representing the encoded message

Raises:

  • RuntimeError – If the code table has not been built

  • ValueError – If any symbol in the message is not in the source alphabet

decode(encoded)[source]

Decode a sequence of channel symbols using the prefix code tree.

Parameters:

encoded (Sequence[TypeVar(ChannelChar)]) – Sequence of channel symbols to decode

Return type:

Sequence[TypeVar(SourceChar)]

Returns:

Sequence of source symbols representing the decoded message

Raises:

  • RuntimeError – If the decoding tree has not been built

  • ValueError – If the encoded sequence cannot be decoded

property code_table: Dict[SourceChar, Sequence[ChannelChar]] | None

Get the encoding table if available.

Returns:

Dictionary mapping source symbols to their code sequences, or None if no code table has been built

property tree: PrefixCodeTree[ChannelChar, SourceChar] | None

Get the decoding tree if available.

Returns:

Prefix code tree used for decoding, or None if no tree has been built

property source_alphabet: Sequence[SourceChar]

Get the source alphabet.

Returns:

Sequence of source symbols that can be encoded

property channel_alphabet: Sequence[ChannelChar]

Get the channel alphabet.

Returns:

Sequence of channel symbols available for encoding