prefix_code_tree

Prefix code tree data structure for the coding experiments library.

This module implements a prefix code tree (also known as a decoding tree or code tree) used for efficient decoding of prefix codes. The tree enables unique decoding of variable-length codes without separators between codewords.

class codinglab.encoders.prefix_code_tree.TreeNode(*, value=None, children=<factory>)[source]

Bases: Generic[ChannelChar, SourceChar]

Node in a prefix code tree. Each node in the tree represents either:

  • An internal node (value is None): has children for possible next symbols in a code sequence

  • A leaf node (value is not None): represents a complete code for a source symbol

Parameters:
value: SourceChar | None = None

Source symbol at this node, or None for internal nodes.

children: Dict[ChannelChar, TreeNode[ChannelChar, SourceChar]]

Dictionary mapping channel symbols to child nodes.

leaf()[source]

Check if this node is a leaf node.

A leaf node has no children, meaning it represents a complete code for a source symbol.

Return type:

bool

Returns:

True if this node has no children (is a leaf), False otherwise (is an internal node)

__init__(*, value=None, children=<factory>)
Parameters:
Return type:

None

class codinglab.encoders.prefix_code_tree.PrefixCodeTree(root=None)[source]

Bases: Generic[ChannelChar, SourceChar]

Prefix code tree for efficient decoding.

This tree data structure enables decoding of prefix codes by traversing from the root to leaves based on the input sequence. Each leaf corresponds to a source symbol, and the path from root to leaf defines the code for that symbol.

Parameters:

root (TreeNode[ChannelChar, SourceChar] | None)

__init__(root=None)[source]

Initialize a prefix code tree.

Parameters:

root (Optional[TreeNode[TypeVar(ChannelChar), TypeVar(SourceChar)]]) – Optional root node for the tree. If None, creates a new empty root node.

Return type:

None

root

Root node of the prefix code tree.

insert_code(code, symbol)[source]

Insert a code sequence into the tree.

This method builds the tree by adding a path from the root corresponding to the code sequence, ending with a leaf node containing the source symbol.

Parameters:

  • code (List[TypeVar(ChannelChar)]) – Sequence of channel symbols representing the code

  • symbol (TypeVar(SourceChar)) – Source symbol that this code represents

Raises:

ValueError – If the code conflicts with existing codes (violates prefix property)

Return type:

None

decode(sequence, position=0)[source]

Decode a symbol from a sequence starting at the given position.

This method traverses the tree from the root, following symbols from the sequence until it reaches a leaf node. It returns the decoded symbol and the new position in the sequence (after consuming the code).

Parameters:

  • sequence (List[TypeVar(ChannelChar)]) – List of channel symbols to decode

  • position (int) – Starting position in the sequence (default: 0)

Returns:

  • decoded_symbol: Source symbol decoded, or None if decoding failed

  • new_position: Position in sequence after consuming the code

Return type:

Tuple of (decoded_symbol, new_position) where

Raises:

ValueError – If the sequence is incomplete or contains symbols not in the tree

vizualize()[source]
Return type:

Digraph