Skip to content

komm.LempelZiv78Code

Lempel–Ziv 78 (LZ78 or LZ2) code. It is a lossless data compression algorithm which is asymptotically optimal for ergodic sources. For more details, see Say06, Sec. 5.4.2 and CT06, Sec. 13.4.2.

Parameters:

  • source_cardinality (int) –

    The source cardinality $S$. Must be an integer greater than or equal to $2$.

  • target_cardinality (int) –

    The target cardinality $T$. Must be an integer greater than or equal to $2$. Default is $2$ (binary).

Examples:

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

encode

Encodes a sequence of source symbols using the LZ78 encoding algorithm.

Parameters:

  • input (ArrayLike) –

    The sequence of symbols to be encoded. Must be a 1D-array with elements in $[0:S)$ (where $S$ is the source cardinality of the code).

Returns:

  • output (NDArray[integer]) –

    The sequence of encoded symbols. It is a 1D-array with elements in $[0:T)$ (where $T$ is the target cardinality of the code).

Examples:

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

>>> lz78 = komm.LempelZiv78Code(2, 8)
>>> lz78.encode(np.zeros(15, dtype=int))
array([0, 1, 0, 2, 0, 3, 0, 4, 0])

decode

Decodes a sequence of encoded symbols using the LZ78 decoding algorithm.

Parameters:

  • input (ArrayLike) –

    The sequence of symbols to be decoded. Must be a 1D-array with elements in $[0:T)$ (where $T$ is the target cardinality of the code). Also, the sequence must be a valid output of the encode method.

Returns:

  • output (NDArray[integer]) –

    The sequence of decoded symbols. It is a 1D-array with elements in $[0:S)$ (where $S$ is the source cardinality of the code).

Examples:

>>> lz78 = komm.LempelZiv78Code(2)
>>> lz78.decode([0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0])
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])

>>> lz78 = komm.LempelZiv78Code(2, 8)
>>> lz78.decode([0, 1, 0, 2, 0, 3, 0, 4, 0])
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])