komm.RunLengthCode

Run-length code. It is a lossless data compression algorithm which parses the source sequence into runs, that is, blocks of repeated symbols. Let $\mathcal{X}$ be the source alphabet, and $\mathcal{Y}$ be the target alphabet. The notation used here is the following: $L \geq 1$ is the maximum run length. The token format is $(x, \ell)$, where $x \in \mathcal{X}$ is the repeated symbol and $\ell \in [1 : L]$ is the length of the run; runs longer than $L$ are split into two or more tokens. A token is represented as a fixed-size word in $\mathcal{Y}^n$, consisting of $x$ followed by $\ell - 1$, where $$n = \lceil \log |\mathcal{X}| \rceil + \lceil \log L \rceil$$ and all logs are to base $|\mathcal{Y}|$. For more details, see Wikipedia: Run-length encoding.

Note

Here, for simplicity, we assume that the source alphabet is $\mathcal{X} = [0 : |\mathcal{X}|)$ and the target alphabet is $\mathcal{Y} = [0 : |\mathcal{Y}|)$, where $|\mathcal{X}| \geq 2$ and $|\mathcal{Y}| \geq 2$ are called the source cardinality and target cardinality, respectively.

Parameters:

• source_cardinality (int) –

  The source cardinality $|\mathcal{X}|$. Must satisfy $|\mathcal{X}| \geq 2$.

• max_run_length (int) –

  The maximum run length $L$. Must satisfy $L \geq 1$.

• target_cardinality (int) –

  The target cardinality $|\mathcal{Y}|$. Must satisfy $|\mathcal{Y}| \geq 2$. The default value is $2$ (binary).

Examples:

>>> code = komm.RunLengthCode(source_cardinality=3, max_run_length=4)

source_to_tokens()

Encodes a given sequence of source symbols to the corresponding list of tokens.

Examples:

>>> code = komm.RunLengthCode(source_cardinality=3, max_run_length=4)
>>> code.source_to_tokens([0, 0, 0, 2, 2, 1, 1, 1, 1, 1])
[(0, 3), (2, 2), (1, 4), (1, 1)]

tokens_to_source()

Decodes a given list of tokens to the corresponding sequence of source symbols.

Examples:

>>> code = komm.RunLengthCode(source_cardinality=3, max_run_length=4)
>>> code.tokens_to_source([(0, 3), (2, 2), (1, 4), (1, 1)])
array([0, 0, 0, 2, 2, 1, 1, 1, 1, 1])

tokens_to_target()

Returns the target alphabet representation corresponding to a given list of tokens.

Examples:

>>> code = komm.RunLengthCode(source_cardinality=3, max_run_length=4)
>>> code.tokens_to_target([(0, 3), (2, 2), (1, 4), (1, 1)])
array([0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0])

target_to_tokens()

Returns the list of tokens corresponding to a given target alphabet representation.

Examples:

>>> code = komm.RunLengthCode(source_cardinality=3, max_run_length=4)
>>> code.target_to_tokens([0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0])
[(0, 3), (2, 2), (1, 4), (1, 1)]

encode()

Encodes a sequence of source symbols to a sequence of target symbols.

Parameters:

• input (ArrayLike) –

  The sequence of source symbols to be encoded. Must be a 1D-array with elements in $\mathcal{X}$.

Returns:

• output (Array1D[integer]) –

  The sequence of encoded target symbols. It is a 1D-array with elements in $\mathcal{Y}$.

Examples:

>>> code = komm.RunLengthCode(source_cardinality=3, max_run_length=4)
>>> code.encode([0, 0, 0, 2, 2, 1, 1, 1, 1, 1])
array([0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0])

decode()

Decodes a sequence of target symbols to a sequence of source symbols.

Parameters:

• input (ArrayLike) –

  The sequence of target symbols to be decoded. Must be a 1D-array with elements in $\mathcal{Y}$. Also, the sequence must be a valid output of the encode method.

Returns:

• output (Array1D[integer]) –

  The sequence of decoded source symbols. It is a 1D-array with elements in $\mathcal{X}$.

Examples:

>>> code = komm.RunLengthCode(source_cardinality=3, max_run_length=4)
>>> code.decode([0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0])
array([0, 0, 0, 2, 2, 1, 1, 1, 1, 1])