Skip to content

komm.LempelZivWelchCode

Lempel–Ziv–Welch (LZW) code. It is a lossless data compression algorithm which is variation of the Lempel–Ziv 78 algorithm. 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

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 (NDArray[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 (NDArray[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])