Skip to content

komm.LempelZivWelchCode

Lempel–Ziv–Welch (LZW) code. It is a lossless data compression algorithm which is a variation of the Lempel–Ziv 78 algorithm. Let $\mathcal{X}$ be the source alphabet, and $\mathcal{Y}$ be the target alphabet. The token format is $p \in \mathbb{N}$, the index of the corresponding dictionary entry. The index $p$ is represented as a variable-size word in $\mathcal{Y}^k$, where $k = \lceil \log_{|\mathcal{Y}|} i \rceil$, and $i$ is the size of the dictionary at the moment. For more details, see Say06, Sec. 5.4.2.

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

  • target_cardinality (int) –

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

Examples:

>>> lzw = komm.LempelZivWelchCode(2)  # Binary source, binary target
>>> lzw = komm.LempelZivWelchCode(3, 4)  # Ternary source, quaternary target

source_to_tokens()

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

Examples:

>>> lzw = komm.LempelZivWelchCode(2)
>>> lzw.source_to_tokens(np.zeros(15, dtype=int))
[0, 2, 3, 4, 5]

tokens_to_source()

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

Examples:

>>> lzw = komm.LempelZivWelchCode(2)
>>> lzw.tokens_to_source([0, 2, 3, 4, 5])
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])

tokens_to_target()

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

Examples:

>>> lzw = komm.LempelZivWelchCode(2)
>>> lzw.tokens_to_target([0, 2, 3, 4, 5])
array([0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1])

target_to_tokens()

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

Examples:

>>> lzw = komm.LempelZivWelchCode(2)
>>> lzw.target_to_tokens([0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1])
[0, 2, 3, 4, 5]

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:

>>> lzw = komm.LempelZivWelchCode(2)
>>> lzw.encode(np.zeros(15, dtype=int))
array([0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1])

>>> lzw = komm.LempelZivWelchCode(2, 8)
>>> lzw.encode(np.zeros(15, dtype=int))
array([0, 2, 3, 4, 5])

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:

>>> lzw = komm.LempelZivWelchCode(2)
>>> lzw.decode([0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1])
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])

>>> lzw = komm.LempelZivWelchCode(2, 8)
>>> lzw.decode([0, 2, 3, 4, 5])
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])