LZP (compression algorithm)

---

LZP (Lempel-Ziv-Prediction)

Class	Lossless data compression
Worst-case performance	O(n)
Best-case performance	O(n)
Average performance	O(n)
Worst-case space complexity	O(n) total, O(TABLE_SIZE) auxiliary.

LZP (short for Lempel-Ziv-Prediction) is a lossless data compression algorithm that leverages the insight that the characters immediately prior a given position tend to be strong predictors for the immediately following characters. It's closely related to PPM context modeling and Markov chains.

Algorithm overview

For every input byte within the input stream, the previous N bytes are gathered to create a finite context of order N. This context is hashed and used to retrieve the corresponding entry in a hashtable, which returns a reference to an earlier position in the already‑processed data. The upcoming sequence of bytes is then compared with the data at that reference point, and the length of the matching segment is determined.

The result of this comparison is written in the output stream using an encoding scheme such as:

• If the matching length is zero, a flag indicating a negative match is recorded followed by the literal byte itself.
• If the matching length is one or greater, a flag indicating a positive match is recorded and then the length of the match is written.

History

The technique was first described by Charles Bloom in 1996. and later popularised in hobbyist publications related to the demoscene due to its low implementation footprint. It is often used as a pre-processor for stronger LZ-type or entropy compressors to improve their compression ratio without a noticeable speed penalty

Comparison with the PPP Predictor algorithm

In the same year of the publication of LZP, another similar algorithm was indipendently published as part of the PPP protocol called Predictor. Multiple online sources have used their name interchangeably even thought the two algorithms are distinct. To be specific, Predictor is different to LZP in that it stores literals instead of pointers in the hashtable, doesn't require jumping to previous locations in the stream and matches single bytes only without attempting to find multi-byte matches.

LZP variants

Documented variants of LZP involve different choices of parameters, further processing with entropy coders or different hashtable matching systems:

• LZP1: A fixed order-3 hashed context model was used, with a hashtable of size 2¹² and match lengths were written using variable-length integers.
• LZP2: Same as LZP1, but literals and match lengths were written with a Huffman coder.
• LZP3: A order-4 context model was used with a 2¹⁶ table size. Literals and match lengths were written with a order-I Huffman coder. Notably, the table also contains the contexts, together with a mechanism that finds the highest-order context that does have a match in the table.
• LZP4: A order-5 context model was used and a table with 2¹⁶ entries, with order-1 arithmetic encoding of match lengths and order-4 PPM encoding of literals. In this version, table entries aren't a single pointer, but contain instead a 2-dimensional linked list of pointers.

Typical parameters

• Hashtable size: A value of 2¹⁶ bytes or greater is typical on modern implementations. Early implementations on memory-constrained hardware would choose a lower amount such as 2¹² or 2⁸ at the cost of a worse compression ratio.
• Context size: How many most-recent input bytes should be taken into account when creating the hash. For example, the original implementation of LZP1 uses a size of 3 bytes.
• Hash function: The hash function should be chosen to yield a hash with representable size equivalent to the hashtable size. For example, in the original implementation of LZP1, the function H = ((C >> 11) ^ C) & 0xFFF was chosen, which yields a 12-bit hash that can be immediately used in a hashtable of size 2¹².

Performance characteristics

• Compression ratio: In the worst case, LZP's output can be at most 12.5% larger than the input, as an all-miss string yields 9 bits per 8 input bits. The best case ratio is dependent on the maximum value representable by the chosen encoding of the match length. On real-world data, LZP alone provides modest compression, around 50% or worse for written text or worse for more general-purpose textual data with markup, but pairing it with an entropy coder has the potential to cut in half again the ratio.
• Speed: due to the lack of tree structures, search buffers or the need for dynamic allocations, LZP is always relatively faster than any algorithm that would employ these techniques such as entropy coders and most LZ variants.
• Memory usage: The predictor table is fixed, no dynamic allocation is required during processing except for LZP4. It is recommended to choose a table size that would fit in the CPU cache to avoid the table overflowing into RAM, which would cause substantial performance degradation.

See also

• Lempel–Ziv
• Reduced Offset Lempel-Ziv
• Markov chain
• Prediction by partial matching
• Lossless compression

References

This article "LZP (compression algorithm)" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:LZP (compression algorithm). Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Genozip
• Channel simulation
• BGZF
• QUAD (compressor)
• LZ77 and LZ78
• Bzip3
• LZJB

---